理想的なデータから抜け出し、グラフ-1を巡ります.DFS

グラフィックとグラフィックの巡回

私がよく知っているグラフは、水平軸に垂直な値を表すことで、データ間の相関を直感的に表す方法です.物理の授業でもよく描いたものです.しかし、私が学界を離れたとき、新しい意味が含まれていたようです.話をしないで現れる見知らぬ感覚と、手で解決すると、何でもない問題に対する認識が違和感を覚え、大きな悩みに陥る.彼はいったいなぜ登場するのか
実際、数学者と工学者の考えはあまりにも明らかだ.これは問題を効果的に解決するために導入されたと思います.効用に対する理解は次の問題です.実際、物理学と数学の資料は絶対的または理想的な環境での観測が多い.資料の構造形式にも相当します.これは,従来の線形構造を解決するアルゴリズムから脱し,より現実に近い方法で問題を解決する方法である.現実の問題に近づいても、数学は数学だ.連続的で固定されていない構造であっても、データ化のために頂点とエッジの重み付けによって問題と解決値を得ることができます.

グラフループ

図の遍歴は、所定の条件に従って図の各頂点にアクセスする方法であり、問題を解決する方法である.すべての接続の頂点にアクセスする探究方式であるため,与えられた資料が以下のようなグラフィック形式で提示される場合に推奨されるアルゴリズムである.

このようなグラフでは、直感的に結果を出すのは難しいが、コンピュータは主観的に聞こえる.グラフィックのプログラミングが正しく解釈されていない場合は、1の位置を2の左側に移動するだけで、まったく異なる値が導出される可能性があります.つまり、最終的にパソコンを借りたい人は、パソコンの言語でお願いするしかありません.グラフも次のように表現して伝える必要があります.

隣接マトリクス形式

上のグラフは、私たちとコンピュータの言語の間の表現方法です.縦軸の数字(頂点)から横軸の数字に変わる場合は1、不連続の場合は0となります.パソコンに伝える場合は、2次元配列で伝えるのが有効です.

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

隣接リスト形式
隣接マトリクスの形状は容易に実現できるが,スタックキューとハッシュテーブルの関係のように容易にナビゲートできない.従って、より効果的に近づけるためには、ディックシェリー形態を利用した隣接リストとして表現することが望ましい.

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

グラフィックループ

わけのわからないことですが、勉強の仕方は大体2つあると思います.一つの分野を深く研究し,高度な知識を得ることを目標とし,その過程で得られた知識を周囲の関連分野に拡張する方法.そして,各分野を探索し,共通の原理と哲学を導き出し,最終的に深い知識に達する方法である.この方法論は,業務処理方式や有効な運動法のように直感的な二分化を行うことができる.
グラフを探索する方法も同じです.始点から最も遠い頂点に到達することを繰り返し、探索に近い頂点から探索を開始する方法がある.前者を深さ優先探索(DFS)と呼び,後者を広さ優先探索(BFS)と呼ぶ.

DFS実装

これからDFS方式のアルゴリズムをPython関数として実現する.方式は大体2種類ある.1つは再帰関数構造であり,もう1つはスタックを利用した繰返し構造である.

再帰関数構造におけるDFS関数

# 처음 인자값으로 넣어줄 visited 선언. 순회한 정점을 받는 리스트.
# 함수 안에 선언 시 초기화 되므로 전역변수로 선언
visited = []

# 함수선언
def dfs_recursive(node, visited)
    # 함수의 인자로 받은 정점은 visited에 추가
    visited.append(node)
    
    # 정점이 가리키는 모든 점을 순회
    for adj in graph[node]:
        # 만약 순회하려는 점이 visited안에 없다면(방문한 적이 없다면)
        if adj not in visited:
            # 순회하려는 점을 인자값으로 함수 재실행(더 깊숙히 탐색)
            dfs_recursive(adj, visited)
    # 함수 정점이 가리키는 모든 값을 순회하면 visited 값 반환
    return visited    

再帰関数を用いたDFS関数.再帰関数は、「関数f=>結果値」の構造において、結果値で実行される関数f自体が再実行される関数である.再帰関数を作成するには、繰り返し返される値と終了条件の設定が重要です.上記の関数では、重複する値はdfs recursive(adj、アクセス済み)とreturnアクセスであり、終了条件はif adj not inがアクセスに合致しない、すなわちすべての巡回点がアクセスに含まれる.
結論から言えば,これはフィボナッチ数列のように戻り値自体の累積時の再帰関数があるわけではない.ただし、関数を実行するたびに、アクセスは目的に応じて更新されるため、最終的に返されるアクセス値には返されるすべての結果が含まれます.

実行シーケンステーブル(dfs recursive()=d r()

スタックの重複構造を持つDFS関数

# 함수선언
def dfs_stack(start):
    # visited 선언, 순회한 정점 저장
    visited = []
    # 인자값으로 넣은 시작점(start)를 리스트에 넣어 스택에 저장
    stack = [start]
    
    # 파이썬의 falsy값에는 0, "", False, None 뿐만 아니라 [],{},()같은 빈 자료형도 포함된다.
    # stack이 참일 경우는 스택 안에 요소가 존재하는 경우다.
    while stack :
        # top 변수로 stack에서 pop한 값을 저장하고 visited에 저장
        top = stack.pop()
        visited.append(top)
        
        # graph에서 top을 키 값으로 밸류(리스트)값 조회 후 순회
        for adj in graph[top]
            # 만약 adj 값이 visited에 저장되지 않은 경우, stack에 차례로 저장.
            if adj not in visited:
                stack.append(adj)
                
    # while문 종료시, visited 반환
    return visited

スタック構造のDFS関数を使用します.コアはスタックに順番に格納され,後入先出を行うため,アクセス値の頂点に直接接続するよりも,新しく得られた頂点も先に巡回する.したがって,同様に深さ優先の探索が行われる.

実行順序テーブル

の最後の部分

私たちの国の话では知っています.
続いてグラフ巡回-2。BFS