必要な資料構造の基礎

ナビゲーションとは

これは、大量のデータから必要なデータを検索するプロセスを意味します.
プログラミングにおけるグラフィック,ツリーなどの資料構造における探索に関する問題
代表的なナビゲーションアルゴリズムを使用してDFS/BFSを正しく理解するには、まず基本データ構造スタックとキューを理解する必要があります.
スタックとキューを使用する場合は、挿入と削除に加えて、オーバーフローとバックフローも考慮されます.
オーバーフローは、あるデータ構造が格納できるデータのサイズが満たされている場合に発生します.逆に,資料構造なしで削除しようとすると,バックフローが発生する.

スタック

スタックはFILOまたはLIFO、すなわち先入後出、後入先出構造である.
stack.append() stack.pop()などの方法を実現できる.

キュー

Qは先入先出のFIFO構造である.
collections import deque#collectionsモジュールからdequeデータ構造を使用する
queue = deque()
queue.append()#の末尾に返済を挿入
queue.Popleft()#削除して一番前の返済に戻る
queue.逆順()#
dequeueはスタックとキューの利点を採用し、データの挿入と削除速度はリストデータ型よりも効率的で簡単である.
ほとんどの符号化テストでは、collectionsモジュールなどの基本ライブラリを使用できます.
Dequeueオブジェクトをリストデータ型に変更する場合はlistメソッドを使用します.list(dequeue)

さいきかんすう

DFSとBFSを実現するには,その貴重さも理解しなければならない.

def recursive_function:
	print('재귀함수를 호출합니다.')
    recursive_function()

recursive_function()

このコードを実行すると、文字列「再帰関数の呼び出し」が無限に出力されます.
もちろん、Python Interferにはコール回数制限がありますが、この制限を超えると、
再帰誤差が発生する.
再帰関数は数学の授業で述べたフラクタル構造に似ている.

再帰関数の終了条件

def recursive_function(i):
	if i == 100:
    	return 
    print(i,'번째 재귀 함수에서',i+1,'번째 재귀함수를 호출합니다.')
    recursive_function(i+1)
    print(i,'번째 재귀 함수를 종료합니다.')

recursive_function(1)

再帰関数の実行にはスタックデータ構造が使用されます.
従って、スタックデータ構造を使用する必要がある多くのアルゴリズムは、再帰関数を用いて容易に実現することができる.DFSは典型的な例である.
再帰関数を用いた代表的な例には工場問題がある.
数学では0!第1課利用した値が1に等しい性質は,工場関数がnが1未満のときに関数を終了する再帰関数の形で実現できる.

#반복적으로 구현한 n!
def factorial_iterative(n):
	result = 1
    for i in range(1,n+1):
    	result *= i
    return result
#재귀적으로 구현한 n!
def factorial_recursive(n):
	if n <= 1:
    	return 1
    return n * factorial_recursive(n-1)

実行結果は同じであるが,再帰関数は再帰(点式)をソースコードに直接移行するため簡潔である.

ナビゲーションアルゴリズムDFS/BFS

DFS

DFSは深さ優先探索とも呼ばれ,グラフィックにおける深さ優先探索のアルゴリズムである.
グラフィックはノードと幹線を表し、ノードは頂点とも呼ばれます.
グラフィックブラウズとは、1つのノードから複数のノードにアクセスすることです.
プログラミングでは、グラフィックは2つの方法で表現することができ、符号化テストでは、この2つの方法が必要です.
隣接マトリクス:グラフィックの接続関係を2 D配列で表す
隣接リスト:グラフの接続関係をリストで表す方法
0120075170無限25無限0

隣接マトリクス方式:
これは,2次元配列における各ノードの接続の形態を記録する方式である.
上記の図形を隣接行列として表す場合、Pythonは2次元リストとして表すことができる.
接続されていないノード間の料金は無限です.
実際のコードでは,論理的に正しく答えられない大きな値のうち,9999999999,987654321等に初期化されることが多い.
このように隣接行列で図形を処理する場合、データの初期化は以下のようになる.

INF = 999999999 #무한의 비용 선언
#2차원 리스트를 이용해 인접행렬 표현
graph= [
	[0,7,5],
    	[7,0,INF],
    	[5,INF,0],
    ]
print(graph)

[[0,7,5],[7,0,999999999],[5,999999999,0]]
隣接リストでは、
「接続リスト」という名前の資料構造を使用して実現します.

#행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]
#노드 0에 연결된 노드정보 저장(노드,거리)
graph[0].append((1,7))
graph[0].append((2,5))
#노드 1에 연결된 노드정보저장(노드,거리)
graph[1].append((0,7))
graph[2].append((0,5))

print(graph)

[[(1,7),(2,5)],[(0,7)],[(0,5)]]
この2つの方法にはどんな違いがありますか?
メモリの観点から,隣接マトリクスはすべての関係を格納し,ノードが多ければ多いほどメモリが浪費される.
逆に,隣接リスト方式は接続された情報のみを格納するため,メモリを効率的に使用できる.
しかし,これらの属性のため,隣接リスト方式は隣接マトリクス方式に比べて,特定の2つのノードが接続されているか否かの情報を取得する速度が遅い.
隣接リスト方式では,接続されたデータを逐一確認するためである.
したがって、あるノードに関連付けられたすべての隣接ノードを巡回する必要がある場合、隣接リスト方式は隣接マトリクス方式に比べてメモリ空間の浪費が小さくなる.

DFS & BFS

DFSはスタック構造を採用し、具体的な操作過程は以下の通りである.
1.ナビゲーション開始ノードをスタックに挿入し、アクセス処理を行います.
2.スタックの最上位ノードに未アクセスの隣接ノードがある場合は、スタックに入れてアクセス処理を行います.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
3.再実行できなくなるまで2回目の手順を繰り返します.
ノード1を起動ノードに設定し、DFSを使用してナビゲートした場合、どうなりますか?
通常、ノードにアクセスされていないノードが複数ある場合は、番号の低い順序から処理を開始します.
DFSの機能を考慮すると、順序で処理することができるが、符号化テストは、番号の低い順序から処理を開始することを示すことが多い.
そこで、慣例に従って、番号の低い順から処理を開始する.
1.DFS

2.BFS

3.比較

DFSの例

def dfs(graph, v,visited):
#현재 노드를 방문 처리
    visited[v] = True
    print(v,end=' ')
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
           dfs(graph, i, visited)
#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [ 
	[], 
	[2,3,8],
    	[1,7],
    	[1,4,5],
    	[3,5],
    	[3,4],
   	 [7],
    	[2,6,8],
    	[1,7]
    ]
#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
#정의된 DFS 함수 호출
dfs(graph,1,visited)

BFS

BFSアルゴリズムは「幅優先探索」の意味を持つ.近接ノードから探索を開始するアルゴリズムである.DFSはできるだけ遠くのノードを優先的に閲覧するように動作するが,BFSは逆であるという.
BFSを実施する際には,先入先出のキュー資料構造を採用することが慣例である.
アルゴリズムを記述して、隣接ノードをキューに繰り返し入れます.

さぎょうモード

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

キューからノードを取り出し、そのノードの隣接ノードでは、アクセスされていないすべてのノードをキューに挿入してアクセス処理を行う.

プロセスを再実行できなくなるまで、手順

2を繰り返します.

from collections import deque
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
    	v = queue.popleft()
        print(v,end=' ')
        for i in graph[v]:
            if not visited[i]:
            	queue.append(i)
                visited[i] = True
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
	[], 
	[2,3,8],
    	[1,7],
    	[1,4,5],
    	[3,5],
    	[3,4],
   	 [7],
    	[2,6,8],
    	[1,7]
    ]
#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

#정의된 BFS 함수 호출
bfs(graph, 1, visited)

1 2 3 8 7 4 5 6
DFS BFSの実施をまとめる
DFSSBFS動作原理スタックキューの実装方法再利用可能なキューリソース構造を使用する