What's Graph?

複数の点と線で接続された複雑なネットワーク状のグラフィックは、頂点と幹線から構成されています.
正確に言えば、頂点(Vertex)間の関係を表す組織も.
図形は木と異なり、頂点ごとに幹線がなく、親子の概念も存在しない可能性があります.
また,グラフィックはネットワークモデル,すなわちオブジェクトとその関係を表すと柔軟に理解できる.実生活で例を探せば、代表的な地下鉄路線図が挙げられる.
グラフィックはアルゴリズムで非常に多く使用されており,特にグラフィックの遍歴方式DFSとBFSが重要である.

非重み付け図:各頂点間に接続

があるか否かを判断する.

重み付け図:幹線接続度情報を含む図形

グラフィック用語

頂点(vertice):データを格納するノード(node)とも呼ばれます.

幹線(エッジ):ノード間の関係を表すリンク(arcs)とも呼ばれる.

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

単純パス(simple-path):パスに重複する頂点はなく、同じ幹線を通らないパス

回(度):無方向図の頂点に隣接する頂点数

インバウンド回数(アウトバウンド回数):方向図で使用する、1ノードから外への幹線数

.

インバウンド回数(インバウンド回数):外部ノードからインバウンドする幹線数

.

磁気リング(self-loop):幹線が他の頂点を通らずに直接自身に入る場合、

サイクル:出発と同じ頂点に到達したとき

グラフィックの表現

隣接マトリクスと隣接リスト.
二つの実現方式にはそれぞれメリットとデメリットがある.

隣接行列隣接行列

隣接マトリクスは、グラフィック内のノードの2 D配列です.
頂点が接続されている場合は、1(true)または0(false)のテーブルとして表されます.
重み付け図の場合、関係に意味のある値が1ではなく格納されます.
長所

の2 D配列には、すべての頂点の幹線情報が含まれています.
配列の位置を特定すれば,接続情報を問い合わせる際にO(1)の時間的複雑さを行うことができる.

は比較的簡便に実現されている.

短所
O(n)²)必要な時間の複雑さ.

は無条件に2次元配列を必要とするため、必要以上の空間を浪費する.

隣接マトリクスはいつ使用しますか?

大きなテーブルの隣接行列は、2つの頂点の間に関係があるかどうかを確認するのに便利です.
最短パス(最短パス)を検索します.

隣接マトリクスの実装

// 이해를 위해 기존 배열의 인덱스를 정점으로! (0, 1, 2, ... --> 정점)

class GraphWithAdjacencyMatrix {
    constructor() {
        this.matrix = []; // {matrix: []}
    }

    addVertex() {
	const currentLength = this.matrix.length;
	for (let i = 0; i < currentLength; i++) {
		this.matrix[i].push(0);
	    }
	  this.matrix.push(new Array(currentLength + 1).fill(0));
    }

    contains(vertex) {
        return !!this.matrix[vertex] 
        //vertex는 index니까 그 안에 값이 있으면 존재하는 거겠지?!
    }

    addEdge(from, to) {
	const currentLength = this.matrix.length - 1;
	if (from === undefined || to === undefined) {
	        console.log("2개의 인자가 있어야 합니다.");
		return;
	}
        // 간선을 추가할 수 없는 상황
	if (from > currentLength || to > currentLength || 
    	    from < 0 || to < 0) {
		console.log("범위가 매트릭스 밖에 있습니다.");
		return;
	}
      this.matrix[from][to] = 1
    }

    hasEdge(from, to) {
    	return !!this.matrix[from][to]
    }

    removeEdge(from, to) {
	const currentLength = this.matrix.length - 1;
	if (from === undefined || to === undefined) {
		console.log("2개의 인자가 있어야 합니다.");
		return;
	}
        // 간선을 지울 수 없는 상황
	if (from > currentLength || to > currentLength || 
            from < 0 || to < 0) {
                return;
	}
      this.matrix[from][to] = 0
    }
}

隣接リスト隣接リスト

隣接リストは、グラフィック内のノードをリストで表します.
各頂点には、隣接する他の頂点を含むリストがあります.
主に頂点のリスト配列を作成することによって関係を確立します.
長所

頂点の接続情報を検出する場合、O(n)の時間は

である可能性がある.

は必要なスペースしか使用しないので、スペースの無駄が少ない.

短所

特定の2点の接続の有無は、隣接する行列よりも長い時間を必要とする.
検索速度は配列より遅い.

は実現しにくい.

#リストの順序は重要ではありません.
優先度を処理する必要がある場合は、より適切なデータ構造(ex.queue,heap)を使用する必要があります.

隣接表はいつ使いますか?

メモリを効率的に使用したい場合は!
隣接マトリクスは、すべての接続可能な状況の数を格納するため、比較的メモリの消費量が多い.

隣接リストの実装(方向なし)

class GraphWithAdjacencyList {
	constructor() {
		this.vertices = {}; // {vertices: {}}
	}

	addVertex(vertex) {
		// 정점 추가
		// 인자(정점)은 키, 빈 배열은 값으로 할당.
		// 이미 존재한다면 덮지않고! => 논리연산자 사용
		this.vertices[vertex] = this.vertices[vertex] || []; 
       		// {vertices: {vertex: [], ...}}
    
	}

	contains(vertex) {
		// 정점 너 있니..? -> vertex에 value가 있니?
		return !!this.vertices[vertex];
	}

	addEdge(fromVertex, toVertex) {
		// 간선 추가
		// fromVertex의 인접 리스트에 toVertex를 추가
		// toVertex의 인접 리스트에 fromVertex를 추가 -> 무방향이니까
		
    		// 넘겨받은 두 정점 모두 존재해야 간선을 추가할 수 있겠지!?
		if (!this.contains(fromVertex) || !this.contains(toVertex)) {
			return; // 하나라도 존재하지 않으면 손 놔
		}
        
	// 첫 정점 리스트에 두번째 정점이 없다면 추가해줘
		if (!this.hasEdge(fromVertex, toVertex)) {
      			this.vertices[fromVertex].push(toVertex);
		}	

		if (!this.hasEdge(toVertex, fromVertex)) {
     			 this.vertices[toVertex].push(fromVertex);
		}
	}

	hasEdge(fromVertex, toVertex) {
		// 정점(fromVertex)이 존재하지 않으면 false 반환
		if (!this.contains(fromVertex)) {
			return false;
		}
		// 존재해? 그럼 해당 정점 리스트에 toVertex가 포함되어있니?
		return !!this.vertices[fromVertex].includes(toVertex);
	}

	removeEdge(fromVertex, toVertex) {
		// 간선 삭제 (전제: 넘겨받은 두 정점이 모두 존재한다면)
		// fromVertex의 인접 리스트에 있는 toVertex 삭제
		// toVertex의 인접 리스트에 있는 fromVertex 삭제 -> 무방향이니까

		if (!this.contains(fromVertex) || !this.contains(toVertex)) {
			return;
		}
	// 첫 정점 리스트에 두번째 정점이 존재하면 삭제해줘
   	// 두번째 정점의 인덱스 위치를 찾아서 제거
		if (this.hasEdge(fromVertex, toVertex)) {
			const index = this.vertices[fromVertex].indexOf(toVertex);
			this.vertices[fromVertex].splice(index, 1);
		}
    		if (this.hasEdge(toVertex, fromVertex)) {
			const index = this.vertices[toVertex].indexOf(fromVertex);
			this.vertices[toVertex].splice(index, 1);
		}
	}

	removeVertex(vertex) {
		// 정점 삭제 (전제: 넘겨받은 정점이 존재한다면)
		// 해당 정점을 삭제함은 물론,
		// 타 정점들의 리스트를 모두 순회하며 해당 정점과 이어져 있는 간선을 제거
		if (this.contains(vertex)) {
      			while(this.vertices[vertex].length) {
        			this.removeEdge(this.vertices[vertex][0], vertex)
      			}
      		    delete this.vertices[vertex]
		}
	}
}

TIL Point

splice()

array.splice(startIndex, deleteCount, item1, item2, ...)

既存のアレイを変更します.たとえば、アレイ要素の削除、置換、または新しい要素の追加などです.
削除された要素を含む配列を返します.

論理演算子
! (ex = !a) Logical NOT operator!! (ex = !!b) Double NOT正確な論理結果を得るためにBooleanを用いてタイプ変換を行った.
たとえば、0をfalse、1をtrueに設定できます.
&& (ex = a && b)
aがfalse値である場合、aは、それ以外にbを返す.(すべてtrueの場合は一番右側に戻ります)
したがって、ブール値とともに使用すると、両方の値が真の場合true、その他の場合falseが返されます.
|| (ex = a || b)
aが真の値である場合、aは、それ以外にbを返す.(すべてtrueの場合は一番左に戻ります)
したがって、ブール値とともに使用すると、1つが真の場合true、もう1つがfalseになります.

this.vertices[vertex] = this.vertices[vertex] || []; 
// 정점이 존재하면 그 것으로 할당하고 아니라면 빈배열을 할당하라