[CS]データ構造(Graph、Tree&BST)基礎日-26

Graph

複雑なネットワークは一般的にグラフィックと呼ばれ、数学で言うグラフィックではありません.
複数のポイント間の複雑な接続を表すデータ構造.直接関係がある場合は、2つの点の間に接続線があります.

Graphの使用例

ポータルサイトの検索エンジン、SNS上の人間関係、ナビゲーションで使用されるデータ構造はGraphです.この3つの頂点には多くの頂点があり、それらの関係は直線です.

幹線:接続された2つの頂点からデータが移動できることを示します.

データが相互に移動できない場合は、関係がないことを示します.

ex)コード

let isConnected = {
	seoul: {
    	busan: true,
        daegu: true
    },
    busan: {
    	seoul: true,
        daegu: true
    }
    daegu: {
    	seoul: true,
        busan: true
    }
}

console.log(isConnected.seoul.busan) // true
console.log(isConnected.busan.seoul) // true

上記のコードでは、ナビゲーションがソウルから釜山までの経路を出力し、釜山からソウルまでの経路を出力することができます.
(数百万のデータを追加すると、通常のナビゲーションと同様に、距離、時間などを幹線でマークできます.)

グラフィック用語のクリーンアップ

頂点(頂点):ノード(ノード)とも呼ばれ、データを格納するグラフィックの基本要素です.

幹線(edge):頂点間の関係を表します.

隣接頂点(隣接頂点):1つの頂点に幹線で直接接続された頂点を指します.

加重パターン:接続の強度を表します.

非重み付けパターン(Unweighted Graph):接続強度が記録されていないパターンを示します.

無方向図:一方向図であれば、単行線とみなされる.データは片側にしか移動できません.

入場回数(入場回数)/出駅回数(出駅回数):1つの頂点に入る幹線が何本あるかを示す.

隣接(隣接):2つの頂点間の直線が直接接続されている場合、2つの頂点は隣接する頂点です.

サイクル(cycle):1つの頂点から開始し、その頂点に戻ったときに1サイクルが存在することを示します.

（隣接比重が低い）

隣接行列

2つの頂点の間に関係があるかどうかを判断すると、

を使用して最速パスを検索

りんせつひょう

隣接リストは、リスト内の各頂点がどの頂点に隣接しているかを示します.
各頂点には、隣接する別の頂点を含むリストがあります.
隣接リストを使用する利点はありますが、優先度に関連するデータ構造を処理する必要がある場合は、キューとスタックを使用するのが合理的です.
それでも、隣接するリストを使用する理由は、メモリの有効な使用です.

Tree

木の枝が1本の根から周囲に伸びる形状を木構造と呼ぶ一方向図形の構造.
木の構造は、木を逆さにしたようです.


データが一方向に関連付けられた階層データ構造.非線形構造で、1つのデータの下に複数のデータがあります.ツリー構造は下にのみ伸びているため、ループはありません.
ツリー構造は、(Root)と呼ばれる頂点データから始まり、複数のデータを1つの直線(edge)に接続します.各データはノード(Node)と呼ばれ、2つのノードが最上位レベルに接続されると親子関係になります.
上記の例では、FをBおよびGの親ノード、BおよびGをFの子ノードと呼ぶ.A,C,E,Hのようなサブノードがないことをリーフノードと呼ぶ.

クリーンアップ用語

ノード(Node):ツリー構造内のすべての独立データ

本(Root):ツリー構造の始点であるノード

親ノード(Parent Node):2つのノードが上下に接続する場合、ルートノード

に相対的に近い.

サブノード(Child Node):2つのノードが上下に接続する場合、ルートノードから相対的に遠い

.

葉(Leaf):ツリー構造の終点で、サブアイテムがない場合は

です.

ツリー構造の深さ(depth)

ツリー構造のルートノードから特定のノードまでの深さを表すことができます.ルートノードの深さは0で、地面のようです.B,Gの深さは1である.A,D,Iの深さは2である.

ツリー構造のレベル(level)

ツリー構造内の同じ深さのノードを組み合わせてレベル(level)として表すことができます.深さが0の場合はlevel 1、深さが1の場合はlevel 2です.同じレベルで並べられたノードを兄弟ノードと呼びます.

サブツリー

ツリー構造のRootから突き出ており、小さなツリー構造を持つものをサブツリーと呼ぶ.B、A、Dを組み合わせてサブツリーとして使用できます.

ツリー内の線の使用

最も代表的な例は、コンピュータのディレクトリ構造です.プログラムまたはファイルを検索すると、フォルダに入り、別のフォルダに移動して必要なファイルを検索します.
すべてのフォルダはルートフォルダから始まります.

Binary Search Tree (BST)

ツリー構造は、便利な構造を示すのではなく、効率的なナビゲーションに使用されます.

バイナリツリー:最大2つのサブノードを含むツリー.2つのサブノードは、左サブノードと右サブノードに分けられます.

データの挿入と削除によって、バイナリツリーは完全バイナリツリー、完全バイナリツリー、飽和バイナリツリーに分けられます.
アンバランスなツリーは、ナビゲーションに時間がかかる可能性があるため、解決する必要がある問題です.

Tree traversal

特定の目的のために、ツリー内の各ノードを一度に巡ることをツリーループと呼ぶ.
ツリー内の3番のすべてのノード(1～10の整数)を検索する場合は、ツリーの一例を巡ります.
ツリーの遍歴方法

フォワードツアー
ルートノードから、左側のノードを順にブラウズし、左側のノードのナビゲーションが終了した後、右側のノードをナビゲートします.

中尉巡り
根を真ん中に置いて巡回します.左端のノードから巡回を開始し、左端ノードのルートノードに対する巡回が終了した後、右端ノードに移動します.

後巡
ルートディレクトリの最後に巡回します.最左端のノードから,ルートノードを通らずに右に移動し,最後にルートノード上を巡回する.

BFS / DFS

グラフィックをナビゲートする目的は、1つの頂点から始まり、グラフィック内のすべての頂点に1つずつアクセスすることです.グラフィックのデータはアレイのように整列しません.必要な資料を検索するには、1つずつアクセスする必要があります.
グラフィック内のすべての頂点のナビゲーション方法には、さまざまな方法があります.その中の2つの典型的な方法はDFSとBFSを紹介する.ただ、データを閲覧する順序が違うだけで、すべてのデータは同じです.

BFS

一番近い頂点からナビゲートを開始します.頂点と最短パスに順番にアクセスできます.

DFS

1つのパスの最後に移動し、次のパスに移動します.パスの表示を続け、頂点から次のパスに移動します.
(最近のパスを表示するよりも、正しいパスに移動し、他のパスを検索し続けます.)