DFS実装のためのデータ構造。

スタック。

オーバーフロー:データ構造にデータサイズが埋め込まれている場合に挿入演算を実行するときに発生します.
≪バックフロー|Backflow|emdw≫:データが含まれていない場合に削除操作が実行される場合に発生します.
スタックとは?
先入後出構造または後入先出構造とは.
Pythonの場合、個別のライブラリを使用する必要はありません.append()とpop()を使用して動作は同じです.

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack)
print(stack[::-1])

富貴。

は、自分の関数を再呼び出しすることを示す.

再帰呼び出しの実行中にエラーが発生します.<1000回制限.>
RecursionError: maximum recursion depth exceeded while calling a Python object
この場合、sys.setrecursionlimit(number)復帰回数の提出が可能である.

重要な点:終了条件を明確にしなければならない.(ベースケースが重要です.)

工場が復帰する.

def factorial(N):
    if N <= 1:
        return 1
    return N * factorial(N - 1)

再帰的には点火式がよく用いられるが,これは後でDPに向かう重要な点である.

DFS

深さ優先探索.(図形の深部を優先的にブラウズ)

隣接マトリクス:2 D配列内のグラフィックの接続関係を表します.(すべてのノードの接続関係が表示されます.)

INF = 999999999
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

利点:2つのノードが接続されているかどうかをすばやく決定します.
欠点:不要なメモリの浪費.(すべてのノードの接続関係を表す)
隣接リスト:接続ノードに関する情報append()のみがリストに表示されます.

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

graph[0].append((1, 7))
graph[0].append((2, 5))

graph[1].append((0, 7))

graph[2].append((0, 5))

利点:メモリの効率的な使用.
欠点:2つのノードの接続が遅いかどうかを確認します.

DFSの操作手順。

ナビゲーション開始ノードをスタックに挿入し、アクセス処理を行う.

スタックの最上位ノードにアクセスされていない隣接ノードがある場合、アクセス処理のためにスタックに格納される.
アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.

(2.)繰り返しのプロセス.

def DFS(graph, node, visit):
    visit[node] = True
    print(node, end=" ")

    for next_node in graph[node]:
        if not visit[next_node]:
            DFS(graph, next_node, visit)

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [5, 6],
    [3, 4],
]
visit = [False] * 6
DFS(graph, 1, visit)