グラフ理論の簡単な例 NetworkX

問題

以下のグラフにおいて、頂点Aと頂点Eの間にパスが存在するかどうかを判定してください。

  A --- B --- C
  |     |     |
  |     |     |
  D --- E --- F

解法・ソースコード

この問題を解くためには、以下の手順に従います。

  1. NetworkXを用いてグラフを作成します。
1
2
3
4
5
import networkx as nx

G = nx.Graph()

G.add_edges_from([('A', 'B'), ('A', 'D'), ('B', 'C'), ('B', 'E'), ('C', 'F'), ('D', 'E'), ('E', 'F')])
  1. 頂点Aと頂点Eの間にパスが存在するかどうかを判定します。

NetworkXのhas_path関数を使います。

1
2
3
4
if nx.has_path(G, 'A', 'E'):
    print("頂点Aと頂点Eの間にパスが存在します。")
else:
    print("頂点Aと頂点Eの間にパスは存在しません。")

実行結果は、「頂点Aと頂点Eの間にパスが存在します。」となります。

以上の手順で、グラフにおいて2つの頂点間にパスが存在するかどうかを判定することができました。