【理论知识可以参考这边】
【lua实现】
1 local DGraph = {}
2 DGraph.__index = DGraph
3
4 function DGraph.new()
5 local obj = {}
6 setmetatable(obj, DGraph)
7
8 obj:ctor()
9 return obj
10 end
11
12 function DGraph:ctor()
13 self.adjacent = {}
14 self.edgeCount = 0
15
16 self.vertexList = {}
17 end
18
19 function DGraph:GetVertexCount()
20 return #self.vertexList
21 end
22
23 function DGraph:GetEdgeCount()
24 return self.edgeCount
25 end
26
27 function DGraph:AddVertex(v)
28 local list = self.adjacent[v]
29 if nil == list then
30 list = {}
31 self.adjacent[v] = list
32 table.insert(self.vertexList, v)
33 end
34 end
35
36 function DGraph:AddEdge(v1, v2)
37 local list1 = self.adjacent[v1]
38 local list2 = self.adjacent[v2]
39 if nil == list1 or nil == list2 then
40 --顶点不存在
41 return
42 end
43 table.insert(list1, v2)
44 end
45
46 function DGraph:__tostring()
47 print("-----DGraph")
48 for i=1,#self.vertexList do
49 local v = self.vertexList[i]
50 local list = self.adjacent[v]
51 print(v, "-->", table.concat(list, ", "))
52 end
53 print("-----")
54 end
测试代码
1 function CreateDGraph()
2 local g = DGraph.new()
3 g:AddVertex("0")
4 g:AddVertex("1")
5 g:AddVertex("2")
6 g:AddVertex("3")
7 g:AddVertex("4")
8 g:AddVertex("5")
9
10 g:AddEdge("0", "2")
11 g:AddEdge("2", "0")
12 g:AddEdge("2", "1")
13 g:AddEdge("2", "3")
14 g:AddEdge("3", "2")
15 g:AddEdge("3", "4")
16 g:AddEdge("3", "5")
17
18 print(g:GetEdgeCount())
19 print(g:GetVertexCount())
20 tostring(g)
21 end
22 CreateDGraph()
【深度优先搜索dfs和广度优先搜索bfs】
# dfs和bfs都可以知道是否可达
# dfs和bfs都可以获取两点之间的路径, 但bfs的路径是最短路径
1 local Dfs = {}
2 Dfs.__index = Dfs
3
4 function Dfs.new(g)
5 local obj = {}
6 setmetatable(obj, Dfs)
7
8 obj:ctor(g)
9 return obj
10 end
11
12 function Dfs:ctor(g)
13 if nil == g then
14 print("ctor g nil")
15 end
16 self.graph = g
17 self.startVertex = nil
18 self.visited = {}
19 self.visitFromMap = {} --通过目标点获取访问源点
20 end
21
22 ---到另一个点是否可达
23 function Dfs:IsReachable(endVertex)
24 return true == self.visited[endVertex]
25 end
26
27 ---遍历所有可达的顶点
28 function Dfs:VisitAllReachable(startVertex)
29 self.startVertex = startVertex
30 self.visited = {}
31 self.visitFromMap = {}
32
33 function dfs(v)
34 self.visited[v] = true
35
36 local list = self.graph:GetAdjacent(v)
37 for i=1,#list do
38 local adjV = list[i]
39 if not self.visited[adjV] then
40 self.visitFromMap[adjV] = v
41 dfs(adjV)
42 end
43 end
44 end
45
46 dfs(startVertex)
47 end
48
49 ---两个点之间的路径
50 function Dfs:GetPath(endVertex)
51 if not self:IsReachable(endVertex) then return nil end
52
53 local pathQueue = {}
54 --从目标点, 反向一步一步算出起点
55 local v = endVertex
56 while v ~= self.startVertex do
57 table.insert(pathQueue, 1, v)
58 v = self.visitFromMap[v]
59 end
60 table.insert(pathQueue, 1, v)
61 return pathQueue
62 end
测试代码
1 function TestDfs1()
2 local g = CreateDGraph()
3 local dfs = Dfs.new(g)
4 dfs:VisitAllReachable("3")
5 print(dfs:IsReachable("4"))
6 print(dfs:IsReachable("0"))
7 print(table.concat(dfs:GetPath("4"), "->"))
8 end
9 TestDfs1()
【广度优先搜索】
1 local Bfs = {}
2 Bfs.__index = Bfs
3
4 function Bfs.new(g)
5 local obj = {}
6 setmetatable(obj, Bfs)
7
8 obj:ctor(g)
9 return obj
10 end
11
12 function Bfs:ctor(g)
13 self.graph = g
14 self.startVertex = nil
15 self.visited = {}
16 self.visitFrom = {} --从哪个点访问的key对应的点
17 end
18
19 function Bfs:IsReachable(endVertex)
20 return true == self.visited[endVertex]
21 end
22
23 function Bfs:VisitAllReachable(startVertex)
24 self.startVertex = startVertex
25 self.visited = {}
26 self.visitFrom = {}
27
28 local queue = {}
29 self.visited[startVertex] = true
30 table.insert(queue, startVertex)
31
32 while #queue > 0 do
33 local v = queue[1]
34 table.remove(queue, 1)
35
36 local list = self.graph:GetAdjacent(v)
37 for i=1,#list do
38 local adjV = list[i]
39 if not self.visited[adjV] then
40 self.visitFrom[adjV] = v
41 self.visited[adjV] = true
42 table.insert(queue, adjV)
43 end
44 end
45 end
46 end
47
48 function Bfs:GetPath(endVertex)
49 if not self:IsReachable(endVertex) then return nil end
50
51 local pathQueue = {}
52 local v = endVertex
53 while v ~= self.startVertex do
54 table.insert(pathQueue, 1, v)
55 v = self.visitFrom[v]
56 end
57 table.insert(pathQueue, 1, v)
58 return pathQueue
59 end
测试代码
1 function CreateDGraph2()
2 local g = DGraph.new()
3 g:AddVertex("0")
4 g:AddVertex("1")
5 g:AddVertex("2")
6 g:AddVertex("3")
7 g:AddVertex("4")
8 g:AddVertex("5")
9
10 g:AddEdge("0", "2")
11 g:AddEdge("2", "0")
12 g:AddEdge("2", "1")
13 g:AddEdge("2", "3")
14 g:AddEdge("2", "5")
15 g:AddEdge("3", "2")
16 g:AddEdge("3", "4")
17 g:AddEdge("3", "5")
18
19 return g
20 end
21
22 function TestBfs1()
23 local g = CreateDGraph2()
24
25 local dfs = Bfs.new(g)
26 dfs:VisitAllReachable("0")
27 print(dfs:IsReachable("3"))
28 print(dfs:IsReachable("5"))
29 print(table.concat(dfs:GetPath("5"), "->"))
30 end
31 TestBfs1()