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

加权无向图的数据结构

 

【lua实现】

 1 local WeightedGraph = {}
 2 WeightedGraph.__index = WeightedGraph
 3 
 4 function WeightedGraph.new()
 5     local obj = {}
 6     setmetatable(obj, WeightedGraph)
 7 
 8     obj:ctor()
 9     return obj
10 end
11 
12 function WeightedGraph:ctor()
13     self.adjacent = {}
14     self.vertexList = {}
15     self.edgeCount = 0
16 end
17 
18 function WeightedGraph:GetVertexCount()
19     return #self.vertexList
20 end
21 
22 function WeightedGraph:GetVertex(index)
23     return self.vertexList[index]
24 end
25 
26 function WeightedGraph:GetEdgeCount()
27     return self.edgeCount
28 end
29 
30 function WeightedGraph:AddVertex(v)
31     local list = self.adjacent[v]
32     if nil == list then
33         list = {}
34         self.adjacent[v] = list
35         table.insert(self.vertexList, v)
36     end
37 end
38 
39 function WeightedGraph:AddEdge(v1, v2, w)
40     local list1 = self.adjacent[v1]
41     local list2 = self.adjacent[v2]
42     if nil == list1 or nil == list2 then
43         return --顶点不存在
44     end
45     table.insert(list1, {v = v2, w = w})
46     table.insert(list2, {v = v1, w = w})
47     self.edgeCount = self.edgeCount + 1
48 end
49 
50 function WeightedGraph:GetAdjacent(v)
51     return self.adjacent[v]
52 end
53 
54 function WeightedGraph:__tostring()
55     print("-----WeightedGraph")
56     for i=1,#self.vertexList do
57         local v = self.vertexList[i]
58         local list = self.adjacent[v]
59         local strBuilder = {}
60         for j=1,#list do
61             local adjVInfo = list[j]
62             if j > 1 then
63                 table.insert(strBuilder, ",")
64             end
65             table.insert(strBuilder, "(")
66             table.insert(strBuilder, adjVInfo.v)
67             table.insert(strBuilder, ":")
68             table.insert(strBuilder, adjVInfo.w)
69             table.insert(strBuilder, ")")
70         end
71         print(v, "->", table.concat(strBuilder))
72     end
73     print("-----")
74 end

 

测试代码：

 1 function CreateGraph()
 2     local g = WeightedGraph.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     g:AddVertex("6")
10     g:AddVertex("7")
11 
12     g:AddEdge("1", "3", 0.29)
13     g:AddEdge("1", "5", 0.32)
14     g:AddEdge("1", "7", 0.19)
15     g:AddEdge("1", "2", 0.36)
16     g:AddEdge("5", "4", 0.35)
17     g:AddEdge("5", "7", 0.28)
18     g:AddEdge("7", "0", 0.16)
19     g:AddEdge("7", "2", 0.34)
20     g:AddEdge("4", "0", 0.38)
21     g:AddEdge("4", "6", 0.93)
22     g:AddEdge("0", "6", 0.58)
23     g:AddEdge("0", "2", 0.26)
24     g:AddEdge("2", "6", 0.4)
25     g:AddEdge("2", "3", 0.17)
26     g:AddEdge("3", "6", 0.52)
27 
28     print("v ct: ", g:GetVertexCount())
29     print("edge ct:", g:GetEdgeCount())
30     tostring(g)
31     return g
32 end
33 CreateGraph()

 

得到下面这样一张图：