Python 中的圖資料結構

Manav Narula 2023年1月30日 2022年5月17日
  1. 在 Python 中使用鄰接表實現圖
  2. 在 Python 中使用鄰接矩陣實現圖
Python 中的圖資料結構

在程式設計中,圖資料結構表示一組相互關聯的物件。每個物件都稱為頂點,連結稱為邊。

圖示例

上圖中,{A, B, C, D, E} 是頂點,集合用 V 符號表示。邊的集合用 E 表示,在上面的例子中它是 {ad,ac,ab,cd,bd,be,de}

我們可以根據不同的標準對圖表進行分類。首先,我們有基於方向的圖。

這些是無向圖和有向圖。在無向圖中,邊沒有方向。

這意味著邊 abba 相同。對於每條邊都有方向或方向的有向圖則相反。

基於權重,我們有加權圖和非加權圖。加權圖有一些與邊相關的值。

還有一些特殊的圖,如樹、有向無環圖等。由於它們的非線性特性,圖在現實世界中有很多應用。

谷歌地圖在他們的交通系統中使用圖表,甚至 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,則 ij 之間沒有邊。值為 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() 顯示矩陣中節點和邊的表示。

Author: Manav Narula
Manav Narula avatar Manav Narula avatar

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

相關文章 - Python Graph