用 NetworkX 探索 Python 中的圖演算法

---

在本教程中，我們將探討 NetworkX 庫中可用的用於 Python 的強大圖演算法。NetworkX 是一個備受廣泛使用的程式包，用於建立、操作和研究複雜網路的結構、動態和功能。它提供了用於處理圖表的廣泛演算法和函式，使其成為分析和視覺化各個領域中資料的一個出色選擇。

在本文中，我們將介紹幾種圖演算法以及它們使用 NetworkX 的實現。我們將從瞭解圖的基本知識以及如何使用 NetworkX 建立和操作它們開始。然後，我們將深入研究各種演算法，例如廣度優先搜尋、深度優先搜尋、最短路徑演算法和中心度量。在本教程結束時，你將對如何利用 NetworkX 來分析和解決現實世界的圖問題有一個全面的瞭解。

建立和操作圖

透過使用以下命令，讓我們開始安裝 NetworkX

pip install networkx

要建立一個新圖，我們可以簡單地匯入 NetworkX 庫並例項化一個圖物件，如下所示

import networkx as nx

# Create an empty graph
G = nx.Graph()

我們可以分別使用 `add_node()` 和 `add_edge()` 方法向圖中新增節點和邊。例如

# Add nodes
G.add_node(1)
G.add_node(2)
G.add_node(3)

# Add edges
G.add_edge(1, 2)
G.add_edge(2, 3)
G.add_edge(3, 1)

NetworkX 提供了各種操作和視覺化圖的方法。我們可以訪問圖的節點和邊，計算基本圖屬性，甚至使用內建視覺化函式繪製圖。

演算法 1：廣度優先搜尋 (BFS)

廣度優先搜尋演算法用於按廣度遍歷圖。它從給定的源節點開始，在繼續其鄰居之前，探索它的所有鄰居。此演算法可用於查詢兩個節點之間的最短路徑、確定圖的連通性等等。

接下來詳細瞭解如何使用 NetworkX 執行廣度優先搜尋

# Perform breadth-first search
bfs_tree = nx.bfs_tree(G, source=1)

# Print the nodes in the BFS tree
print("BFS tree nodes:", list(bfs_tree.nodes()))

在上述程式碼中，我們使用 `bfs_tree()` 函式執行從標記為 1 的節點開始的廣度優先搜尋。最終的 `bfs_tree` 是一個新的圖物件，其中僅包含廣度優先搜尋中訪問的節點和邊。然後，可以使用 `nodes()` 方法訪問 BFS 樹的節點。

輸出

BFS tree nodes: [1, 2, 3]

如你所見，從節點 1 開始的廣度優先搜尋以該順序訪問了節點 2 和 3。

演算法 2：深度優先搜尋 (DFS)

深度優先搜尋演算法透過在回溯之前儘可能訪問每條支路以探索圖。它從給定的源節點開始，儘可能深入地沿每條支路探索，並且僅在沒有更多未探索節點時才會回溯。

若要使用 NetworkX 執行深度優先搜尋，我們可以使用 `dfs_tree()` 函式

# Perform depth-first search
dfs_tree = nx.dfs_tree(G, source=1)

# Print the nodes in the DFS tree
print("DFS tree nodes:", list(dfs_tree.nodes()))

在上述程式碼中，我們使用 `dfs_tree()` 函式執行從標記為 1 的節點開始的深度優先搜尋。最終的 `dfs_tree` 是一個新的圖物件，表示深度優先搜尋期間形成的樹。可以使用 `nodes()` 方法訪問 DFS 樹的節點。

輸出

DFS tree nodes: [1, 3, 2]

如你所見，從節點 1 開始的深度優先搜尋以該順序訪問了節點 3 和 2。

演算法 3：最短路徑

找到圖中兩個節點之間的最短路徑是圖論中的常見問題。NetworkX 提供了幾種演算法來計算最短路徑，包括 Dijkstra 演算法和 A* 演算法。

使用 Dijkstra 演算法查詢圖中兩個節點之間最短路徑示例如下

# Find the shortest path using Dijkstra's algorithm
shortest_path = nx.shortest_path(G, source=1, target=3)

# Print the shortest path
print("Shortest path:", shortest_path)

在上述程式碼中，我們使用 `shortest_path()` 函式使用 Dijkstra 演算法在節點 1 和 3 之間查詢最短路徑。最終的 `shortest_path` 是表示從源到目標節點路徑的節點列表。

輸出

Shortest path: [1, 3]

如你所見，在我們的圖中，節點 1 和 3 之間的最短路徑是從節點 1 到節點 3 的直接邊。

演算法 4：中心度量

圖論中的中心度量用於確定圖中節點的相對重要性。NetworkX 提供了幾種中心度量，如度中心度、介數中心度和接近中心度。

計算我們圖的度中心度

# Compute degree centrality
degree_centrality = nx.degree_centrality(G)

# Print the degree centrality for each node
for node, centrality in degree_centrality.items():
    print(f"Degree centrality of node {node}: {centrality}")

在上述程式碼中，我們使用 `degree_centrality()` 函式計算圖中每個節點的度中心度。最終的 `degree_centrality` 是一個字典，其中鍵是節點，值是其度中心度得分。

輸出

Degree centrality of node 1: 0.6666666666666666
Degree centrality of node 2: 0.6666666666666666
Degree centrality of node 3: 0.6666666666666666

如你所見，由於鄰節點數相同，我們圖中的所有節點均具有相同的度中心度。

結論

在本教程中，我們探索了 NetworkX 的功能，NetworkX 是用於圖分析的強大 Python 庫。我們瞭解瞭如何建立和操作圖，並且我們已詳細瞭解各種圖演算法，如廣度優先搜尋、深度優先搜尋、最短路徑演算法和中心度量。利用 NetworkX 提供的功能，你可以以簡單有效的方式解決複雜的圖相關問題。