[アルゴリズム]グラフ

グラフィックとは?

さまざまな定義がありますが、グラフィック理論のグラフィックとは、オブジェクトのいくつかの関連付けられたオブジェクトの集合構造を指します.ここでは、符号化テストでよく見られるグラフの順序について説明します.

グラフループ

「グラフィックツアーはグラフィックブラウズとも呼ばれ、グラフィックの各頂点にアクセスするプロセスです.」
図の順序は,深さ優先探索(Depth First Search,以下DFSと略す)と幅優先探索(Breadth First Search,以下BFSと略す)が大別されており,個別の分類が存在するため,そこで詳細に議論することにした.

グラフィックとツリー

要するに、グラフとツリーの違いは、次のとおりです.
ツリーは循環構造を持たないグラフです.
すなわち,図はツリーと比較して一般化概念ツリーのループ構造を持たない.

Python（Python）

Pythonの利点の1つは、複数のライブラリをサポートすることです.Pythonを比較符号化テストの言語として選んだ以上,Pythonの利点を積極的に利用すべきである.
コレクションのdefaultdict(list)を使用してグラフィックを整理するのが好きです.
グラフ問題でよく見られるアクセスタグは、時間に応じてリストやバーコードを適切に使用します.
次に例を示します.

from collections import defaultdict, deque
def solution(n, edges):
    # 그래프 구성
    graph = defaultdict(list)
    for edge in edges:
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
        
        # graph 출력결과 : defaultdict(<class 'list'>, {3: [6, 4, 2, 1], 6: [3], 4: [3, 2], 2: [3, 1, 4, 5], 1: [3, 2], 5: [2]})

プログラマハイスコアスイートの問題

最遠ノード(lv 3)

ランキング(lv 3)

部屋数(lv 5)

参考文献

朴相吉、『Pythonアルゴリズムインタビュー』、本だけ