圖的定義：由基本元素構(gòu)成（如點(diǎn)理盆、線段）
圖的構(gòu)成：
- 頂點(diǎn)Vertex（攜帶key蓝谨，value）
- 邊Edge：連接兩個頂點(diǎn)之間的線段垛玻，可以是有向或者無向
-
權(quán)重Weight：從一個頂點(diǎn)至另一個的頂點(diǎn)的代價（距離摹察、時間...)
圖G = （V，E）碧囊，E中每條邊e = (vx,vy,w)
image.png - 路徑：把邊依次連接起來的頂點(diǎn)序列
- 圈：首尾頂點(diǎn)相同的路徑树灶，若有向圖不存在任何圈稱為DAG
實(shí)現(xiàn)方法：
-
鄰接矩陣Adjacency Matrix
建立一個NxN矩陣，矩陣格子用來裝權(quán)重
image.png
優(yōu)點(diǎn)： 簡單易懂
缺點(diǎn)：稀疏矩陣糯而，很多格子沒有利用 -
鄰接列表 Adjacency List
建立一個包含所有頂點(diǎn)的列表破托，每個頂點(diǎn)包含與各個頂點(diǎn)的連接及權(quán)重信息
image.png
實(shí)現(xiàn)代碼如下：
class Vertex:
def __init__(self, key):
self.id = key
self.connectedTo = {}
def addNeigbor(self, nbr, weight=0):
self.connectedTo[nbr] = weight
def __str__(self):
return str(self.id) + 'connect to' + str([i.id for i in self.connectedTo])
def getConnection(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self, nbr):
return self.connectedTo[nbr]
class Graph:
def __init__(self):
self.vertList = {}
self.numvert = 0
# 添加頂點(diǎn)
def addvertex(self, key):
self.numvert += 1
newVertex = Vertex(key)
self.vertList[key] = newVertex
return newVertex
# 查看是否有該頂點(diǎn)
def getVertex(self, n):
if n in self.vertList:
return self.vertList[n]
else:
return None
def __contains__(self, item):
return item in self.vertList
# 添加頂點(diǎn)之間的線段
def addEdge(self, frompoint, endpoint, cost=0):
if frompoint not in self.vertList:
new_vertex = self.addvertex(frompoint)
if endpoint not in self.vertList:
new_vertex = self.addvertex(endpoint)
self.vertList[frompoint].addNeighbor(self.vertList[endpoint], cost)
# 返回頂點(diǎn)Key值列表
def getVertices(self):
return self.vertList.keys()
# 迭代返回頂點(diǎn)
def __iter__(self):
return iter(self.vertList.values())
