DFS

16340 ワード
python algorithm テキストリンク

DFS

  • は非線形構造のグラフィック構造であり、グラフィックで表されるすべてのデータを検索することが重要である.
  • の始点の一方向の経路の所在を深く探索し、これ以上行く場所がなければ、最後に出会った道路幹線を遮る頂点に戻り、別の方向の頂点に探索を続け、最終的にすべての頂点にアクセスする巡回方法
  • は最後に遭遇した分岐点の頂点を返し、深さ優先探索を再開し、後入先出構造のスタック
    • を用いる.

    アルゴリズム#アルゴリズム#


  • 頂点vへのアクセスを開始することにした.

  • 正犯vに隣接する頂点にあります.

  • 未アクセスの頂点wがある場合は、頂点vをスタックにプッシュして頂点wにアクセスする.
    そしてwをvとして、再び2回目を繰り返す.

  • 未アクセスの頂点がない場合は、スタックをポップアップして受信した最後のアクセス頂点をvに設定し、2番目を繰り返してナビゲーション方向を変更します.

  • スタックが空になるまで2)繰り返します.

    • DFSベース

    input_str = "1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7"


lst = list(map(int,input_str.split(", ")))
grid = [[0]*8 for _ in range(8)]
# 1
from collections import defaultdict

# 그래프 만들기
graph = defaultdict(list)
for i in range(0, len(lst), 2):
    a = lst[i]
    b = lst[i+1]


    
    grid[a][b] = 1
    grid[b][a] = 1

    graph[a].append(b)
    graph[b].append(a)
    
from pprint import pprint

# pprint(grid)
# pprint(graph)


stack = []
visited = []
print(i)

stack.append(1)
visited.append(1)

while stack:

    tmp = stack[-1]


    for node in range(1,8): # 7 : node의 개수 1 ~ 7
        if grid[tmp][node] == 1 and node not in visited:
            stack.append(node)
            visited.append(node)
            break
    else:
        stack.pop()


    # for value in graph[tmp]:
    #     if value not in visited:
    #         stack.append(value)
    #         visited.append(value)
    #         break
    # else:
    #     stack.pop()
    
print(visited)

    DFS再帰

    input_str = "1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7"


lst = list(map(int,input_str.split(", ")))



grid = [[0]*8 for _ in range(8)]
for i in range(0, len(lst), 2):
    a = lst[i]
    b = lst[i+1]    
    grid[a][b] = 1
    grid[b][a] = 1


from collections import defaultdict
graph = defaultdict(list)

for i in range(0, len(lst), 2):
    a = lst[i]
    b = lst[i+1]    
    graph[a].append(b)
    graph[b].append(a)
    
from pprint import pprint




stack = []
visited = []

stack.append(1)
visited.append(1)
cnt = 0
while stack:
    cnt += 1

    tmp = stack[-1]

    for node in graph[tmp]:
        if node not in visited:
            stack.append(node)
            visited.append(node)
            break
    else:
        stack.pop()
    
print(visited)
print(cnt)


visited = []

for i in range(0, len(lst), 2):
    a = lst[i]
    b = lst[i+1]    
    graph[a].append(b)
    graph[b].append(a)


def func(tmp):
    visited.append(tmp)
    for node in graph[tmp]:
        if node not in visited:
            # visited.append(node)
            func(node)

func(1)
print(visited)
    Heap
    Python文字列のフォーマット