Python 中的圖資料結構
在程式設計中，圖資料結構表示一組相互關聯的物件。每個物件都稱為頂點，連結稱為邊。
上圖中，{A, B, C, D, E} 是頂點，集合用 V 符號表示。邊的集合用 E 表示，在上面的例子中它是 {ad,ac,ab,cd,bd,be,de}。
我們可以根據不同的標準對圖表進行分類。首先，我們有基於方向的圖。
這些是無向圖和有向圖。在無向圖中，邊沒有方向。
這意味著邊 ab 與 ba 相同。對於每條邊都有方向或方向的有向圖則相反。
基於權重，我們有加權圖和非加權圖。加權圖有一些與邊相關的值。
還有一些特殊的圖，如樹、有向無環圖等。由於它們的非線性特性，圖在現實世界中有很多應用。
谷歌地圖在他們的交通系統中使用圖表，甚至 Facebook 也使用圖表來視覺化使用者及其朋友列表。
在本教程中，我們將討論用 Python 表示一個簡單的圖形。
在 Python 中使用鄰接表實現圖
鄰接列表儲存每個頂點及其相鄰頂點以視覺化圖形。這可以使用字典來表示。
每個頂點都將是字典的鍵，鍵的對應值將包含列表中的相鄰頂點。
adjacency_lst = {}
mylst = []
def graph_node(node):
if node not in mylst:
mylst.append(node)
else:
print("The given node exists")
def graph_edge(node1, node2):
temp = []
if node1 in mylst and node2 in mylst:
if node1 not in adjacency_lst:
temp.append(node2)
adjacency_lst[node1] = temp
elif node1 in adjacency_lst:
temp.extend(adjacency_lst[node1])
temp.append(node2)
adjacency_lst[node1] = temp
else:
print("The given node does not exist")
def disp_graph():
for node in adjacency_lst:
print(node, " -> ", [i for i in adjacency_lst[node]])
graph_node("a")
graph_node("b")
graph_node("c")
graph_node("d")
graph_edge("a", "b")
graph_edge("b", "c")
graph_edge("c", "d")
graph_edge("d", "a")
disp_graph()
print(adjacency_lst)
輸出：
a -> ['b']
b -> ['c']
c -> ['d']
d -> ['a']
{'a': ['b'], 'b': ['c'], 'c': ['d'], 'd': ['a']}
我們使用上面例子中的鄰接表來實現一個簡單的圖。一開始，定義了 adjacency_lst 字典來儲存節點和邊。
graph_node() 函式將一個頂點新增到該字典並檢查一個節點是否已經存在。我們使用 graph_edge() 函式新增邊。
disp_graph() 函式通過顯示節點的邊緣來顯示此圖。
在 Python 中使用鄰接矩陣實現圖
我們可以使用矩陣來表示圖。矩陣是二維陣列。
在鄰接矩陣中，特定行和列的值表示是否存在邊。
如果 A[i][j] 為 0，則 i 和 j 之間沒有邊。值為 1 表示邊緣存在。
def graph_node(v):
global graph
global nodes_no
global nodes
if v in nodes:
print("Node already exists")
else:
nodes_no = nodes_no + 1
nodes.append(v)
if nodes_no > 1:
for vertex in graph:
vertex.append(0)
temp = []
for i in range(nodes_no):
temp.append(0)
graph.append(temp)
def graph_edge(v1, v2, e):
global graph
global nodes_no
global nodes
if v1 not in nodes:
print("Node ", v1, " does not exist.")
elif v2 not in nodes:
print("Node ", v2, " does not exist.")
else:
index1 = nodes.index(v1)
index2 = nodes.index(v2)
graph[index1][index2] = e
def disp_graph():
global graph
global nodes_no
for i in range(nodes_no):
for j in range(nodes_no):
if graph[i][j] != 0:
print(nodes[i], " -> ", nodes[j], "Weight for the edge: ", graph[i][j])
nodes = []
nodes_no = 0
graph = []
graph_node(1)
graph_node(2)
graph_node(3)
graph_node(4)
graph_edge(1, 2, 1)
graph_edge(1, 3, 1)
graph_edge(2, 3, 0)
graph_edge(3, 1, 2)
disp_graph()
print("Matrix Representation: ", graph)
輸出：
1 -> 2 Weight for the edge: 1
1 -> 3 Weight for the edge: 1
3 -> 1 Weight for the edge: 2
Matrix Representation: [[0, 1, 1, 0], [0, 0, 0, 0], [2, 0, 0, 0], [0, 0, 0, 0]]
在上面的例子中，我們使用鄰接矩陣實現了一個圖。我們維護圖是一個名為 graph 的列表列表。
graph_node() 函式向圖中新增一個頂點，並新增頂點之間的邊。
使用 graph_edge() 函式。disp_graph() 顯示矩陣中節點和邊的表示。
Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.
LinkedIn