目录
- kruskal算法
- prim算法
认真的人才能取得很好的成绩。 算两个点的最短路径可以先通过最短路径算法去除环，然后通过广度优先搜索来得到任意两个点的最短路径.
图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中。不但包括了连通图里的全部顶点（英语：Vertex (graph theory)），且其全部边的权值之和亦为最小。
kruskal算法
每次找到权值最小的边，然后进行判断是否已经形成通路，没有则添加这条边，否则不添加。
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
graph = {
{ value = 7, name = "ab", node = { "A", "B" } },
{ value = 8, name = "bc", node = { "B", "C" } },
{ value = 5, name = "ad", node = { "A", "D" } },
{ value = 9, name = "bd", node = { "D", "B" } },
{ value = 7, name = "be", node = { "E", "B" } },
{ value = 5, name = "ce", node = { "C", "E" } },
{ value = 15, name = "de", node = { "D", "E" } },
{ value = 6, name = "df", node = { "D", "F" } },
{ value = 8, name = "fe", node = { "F", "E" } },
{ value = 9, name = "eg", node = { "E", "G" } },
{ value = 11, name = "fg", node = { "F", "G" } }
}
table.sort(graph, function(a, b)
return a.value < b.value
end)
local result = {}
local nodes = {}
local trees = {}
local checkTwoNodeBelongToOneTree = function(node1, node2)
local tree1, i1, tree2, i2
for i, v in ipairs(trees) do
for j, k in ipairs(v) do
if k == node1 then
tree1 = v
i1 = i
end
end
end
for i, v in ipairs(trees) do
for j, k in ipairs(v) do
if k == node2 then
tree2 = v
i2 = i
end
end
end
if not tree1 then
print(node1,node2)
end
for i, v in ipairs(tree1) do
if v == node2 then
return true
end
end
local merTree
if i1 > i2 then
table.move(tree1, 1, #tree1, #tree2 + 1, tree2)
merTree = i1
else
table.move(tree2, 1, -1, -1, tree1)
merTree = i2
end
table.remove(trees, merTree)
return false
end
local function checkNode(node)
for i, v in ipairs(nodes) do
if v == node then
return false
end
end
table.insert(nodes, node)
return true
end
local function increaseTree(node, addNode)
for i, v in ipairs(trees) do
for j, k in ipairs(v) do
if k == node then
table.insert(v, addNode)
return
end
end
end
end
---@param graph graph
local function minTree(graph)
while #graph > 0 do
local v = graph[1]
local checkNode1 = checkNode(v.node[1])
local checkNode2 = checkNode(v.node[2])
if checkNode1 and checkNode2 then
trees[#trees + 1] = {}
table.insert(trees[#trees], v.node[1])
table.insert(trees[#trees], v.node[2])
elseif checkNode1 or checkNode2 then
if checkNode1 then
increaseTree(v.node[2], v.node[1])
else
increaseTree(v.node[1], v.node[2])
end
end
if checkNode1 or checkNode2 or not checkTwoNodeBelongToOneTree(v.node[1], v.node[2]) then
table.insert(result, v)
end
table.remove(graph, 1)
end
end
minTree(graph)
prim算法
和Kruskal算法类似，Prim算法也是使用的贪心算法。它的计算过程和Dijkstra算法非常的类似，在这里我们先学习prim算法，后面再讲述Dijkstra算法。 为了有效地实现prim算法，需要一种快速的方法来选择一条新的边来加入到集合A中边所构成的树里。
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
70
71
72
73
74
75
76
77
78
79
80
81
graph = {
{ value = 7, name = "ab", node = { "A", "B" } },
{ value = 8, name = "bc", node = { "B", "C" } },
{ value = 5, name = "ad", node = { "A", "D" } },
{ value = 9, name = "bd", node = { "D", "B" } },
{ value = 7, name = "be", node = { "E", "B" } },
{ value = 5, name = "ce", node = { "C", "E" } },
{ value = 15, name = "de", node = { "D", "E" } },
{ value = 6, name = "df", node = { "D", "F" } },
{ value = 8, name = "fe", node = { "F", "E" } },
{ value = 9, name = "eg", node = { "E", "G" } },
{ value = 11, name = "fg", node = { "F", "G" } }
}
table.sort(graph, function(a, b)
return a.value < b.value
end)
local result = {}
local nodes = {} --已经添加进去的点
local notAddNodes = { "A", "B", "C", "D", "E", "F", "G" }
local function checkNode(node)
for i, v in ipairs(nodes) do
if v == node then
return false
end
end
return true
end
local getNodeMinEdge = function(node)
for i, v in ipairs(graph) do
if v.node[1] == node or v.node[2] == node then
local anotherNode
if v.node[1] == node then
anotherNode = v.node[2]
else
anotherNode = v.node[1]
end
if checkNode(anotherNode) then
return anotherNode, v
end
end
end
return nil, nil
end
local getTheMinEdge = function()
local edges = {}
for i, v in ipairs(nodes) do
local anotherNode,nodeData = getNodeMinEdge(v)
if anotherNode then
table.insert(edges, {anotherNode,nodeData})
end
end
table.sort(edges,function (a,b)
return a[2].value < b[2].value
end)
return edges[1][1],edges[1][2]
end
local removeAddNodes = function(node)
for i, v in ipairs(notAddNodes) do
if v == node then
table.remove(notAddNodes, i)
break
end
end
end
---@param graph graph
local function minTree(graph)
table.insert(nodes, "A")
removeAddNodes("A")
while #notAddNodes > 0 do
local node, nodeData = getTheMinEdge()
table.insert(result, nodeData)
table.insert(nodes, node)
removeAddNodes(node)
end
end
minTree(graph)
