[JS-DSAA]17図

グラフィック:オブジェクト間の接続を表すビジュアル化されたデータ構造
グラフは、オブジェクト間のつながりや関係を多様に表す資料構造です.
グラフィックアルゴリズム(巡回、検索、ソートなど)により、2つのグラフィックノード間の最短パス検索などの問題を解決できます.
グラフを用いた事例は多く,代表的なものはウェブサイト,地図,回路,ソーシャルメディア,電話などである.

적용 사례   | 항목       | 연결
-------------------------------
웹사이트    | 웹페이지    | 링크
지도       | 교차로     | 도로
회로       | 부품      | 배선
소셜미디어   | 사람      | 친구 맺기
전화       | 전화번호    | 전화선

グラフィックの基本概念

頂点:グラフィックノード.視覚マークは円で表示されます.

幹線エッジ:グラフィックノード間の接続.視覚的にマークするときは線で表現します.

頂点数:ノードに接続されている幹線の数.

疎図:接続可能ノードの一部のみが幹線に存在する場合、この図を疎図と呼ぶ.

密集図:ノード間の接続が多い場合、この図を密集図と呼びます.

ループ図:1つのノードからそのノード経路を返す指向性図をループ図と呼ぶ.

重み付け:幹線の値.文脈によっていろいろなものを表すことができます.

1.方向図なし

方向図なし方向図なし:ノード間の幹線に方向図がない.
無方向図では、幹線は2つのノード間の相互接続を表し、重み付けされているが方向を持たない.
無方向図は、隣接行列(隣接行列)と隣接リスト(隣接リスト)でクラスとして表すことができる.
隣接マトリクスは、2つのノード間に接続があるかどうかを示す数独のように表示されます.
隣接リストはノードをキーとし,そのノードの隣接をリスト形式で格納する.

2.指向性図形

指向性図形有向図:ノード間の幹線に方向性のある図形.

3.巡視グラフ

1)優先検索幅

幅優先探索BFS、幅優先探索:ルートノードからの高さ(ステップ)で探索するアルゴリズム
幅優先探索は、バイナリ探索ツリーのシーケンス優先順位と同様に、ルートノードからの高さ単位で探索される.
幅優先検索を実現するために、キュー資料構造を使用します.
ルートノードから各ノードに接続されたノードをキューに追加し、キュー内の各エントリにアクセスして検索します.

2）優先探索深度

深度優先検索DFS,depth-first search:ルートノードから接続を深くしてループする検索アルゴリズム.
深度優先検索は、ツリーの下位レベルの順序に似ています.
ルートノードから接続されたノードを深く掘り下げます.これは再帰コードで実現できます.

4.ウェイト付きグラフィックと最短パス

1）重み付け幹線を有する図形

幹線に権限値を割り当てて情報を表示できます.また、グラフ上では、幹線の長さは幹線の重量に関係ありません.
たとえば、地図を表すグラフでは、距離(重み付け値)に関係なく指定された幹線の長さの重み付け値として距離(距離)を表すことができます.
重みのある幹線図では、ノード間の「最短パスは何ですか」が最も重要です.
図の最短パスアルゴリズムには多くの種類があるが,今回はマルチアウトプットアルゴリズムについて理解する.

2）マルチアウトレットのアルゴリズム：最短パス

マルチアウトアルゴリズムDijkstra'sアルゴリズム:目的地を達成するために、各段階で最短経路で動作する.

マルチ出口ステップ1:無限タグ距離(一部のノードに到達できない可能性がある)

ステップ

マルチ出口2:各ループにおいて各ノードについて最短経路

を選択する.
ステップ

マルチ出口3:すべてのノードの最短パス

を選択する.

5.位相整列

指向性図を適用する場合は、まずどのノードを処理すべきかを知る必要があります.
たとえば、タスクスケジューラでは、1つのタスクが前のタスクを実行するかどうかの影響を受けます.また、importを実行するときに、JavaScript依存マネージャなど、事前にインポートする必要があるライブラリについても理解する必要があります.
位相ソートアルゴリズムは深さ優先ソートアルゴリズムであり,記録順序により上記機能を実現できる.このアルゴリズムは、あるノードから深さ優先ソートを実行することによって、ノードに関連付けられたすべてのノードに再帰的にアクセスし、これらのノードをスタックに追加します.再帰呼び出しの終了時に現在のノード値をスタックに追加することで、時間順序が保証されます.
このアルゴリズムがどこで使えるのかよく分からないので、今回はあまり理解できません.もともとこのようなアルゴリズムがあったことを知り,後で論理や設計構造を記述する際にもこのようなアルゴリズムを考慮しなければならない.