Luna Tech

Tutorials For Dummies.

Graph 的实现

2021-04-28


0. 前言

Reference: 8.6

之前两篇讲了 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

  1. map node id to node object.
  2. 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()))