python 2パターンにおけるDFSループと再帰関数の考察
4930 ワード
グラフ#グラフ#
定点と幹線の巡回
ハミルトンパス:すべての頂点に1回アクセス(ダレストラ、クルーズ、フリーム)
BFS:「幅優先検索」(Breadth First Search)キューを使用して実装します.再帰の道は実現できない.
DFSで実装されたグラフィック
下の図
ディクシャナリーで以下のように表現されています.
graph = {
1 : [2, 3, 4],
2 : [5],
3 : [5],
4 : [],
5 : [6, 7],
6 : [],
7 : []
}
1.スタックおよびwhile pop構文を使用して実装されるDFSreturn -> [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. 再帰関数の特徴とその特徴を利用したアルゴリズム構想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
Reference
この問題について(python 2パターンにおけるDFSループと再帰関数の考察), 我々は、より多くの情報をここで見つけました https://velog.io/@clayryu328/python2-그래프-DFSBFS-재귀와-스택-그리고-반복テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol