圖結構的實作python

#File Name : 圖結構的實作.py

# 設定節點類型
#圖中的度：所謂頂點的度(degree)，就是指和該頂點相關聯的邊數。
#在有向圖中，度又分為入度和出度。
#入度 (in-degree) ：以某頂點為弧頭，終止于該頂點的弧的數目稱為該頂點的入度。
#出度 (out-degree) ：以某頂點為弧尾，起始于該頂點的弧的數目稱為該頂點的出度。


class Node(object):
    def __init__(self,value=None):
        self.value = value #節點的值
        self.come = 0 #節點入度
        self.out = 0 #節點出度
        self.nexts = [] #節點的鄰居節點
        self.edges = [] #在節點為from的情況下，邊的集合
class Edge(object):
    def __init__(self,weight=None,fro,to):
        self.weight = weight # 邊的權重
        self.fro = fro # 邊的from節點
        self.to = to #邊的to節點
class Graph(object):
    def __init__(self):
        self.nodes = {} #圖所有節點的集合  字典形式 ：{節點編号：節點}
        self.edges = [] #圖的邊集合

def creatGraph(matrix):
    # 二維數組matrix [權重  從那個點的值  去哪個點的值]
    graph = Graph()
    # 建立所有節點
    for edge in matrix:
        weight = edge[0]
        fro = edge[1]
        to = edge[2]
        if fro not in graph.nodes:
            graph.nodes[fro] = Node(fro)
        if to not in graph.nodes:
            graph.nodes[to] = Node(to)
    #建立所有的邊
        fromNode = graph.nodes[fro]
        toNode = graph.nodes[to]
        newEdge = Edge(weight,fromNode,toNode)
        fromNode.nexts.append(toNode) #加上鄰居指向
        fromNode.out+=1 #出度+1
        toNode.come+=1 #to 的入度+1
        fromNode.edge.append(newEdge) #邊的集合+1
        graph.edges.append(newEdge)

    return graph