最小生成树

prim和kruskal算法

Posted by Jow on August 2, 2019

目录

  1. kruskal算法
  2. prim算法

认真的人才能取得很好的成绩。 算两个点的最短路径可以先通过最短路径算法去除环,然后通过广度优先搜索来得到任意两个点的最短路径.

图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中。不但包括了连通图里的全部顶点(英语:Vertex (graph theory)),且其全部边的权值之和亦为最小。

dijkstra算法

通过记录cost、parent以及已经遍历过得点来进行算法的构造。 这里的重点是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
local graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {}

local costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = math.huge

local parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = nil

local processed = {}

local function checkNodeIsAdded(node)
    for i, v in ipairs(processed) do
        if v == node then
            return true
        end
    end
    return false
end

local function findMinCostNode()
    local min = math.huge
    local node
    for i, v in pairs(costs) do
        if v < min and not checkNodeIsAdded(i) then
            min = v
            node = i
        end
    end
    return node
end

local function dijkstra()
    table.insert(processed, "start")
    local node = findMinCostNode()
    while node do
        local cost = costs[node]
        local neighbors = graph[node]
        for i, v in pairs(neighbors) do
            local newCost = cost + v
            if costs[i] > newCost then
                costs[i] = newCost
                parents[i] = node
            end
        end
        table.insert(processed, node)
        node = findMinCostNode()
    end
end

dijkstra()
for i, v in pairs(costs) do
    print(i,v)
end