スタックとキュー、再帰関数はDFS/BFSの中で最も重要な概念であり、学習する前にもう一度熟知してほしい.

グラフィック(Graph)

知る前に、グラフで基本構造を理解してみましょう.

グラフ＃グラフ＃

グラフィック構造:

1.ノード:
ノードは頂点(Vertex)とも呼ばれます.
2.幹線

グラフィックナビゲーションとは

1つのノードから複数のノードにアクセスします.
プログラミングでは、図形は大きく2つに表現されています

1.隣接行列:図形の接続関係を2次元配列で表す。

各ノード接続のシェイプを2 Dアレイに記録します.

INF = 999999

graph =[
[0,1,0,0],
[0,0,1,0],
[1,0,0,1],
[1,1,0,0]
]

print(graph)

結果:

[[0, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 1], [1, 1, 0, 0]]

2.隣接リスト：グラフの接続関係をリストで表す方式。

graph = [[] for _ in range(4)]

graph[1].append((2, 7))
graph[2].append((3, 2))
graph[3].append((2, 4))
graph[3].append((1, 4))

print(graph)

結果

[[], [(2, 7)], [(3, 2)], [(2, 4), (1, 4)]]

2つの方法の違い:

メモリの面では,隣接マトリクスを必要としない関係も格納され,メモリが浪費される.
逆に,隣接テーブルは接続された情報のみを格納するので記憶効率は高いが,隣接テーブルは隣接マトリクス方式に比べて特定の2つのノードが接続されているか否かの情報を取得する速度が遅い.隣接するリストは、関連するリストを1つずつチェックする必要があるからです.
ノードに関連付けられたすべての隣接ノードを巡回します.隣接リスト方式は隣接行力方式に比べてメモリスペースの無駄が少ない.