无向图-邻接表方式

【要看理论知识的，可以参考这边】

无向图的邻接链表实现

无向图的深度优先搜索和广度优先搜索

 漫画：图的 “最短路径” 问题

【lua实现】

 1 local Graph = {}
 2 Graph.__index = Graph
 3 
 4 ---无向图
 5 function Graph.new()
 6     local obj = {}
 7     setmetatable(obj, Graph)
 8 
 9     obj:ctor()
10     return obj
11 end
12 
13 function Graph:ctor()
14     self.adjacent = {}
15     self.edgeCount = 0
16     self.vertexList = {}
17 end
18 
19 function Graph:GetVertexCount()
20     return #self.vertexList
21 end
22 
23 function Graph:GetEdgeCount()
24     return self.edgeCount
25 end
26 
27 function Graph: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     else
34         --顶点已存在
35     end
36 end
37 
38 function Graph:AddEdge(v1, v2)
39     local list1 = self.adjacent[v1]
40     local list2 = self.adjacent[v2]
41     if nil == list1 or nil == list2 then
42         return --顶点不存在
43     end
44 
45     table.insert(list1, v2) --最好判断下在list中是否已存在
46     table.insert(list2, v1)
47     self.edgeCount = self.edgeCount + 1
48 end
49 
50 function Graph:GetAdjacent(v)
51     return self.adjacent[v]
52 end
53 
54 function Graph:__tostring()
55     print("-----Graph")
56     for i=1,#self.vertexList do
57         local v = self.vertexList[i]
58         local adjList = self.adjacent[v]
59         print(v, "-->", table.concat(adjList, ", "))
60     end
61     print("-----")
62 end

 1 function CreateGraph()
 2     local g = Graph.new()
 3     g:AddVertex("A")
 4     g:AddVertex("B")
 5     g:AddVertex("C")
 6     g:AddVertex("D")
 7     g:AddVertex("E")
 8     g:AddVertex("F")
 9     g:AddVertex("G")
10 
11     g:AddEdge("A", "B")
12     g:AddEdge("A", "C")
13     g:AddEdge("B", "D")
14     g:AddEdge("B", "E")
15     g:AddEdge("C", "D")
16     g:AddEdge("C", "F")
17     g:AddEdge("D", "E")
18     g:AddEdge("D", "F")
19     g:AddEdge("E", "G")
20     g:AddEdge("F", "G")
21 
22     print("v ct: ", g:GetVertexCount())
23     print("edge ct:", g:GetEdgeCount())
24     tostring(g)
25     return g
26 end

上面的代码会创建出这样一张图

【深度优先搜索】

# 这边使用了递归来实现

# 用途：会把某个点的所有可达顶点都走一遍，即可以通过它来确定两个点之间是否可达

 1 function TestDfs1()
 2     local visited = {}
 3 
 4     function Dfs1(g, vertex)
 5         print(vertex)
 6 
 7         visited[vertex] = true
 8         local list = g:GetAdjacent(vertex)
 9         for i=1,#list do
10             local adjV = list[i]
11             if not visited[adjV] then
12                 Dfs1(g, adjV)
13             end
14         end
15     end
16 
17     local g = CreateGraph()
18     Dfs1(g, "A")
19 end
20 TestDfs1()

【广度优先搜索】

# 一般会借助一个队列来实现

# 用途1：会把某个点的所有可达顶点都走一遍，即可以知道两个点之间是否可达

# 用途2：可以算出点A到点B的最短路径 

 1 function TestBfs1()
 2     local edgeFrom = {}
 3 
 4     function Bfs1(g, vertex)
 5         local visited = {}
 6         local queue = {}
 7         visited[vertex] = true --加入queue就要设为visited
 8         table.insert(queue, vertex)
 9 
10         while #queue > 0 do
11             local v = queue[1]
12             print("---", table.concat(queue, ", "))
13             print(v)
14             table.remove(queue, 1)
15 
16             local list = g:GetAdjacent(v)
17             for i=1,#list do
18                 local adjV = list[i]
19                 if not visited[adjV] then
20                     visited[adjV] = true --加入queue就要设为visited
21                     edgeFrom[adjV] = v
22                     table.insert(queue, adjV)
23                 end
24             end
25         end
26     end
27 
28     local g = CreateGraph()
29     Bfs1(g, "A")
30 
31     local path = {}
32     local target = "G"
33     local start = "A"
34     local v = target
35     while v ~= start do
36         table.insert(path, v)
37         v = edgeFrom[v]
38     end
39     table.insert(path, v)
40     print("shortest path: ", table.concat(path))
41 end
42 TestBfs1()