[자료 구조 기초] Graph

July 26, 2022 6 분 소요

Graph

Graph : 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료 구조 -> 마치 네트워크 망과 같은 형태를 띈다.

Graph의 구조

직접적인 관계가 있는 경우 두 점 사이의 선을 통해 표현한다.
간접적인 관계라면 몇 개의 점과 선을 통해 이어진다.
여기서 점을 정점(vertex)라고 표현하고, 선을 간선이라고 한다.

Graph의 표현 방식

인접행렬

인접 행렬 : 두 정점이 이어져 있다면 ‘1’ 이어져 있지 않다면 ‘0’으로 나타낸 행렬

언제 사용?

두 정점 사이의 관계 파악에 용이
가장 빠른 경로를 찾고자 할 때 주로 사용

Ex.

// directed graph (방향 그래프)
// unweighted (비가중치)
// adjacency matrix (인접 행렬)
// 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다 (0, 1, 2, ... --> 정점)

class GraphWithAdjacencyMatrix {
	constructor() {
		this.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 vertex < this.matrix.length;
	}

	addEdge(from, to) {
		const currentLength = this.matrix.length;
		if (from === undefined || to === undefined) {
			console.log("2개의 인자가 있어야 합니다.");
			return;
		}
		if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
			console.log("범위가 매트릭스 밖에 있습니다.");
			return;
		}
        this.matrix[from][to] = 1;
	}

	hasEdge(from, to) {
    return this.matrix[from][to] === 1;
	}

	removeEdge(from, to) {
		const currentLength = this.matrix.length;
		if (from === undefined || to === undefined) {
			console.log("2개의 인자가 있어야 합니다.");
			return;
		}
		if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
      return;
		}
        this.matrix[from][to] = 0;
	}
}

const adjMatrix = new GraphWithAdjacencyMatrix();
adjMatrix.addVertex();
adjMatrix.addVertex();
adjMatrix.addVertex();
console.log(adjMatrix.matrix);
/*
							TO
		 	  	 0  1  2
		  	0	[0, 0, 0],
	FROM 	1	[0, 0, 0],
		  	2	[0, 0, 0]
*/
let zeroExists = adjMatrix.contains(0);
console.log(zeroExists); // true
let oneExists = adjMatrix.contains(1);
console.log(oneExists); // true
let twoExists = adjMatrix.contains(2);
console.log(twoExists); // true

adjMatrix.addEdge(0, 1);
adjMatrix.addEdge(0, 2);
adjMatrix.addEdge(1, 2);

let zeroToOneEdgeExists = adjMatrix.hasEdge(0, 1);
console.log(zeroToOneEdgeExists); // true
let zeroToTwoEdgeExists = adjMatrix.hasEdge(0, 2);
console.log(zeroToTwoEdgeExists); // true
let oneToZeroEdgeExists = adjMatrix.hasEdge(1, 0);
console.log(oneToZeroEdgeExists); // false

console.log(adjMatrix.matrix);
/*
							TO
		 	  	 0  1  2
		  	0	[0, 1, 1],
	FROM 	1	[0, 0, 1],
		  	2	[0, 0, 0]
*/

adjMatrix.removeEdge(1, 2);
adjMatrix.removeEdge(0, 2);
let oneToTwoEdgeExists = adjMatrix.hasEdge(1, 2);
console.log(oneToTwoEdgeExists); // false
zeroToTwoEdgeExists = adjMatrix.hasEdge(0, 2);
console.log(zeroToTwoEdgeExists); // false

console.log(adjMatrix.matrix);
/*
							TO
		 	  	 0  1  2
		  	0	[0, 1, 0],
	FROM 	1	[0, 0, 0],
		  	2	[0, 0, 0]
*/

인접 리스트

인접 리스트 : 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현

여기서 우선 순위를 고려하지 않는다면 순서는 중요하지 않다.

언제 사용?

메모리를 효율적으로 사용하고 싶을 때 사용
- 인접 행렬의 경우 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리 많이 차지

Ex.

// undirected graph (무향 그래프)
// adjacency list (인접 리스트)
class GraphWithAdjacencyList {
	constructor() {
		this.vertices = {};
	}

	addVertex(vertex) {
		// 이미 존재하는 정점이라면 덮어씌워지지 않게 방지합니다.
		this.vertices[vertex] = this.vertices[vertex] || [];
	}

	contains(vertex) {
		// 인자로 넘겨받은 정점의 존재여부를 반환합니다.
		return !!this.vertices[vertex];
	}

	addEdge(fromVertex, toVertex) {
		// 넘겨받은 두 정점중 하나라도 존재하지 않는다면
		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)이 존재하지 않는다면
		if (!this.contains(fromVertex)) {
			// false를 반환합니다
			return false;
		}
		// 존재한다면 해당 정점의 리스트에 toVertex가 포함되어있는지 반환합니다
		return !!this.vertices[fromVertex].includes(toVertex);
	}

	removeEdge(fromVertex, toVertex) {
		// 넘겨받은 두 정점중 하나라도 존재하지 않는다면
		if (!this.contains(fromVertex) || !this.contains(toVertex)) {
			// 아무것도 하지않고 종료합니다
			return;
		}

		// 두 정점이 모두 존재한다면
		// 첫번째 정점의 인접 리스트에 두번째 정점이 있을 경우
		if (this.hasEdge(fromVertex, toVertex)) {
			// 두번째 정점의 인덱스를 찾은 뒤 삭제합니다
			const toVertexIndex = this.vertices[fromVertex].indexOf(toVertex);
			this.vertices[fromVertex].splice(toVertexIndex, 1);
		}
		// 두번째 정점의 인접 리스트에 첫번째 정점이 있을 경우
		if (this.hasEdge(toVertex, fromVertex)) {
			// 첫번째 정점의 인덱스를 찾은 뒤 삭제합니다
			const fromVertexIndex = this.vertices[toVertex].indexOf(fromVertex);
			this.vertices[toVertex].splice(fromVertexIndex, 1);
		}
	}

	removeVertex(vertex) {
		// 만약 인자로 넘겨받은 정점이 존재한다면
		if (this.contains(vertex)) {
			// 해당 정점과 연결된 간선을 지우고
			while (this.vertices[vertex].length > 0) {
				this.removeEdge(this.vertices[vertex][0], vertex);
			}
			// 최종적으로 해당 정점을 삭제합니다
			delete this.vertices[vertex];
		}
	}
}

const adjList = new GraphWithAdjacencyList();
adjList.addVertex("Seoul");
adjList.addVertex("Daejeon");
adjList.addVertex("Busan");

adjList.contains("Seoul"); // true
adjList.contains("Jeonju"); // false

adjList.addEdge("Daejeon", "Seoul");
adjList.hasEdge("Seoul", "Daejeon"); //true

adjList.removeVertex("Seoul");
adjList.hasEdge("Seoul", "Daejeon"); //false

그래프 용어

정점(vertex) : 노드라고 하며 데이터가 저장되는 그래프의 기본 원소
간선(edge) : 정점 간의 관계 == 정점을 이어주는 선
인접 정점(adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
가중치 그래프(unweighted Graph) : 연결의 강도가 명시된 그래프
비가중치 그래프(undirected Graph) : 연결의 강도가 명시되지 않은 그래프
무방향 그래프(undirected graph) : 간선의 방향이 없는 그래프
진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 들어오는 간선 개수 / 한 정점에서 나가는 간선 개수
인접(adjacency) : 두 정점 간에 간선이 직접 이어져 있는 경우
자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 집입하는 경우
사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 경우

그래프 탐색 : BFS/DFS

그래프 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 탐색하는 것이 목적이다.

BFS : Breath-Frist Search(넓이 우선 탐색)

구현 : Queue

시작할 노드을 Queue에 넣는다.
노드을 Queue에서 하나 꺼낸다.
꺼낸 노드의 자식 노드들을 Queue에 넣는다.
1. 여기서 한 번 담았던 노드는 Queue에 넣지 않는다.
2. 꺼낸 정점의 자식 노드가 없거나 Queue에 넣은 노드이었다면 바로 출력
꺼낸 노드을 출력한다.

의 반복 => Queue가 빌 때까지

DFS : Depth-First Search(깊이 우선 탐색)

구현 : Stack, Recursion

Stack

시작할 노드을 Stack에 넣는다.
노드을 Stack에서 하나 꺼낸다.
꺼낸 노드의 자식 노드들을 Stack에 넣는다.
1. 여기서 한 번 담았던 노드는 Stack에 넣지 않는다.
2. 꺼낸 정점의 자식 노드가 없거나 Stack에 넣은 노드이었다면 바로 출력
꺼낸 노드을 출력한다.

의 반복 => Stack이 빌 때까지

Recursion : stack과 다르게 정방향으로 호출

시작할 노드로 함수를 호출한다.
자식 노드로 함수를 재귀 호출한다. -> return

의 반복

BFS/DFS 예제

Ex. 연결된 정점 개수 찾기

function connectedVertices(edges) {

	// 최대 버텍스를 찾습니다.
	const maxVertex = edges.reduce((a, c) => {
		const bigger = Math.max(...c);
		if (bigger > a) return bigger;
		return a;
	}, 0);

	//인접 리스트
	const adjList = {};

  // 인접 리스트에 최대 버텍스 크기만큼 반복해 버텍스를 생성
	for (let i = 0; i <= maxVertex; i++) {
		adjList[i] = [];
	}

  // edges를 순회하며, 간선을 연결해 줍니다.
	for (let i = 0; i < edges.length; i++) {
		adjList[edges[i][0]].push(edges[i][1]);
		adjList[edges[i][1]].push(edges[i][0]);
	}

  // 방문한 버텍스를 담을 객체를 선언합니다.
	const visited = {};
	// 컴포넌트가 몇 개인지 카운트할 변수를 선언합니다.
	let count = 0;

  // 그래프에 있는 버텍스를 전부 순회합니다.
	for (let vertex = 0; vertex <= maxVertex; vertex++) {

		// 만약 i 번째 버텍스를 방문하지 않았다면 bfs로 해당 버텍스와, 버텍스와 연결된(간선) 모든 버텍스를 방문합니다.
		// BFS로 갈 수 있는 모든 정점들을 방문하며 visited에 담기 때문에, 방문한 버텍스는 visited에 들어 있어서 bfs를 돌지 않습니다.
		if (!visited[vertex]) {
			// 그래프와 버텍스, 방문했는지 확인할 visited를 변수에 담습니다.
			bfs(adjList, vertex, visited);

			// 카운트를 셉니다.
			count++;
		}
	}

  // 카운트를 반환합니다.
	return count;
}

// bfs solution
function bfs(adjList, vertex, visited) {

	// bfs는 가장 가까운 정점부터 탐색하기 때문에 queue를 사용합니다.
	// queue에 vertex를 담습니다.
	const queue = [vertex];
	// 해당 버텍스를 방문했기 때문에 visited에 담아 주고, 방문했다는 표시인 true를 할당합니다.
	visited[vertex] = true;

  // queue의 길이가 0일 때까지 순환합니다.
	while (queue.length > 0) {

		// cur 변수에 정점을 할당합니다.
		// queue는 선입선출이기 때문에 shift 메소드를 사용하여 버텍스를 가져옵니다.
		const cur = queue.shift();

		// 그래프의 cur 정점에 있는 간선들을 전부 순회합니다.
		for (let i = 0; i < adjList[cur].length; i++) {

			// 만약, 해당 버텍스를 방문하지 않았다면 queue에 삽입합니다.
			// 방문했다는 표시로 visited에 해당 버텍스를 삽입하고 true를 할당합니다.
			if (!visited[adjList[cur][i]]) {
				queue.push(adjList[cur][i]);
				visited[adjList[cur][i]] = true;
			}

			// queue에 다음으로 방문할 버텍스가 있기 때문에 while은 멈추지 않습니다.
			// 만약, queue가 비어 있다면 더 이상 갈 곳이 없는 것이기 때문에 bfs 함수를 종료하고 카운트를 셉니다.
		}
	}
}

// dfs solution
function dfs(adjList, vertex, visited) {
	// 해당 버텍스에 방문했다는 표시로 visited key에 vertex를 담고 값에 true를 할당합니다.
	visited[vertex] = true;

	// 해당 버텍스의 모든 간선들을 전부 순회합니다.
	for (let i = 0; i < adjList[vertex].length; i++) {

		// 만약 i번째 간선과 이어진 버텍스를 방문하지 않았다면
		if (!visited[adjList[vertex][i]]) {
			// dfs를 호출해(재귀) 방문합니다.
			dfs(adjList, adjList[vertex][i], visited);
		}
		// 모든 방문이 종료되면 다음 버텍스를 확인합니다.
		// 재귀가 종료되면(한 정점에서 이어진 모든 간선들을 확인했다면) dfs 함수를 종료하고 카운트를 셉니다. 
	}
}

본 포스팅은 코드스테이츠 BEB 과정을 수강하며 작성한 글입니다.

Twitter Facebook LinkedIn

apfl99

[자료 구조 기초] Graph

Graph

Graph의 구조

Graph의 표현 방식

인접행렬

인접 리스트

그래프 용어

그래프 탐색 : BFS/DFS

BFS : Breath-Frist Search(넓이 우선 탐색)

구현 : Queue

DFS : Depth-First Search(깊이 우선 탐색)

구현 : Stack, Recursion

BFS/DFS 예제

공유하기

참고

DankSharding

The Merge

DankSharding의 등장 배경

Final Project : Ad4U, 유튜브 광고 중개 플랫폼