python 2パターンにおけるDFSループと再帰関数の考察

グラフ＃グラフ＃

オブジェクトのいくつかの関連するオブジェクトの集合構造は、主に巡回および最短経路のアルゴリズムの資料構造を探すために使用される.

定点と幹線の巡回

化油器経路:幹線ごとに1回(ブラシ)
ハミルトンパス:すべての頂点に1回アクセス(ダレストラ、クルーズ、フリーム)

DFS:深度優先探索(Depth First Search)は、スタックまたは再帰的に実現され、バックグラウンド追跡によって優れた効果を表示します.
BFS:「幅優先検索」(Breadth First Search)キューを使用して実装します.再帰の道は実現できない.

backtracking:ソリューションの候補を決定した後、直ちに前の候補に戻り、不要な計算プロセスを低減するアルゴリズム

.

DFSで実装されたグラフィック

下の図

ディクシャナリーで以下のように表現されています.

graph = {
    1 : [2, 3, 4],
    2 : [5],
    3 : [5],
    4 : [],
    5 : [6, 7],
    6 : [],
    7 : []
    }

1.スタックおよびwhile pop構文を使用して実装されるDFS
return -> [1, 4, 3, 5, 7, 6, 2]

def DFS(graph, start_node):
    # 1개의 dict와 2개의 list
    need_visit, visited = list(), list()
    # 초기화
    need_visit.append(start_node)
    # while pop에서는 need_visit리스트의 원소들을 삭제하는 구조를 취한다. 
    #스택을 활용해서 쉽게 DFS를 구현할 수 있지만 
    #이 방식은 순회의 방향이 오른쪽 노드를 우선으로 탐색하게 된다.
    while need_visit:
        node = need_visit.pop()
        #그래프의 그림을 보며 따라가보면 쉽게 이해할 수 있다.
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])     
    return visited

2-1. 再帰関数の特徴とその特徴を利用したアルゴリズム構想

再帰関数を記述する場合、次の再帰関数をどの条件でロードするかを考慮する必要があります.また,アルゴリズムの最終結果値から関数に入る因子を考慮すると,これらの条件は自然に現れるようである.

再帰関数が必要な場合、まず問題が動的計画法またはDivideandConquenceによって解決できるかどうかを考慮する.また、問題がルートディレクトリにドリルする形式、すなわちDFS順序が要求される場合、listフォーマットを更新する再帰関数を使用することができます.

DFSに従って、ループノードの再帰関数を想定しようとする.大きなフレームワークでは、DFS/BFS巡回アルゴリズムの特徴「1図と2 list(アクセス、需要visit)」を考慮して、コードを書きたいと思います.

は、結果値がアクセスされたノードのリスト(アクセスされた)であることを優先する.したがって、関数はvistedです.append(ノード)が必要です.そうであれば、関数のパラメータでnodeとgraphを受信し、if node not in vistedを使用して関数をロードする条件を考慮することができます.

関数の実行順序が

であることを考慮すると、アクセスが更新され、for構文遍歴図[node]、すなわち値値値値を使用すると、再帰関数はスタック形式で演算されるため、DFS形式で正しく実行される.

が終了すると、list(アクセス済み)は関数のパラメータとして追加され、各関数に最新のlistがあることを確認する必要があります.

2-2. 再帰関数によるDFS
return -> [1, 2, 5, 6, 7, 3, 4]

def recursive_dfs(node, visited = []):
    visited.append(node)
    for visiting_node in graph[node]:
    	if visiting_node not in visited:
        	recursive_dfs(visiting_node, visited)
    return visited