Graph 的实现
2021-04-28
0. 前言
之前两篇讲了 Graph 的基本概念和两种理论上的实现方式，这篇就来讲一下具体是怎么实现的吧~ Time for some actual code!
回顾
我们需要一个 master list 来代表 graph，每个 node 都是一个 dictionary，里面包含跟其他 node 的联系以及 edge 的 weight。
所以我们要有两个 class，一个叫做 Graph，一个叫做 Node。
1. Code
Node Class
connectedTo 包含跟其他 node 的联系。
class Node:
def __init__(self,key):
self.id = key
self.connectedTo = {}
def addNeighbor(self,neighbourId,weight=0):
self.connectedTo[neighbourId] = weight
def __str__(self):
return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self,neighbourId):
return self.connectedTo[neighbourId]
Graph Class
- map node id to node object.
- keep track of number of nodes
class Graph:
def __init__(self):
self.nodeList = {}
self.numNodes = 0
def addNode(self,key):
self.numNodes = self.numNodes + 1
newNode = Node(key)
self.nodeList[key] = newNode
return newNode
def getNode(self,node):
if node in self.nodeList:
return self.nodeList[node]
else:
return None
def __contains__(self,node):
return node in self.nodeList
def addEdge(self,fromNode,toNode,weight=0):
if fromNode not in self.nodeList:
self.addNode(fromNode)
if toNode not in self.nodeList:
self.addNode(toNode)
self.nodeList[fromNode].addNeighbor(self.nodeList[toNode], weight)
def getNodes(self):
return self.nodeList.keys()
# iteration
def __iter__(self):
return iter(self.nodeList.values())
2. 使用
g = Graph()
for i in range(6):
g.addNode(i)
g.addEdge(0,1,5)
g.addEdge(0,5,2)
g.addEdge(1,2,4)
g.addEdge(2,3,9)
g.addEdge(3,4,7)
g.addEdge(3,5,3)
g.addEdge(4,0,1)
g.addEdge(5,4,8)
g.addEdge(5,2,1)
for v in g:
for w in v.getConnections():
print("( %s , %s )" % (v.getId(), w.getId()))