グラフィック(Graph)

コンピュータ工学のグラフ:複数の点間の複雑なつながりを表すデータ構造.

図面の実際の使用例

ソウル在住のAさんと釜山在住のBさんは旧友今週末はBさんの結婚式があるそうで、Aさんは車で釜山に行く予定です.ちょうど、大田に住んでいるAさんとBさんの友人Cさんも参加するので、Aさんは大田からCさんを乗せて釜山に行きたいと思っています.
上記の例では、A、B、Cの3つの頂点があり、各都市をグラフィックの頂点に代入することができます.また,この3つの頂点は相互に接続された幹線(関係)を有している.

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true
  },
  daejeon: {
    seoul: true,
    busan: true
  },
  busan: {
    seoul: true,
    daejeon: true
  }
}
console.log(isConnected.seoul.daejeon) // true
console.log(isConnected.daejeon.busan) // true

重み付け(接続強度)が書かれていない現在の図形を非重み付け図形と呼ぶ.

非重み付けパターンは、各頂点間に接続があるか否かのみを判断し、重み付けパターンはより詳細な情報を提供することができる.

非重み付けグラフィック
頂点:ソウル、大田、釜山
幹線:ソウル-大田、大田-釜山、釜山-ソウル

加重パターン
頂点:ソウル、大田、釜山
幹線:ソウル-140キロ-大田、大田-200キロ-釜山、釜山-325キロ-ソウル

理解する必要があるグラフィック用語。

無方向図:前のナビゲーション例は無方向図である.ソウルから釜山に行くこともできますし、逆に釜山からソウルに行くこともできます.しかし、一方向(directed)グラフを採用すれば、ソウルから釜山に行くことができるが、釜山からソウルに行くことは不可能(または逆)だ.2つの場所が1本の一方通行につながっている場合は、一方通行の幹線で表すことができます.

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

隣接(隣接):2つの頂点の間に直接直線がある場合、2つの頂点は隣接する頂点です.

磁気リング(self-loop):頂点から入る幹線が直接自身に入ると、磁気リングがあることを示します.他の頂点を通らないのが特徴です.

サイクル(cycle):頂点から頂点を返すことができる場合は、サイクルが存在することを示します.ナビゲーション例では、ソウル->大田->釜山->ソウルが存在周期のグラフです.

隣接行列

A의 진출차수는 1개 입니다: A —> C
[0][2] === 1
B의 진출차수는 2개 입니다: B —> A, B —> C
[1][0] === 1
[1][2] === 1
C의 진출차수는 1개입니다: C —> A
[2][0] === 1

Q)隣接行列はいつ使えば良いですか?

は、2つの頂点の間に関係があるかどうかを容易に確認します.

AからBまでの幹線を決定するには、0行目の最初の列に格納されている値をすぐに確認します.

主に最短経路(最短経路)を探すために使用されます.

りんせつひょう

Q)隣接表はいつ使えばいいですか?

隣接行列は、すべての接続可能な場合の数を格納する.

が隣接していない場合は0が格納され、隣接している場合は1が格納され、メモリが大量に消費されます.

メモリを効率的に使用する場合は、隣接マトリクスではなく隣接リストを使用します.