Data Structures & Algorithms with Javascript : Graphs and Graph Algorithms

2024.07.25 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Binary Trees and Binary Search Trees

Data Structures & Algorithms with Javascript : Binary Trees and Binary Search Trees

2024.07.24 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Sets Data Structures & Algorithms with Javascript : Sets[이전 글]2024.07.23 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Java

pyotato-dev.tistory.com

오늘은 그래프로 네트워크가 모델링 되는 방식, 그래프가 무엇인지, 자바스크립트로 구현 등에 대해 살펴보자.

‼ 예제는 책의 구현을 참고하여 클래스로 재구성했습니다!!

🕸️ 그래프란?

그래프는 vertice(vertex의 복수형)와 edge로 구성된다.

그래프의 개념을 강남구 지도에 대입해보자면 vertice는 강남역, 역삼역, 삼성역 등등의 역이고,

각 역을 연결하고 있는 2호선 지하철이 edge에 해당된다.

강남역(v1)에서 삼성역(v2)으로 가는 지하철 노선도 있겠지만 버스를 타고 갈 수도 있고, 걸어가는 길도 있을 수도 있다.

가는 방법에 따라 비용이나 시간이 달라질 수 있는데, 그래프에서는 이 비용을 weight (cost) 라고 한다.

강남역(v1)에서 삼성역(v2)으로 이어지는 edge를 pair(v1, v2)로 정의할 수 있다.

vertice들을 연결하는 edge들을 path라고 하는데, 자기 자신의 vertex로 연결된 path는 loop라고 한다.

하나의 vertex에서 다른 vertex까지를 path의 길이(length)라고 하고, loop의 path 길이는 0이다.

아래의 지도는 출발 지점과 도착지점이 있다. 이렇게 방향이 있는 그래프는 directed graph (digraph)라고 한다.

반면에 방향이 없는 그래프는 unordred graph (graph)라고 한다.

두 vertice 사이에 path가 있다면 strongly connected라고 표현한다.

🗺️ 그래프 구현

언뜻보면 그래프 구조가 트리나 이진트리와 비슷해 보이기 때문에 각 vertex를 나타내기 위해 Node 클래스로 나타내려고 할 수도 있다. 하지만 Node 클래스와 같은 객체 기반의 접근은 그래프의 크기가 커짐에 따라 부적합할 수 있다. 그리고 이진트리는 자식 노드의 개수가 2개 이하로 제한되었기 때문에 노드 간의 연결이 무한할 수 있는 그래프를 표현하기에는 어려움이 있다.

그럼 어떤 자료 구조로 vertice와 edge를 표현할 수 있을까?

Vertex 구현

Graph 클래스를 만들기 위해 그래프를 구성할 Vertex가 필요하다.

이진 탐색 트리와 linked list에서 살펴봤던 것처럼 Node 클래스는 Vertex와 비슷한 기능을 수행해야한다.

Vertex가 지녀야 할 정보는 다음과 같다

label : vertex의 값
wasVisited : vertex 방문 여부

class Vertex{
	constructor(label){
		this.label = label;
	}
}

Edge 구현

인접 리스트 (adjacency list 또는 array of adjacency lists)

두 개의 배열을 활용한다. 각 배열의 인덱스가 vertice를 나타내고, 각 배열의 값은 그 vertice가 연결된 vetice를 나타낸다.

예를 들면 다음과 같은 그래프가 있다고 하자. vertice 2는 나머지 0,1,3,4와 연결된 edge들이 있다.

인접 리스트를 활용해서 다음과 같이 연결 관계를 표현할 수 있다.

vertex 인덱스 0에는 vertex 인덱스 2가, 인덱스 1에는 2가 인덱스 2는 0,1,3,4가, 인덱스 3은 인덱스 2가, 그리고 인덱스 4는 2를 배열 원소로 지닐 수 있다.

인접 행렬 (adjacency matrix)

이차원 배열로 두 vertice 사이에 edge가 존재하는지 나타내는 방식으로도 나타낼 수 있다.

vertex 사이에 edge가 존재하면 true(1), 아니면 false(0)

0, 1, 2, 3, 4
0 [0, 0, 1, 0, 0]
1 [0,  0,  1,  0,  0]
2 [1,  1,  0,  1,  1]
3 [0,  0,  1,  0,  0]
4 [0,  0,  1, 0,  0]

그래프 구현

우리는 인접 리스트로 그래프를 구현해보자.

class Graph {
	constructor(v){
    	this.vertices = v; 
        this.edges = 0;
        this.adj = [];	// 인접 리스트로 구현
        for(let i=0; i<this.vertices;++i){
        	this.adj[i] = [];
        }
    }
    
    // 출력 헬퍼 함수
    print(item){
		console.log(item);
	}
    
    // edge 추기
	addEdge(v,w){
    	this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    }
	
    // 그래프 그리기
    showGraph(){
    	for(let i=0; i< this.vertices; ++i){
            this.print(`${i} -> ${this.adj[i].join(', ')}`);
        }
    }
}

const graph = new Graph(5);
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(1,3);
graph.addEdge(2,4);
graph.showGraph();

/**
0 -> 1, 2
1 -> 0, 3
2 -> 0, 4
3 -> 1
4 -> 2

*/

그래프 탐색

그래프 탐색 알고리즘에는 두 가지가 있다 : DFS(depth-first-search)와 BFS (breadth-first search)

DFS (깊이 우선 탐색)

dfs는 시작하는 vertex에서 마지막 vertex에 도달할 때까지 탐색하고,

끝 vertex에서 역으로 거슬러 (backtrack) 올라와서 더 이상 방문하지 않은 vertex가 없을 때까지 다음 path을 탐색한다.

dfs 알고리즘 구현 로직은 간단한 편이다. 아직 방문하지 않은 vertex들을 방문하고 방문여부를 마크하면 된다.

방문하지 않은 vertex가 없을 때까지 재귀적으로 탐색을 하면 된다.

구현

class Graph {
	constructor(v){
    	this.vertices = v; 
        this.edges = 0;
        this.adj = [];	
        for(let i=0; i<this.vertices;++i){
        	this.adj[i] = [];
        }
        /////////////////////////// 💖수정 ///////////////////////////
        this.visited = [];	
        for(let i=0; i<this.vertices;++i){
        	this.visited[i] = false;
        }
        /////////////////////////// 💖수정 ///////////////////////////
    }
    
    // 출력 헬퍼 함수
    print(item){
		console.log(item);
	}
    
    // edge 추기
	addEdge(v,w){
    	this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    }
	
    // 그래프 그리기
    showGraph(){
    	for(let i=0; i< this.vertices; ++i){
            this.print(`${i} -> ${this.adj[i].join(', ')}`);
        }
    }
    /////////////////////////// 💖추가 ///////////////////////////
    // dfs 
    dfs(v){
    	this.visited[v] = true;
        if(this.adj[v] != undefined){
        	this.print(`visited vertex: ${v}`);
        }
        this.adj[v].forEach((w)=>{
            if(!this.visited[w]){
                this.dfs(w);
            }
        })
    }
    /////////////////////////// 💖추가 ///////////////////////////
}

const graph = new Graph(5);
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(1,3);
graph.addEdge(2,4);
graph.showGraph();
graph.dfs(0);

/**
0 -> 1, 2
1 -> 0, 3
2 -> 0, 4
3 -> 1
4 -> 2
visited vertex: 0
visited vertex: 1
visited vertex: 3
visited vertex: 2
visited vertex: 4
*/

BFS (너비 우선 탐색)

bfs는 첫 vertex에서 시작해서 가능한 가장 가까운 vertex를 찾아 방문한다.

하나의 path을 따라 마지막 vertex에 방문하려는 dfs와는 달리 bfs는 layer 단위로 먼저 방문한다.

위의 그림에서 k, h, e, b는 같은 layer에, c, f, i, l도 같은 layer다. bfs는 첫 vertex인 a부터 시작해서 가까운 layer들의 vertex들을 방문한다. bfs는 vertice 방문을 표현하기 위해 queue를 추상화한 알고리즘을 활용한다.

알고리즘 로직은 다음과 같다.

현재 vertex와 가장 가까운 방문하지 않은 vertex를 찾아 방문한 vertice 리스트에 추가하고 queue에도 추가한다.
다음 vertex v를 그래프에서 가져와 방문한 vertice 리스트에 추가한다.
v와 인접한 방문하지 않은 vertice를 모두 queue에 추가한다.

class Graph {
	constructor(v){
    	this.vertices = v; 
        this.edges = 0;
        this.adj = [];	
        for(let i=0; i<this.vertices;++i){
        	this.adj[i] = [];
        }
        this.visited = [];	
        for(let i=0; i<this.vertices;++i){
        	this.visited[i] = false;
        }
    }
    
    // 출력 헬퍼 함수
    print(item){
		console.log(item);
	}
    
    // edge 추기
	addEdge(v,w){
    	this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    }
	
    // 그래프 그리기
    showGraph(){
    	for(let i=0; i< this.vertices; ++i){
            this.print(`${i} -> ${this.adj[i].join(', ')}`);
        }
    }
    
    // dfs 
    dfs(v){
    	this.visited[v] = true;
        if(this.adj[v] != undefined){
        	this.print(`visited vertex: ${v}`);
        }
        this.adj[v].forEach((w)=>{
            if(!this.visited[w]){
                this.dfs(w);
            }
        })
    }
    
    /////////////////////////// 💖추가 ///////////////////////////
    // bfs 
    bfs(s){
    	let queue = [];
    	this.visited[s] = true;
        queue.push(s);	// 맨 뒤에 추가
        while(queue.length>0){
        	let v = queue.shift(); // 맨 앞에서 꺼내오기
            if(v != null){
            	this.print(`visited vertex : ${v}`);
            }
            this.adj[v].forEach((w)=>{
                if(!this.visited[w]){
                    this.visited[w]= true;
					queue.push(w);
                }
       		})
        }

    }
    /////////////////////////// 💖추가 ///////////////////////////
}

const graph = new Graph(5);
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(1,3);
graph.addEdge(2,4);
graph.showGraph();
graph.bfs(0);

/**
0 -> 1, 2
1 -> 0, 3
2 -> 0, 4
3 -> 1
4 -> 2
visited vertex: 0
visited vertex: 1
visited vertex: 3
visited vertex: 2
visited vertex: 4
*/

dfs bfs 비교

그래프로 나타내기

0 -> 1, 2
1 -> 0, 3
2 -> 0, 4
3 -> 1
4 -> 2

3️⃣
b ⁄
1️⃣
a ⁄
0️⃣
＼ c
2️⃣
＼ d
4️⃣

dfs
vertex 방문 순서 : 0 1 3 2 4
edge : a b c d

bfs
vertex 방문 순서 : 0 1 2 3 4
edge : a c b d

최단 거리 구하기

그래프 연산 중 가장 흔하게 사용되는 것은 두 vertex 간의 최단 거리를 구하는 것이다.

이미지 출처 : https://m.blog.naver.com/hoti7746/223029389423

🏝️ 유럽으로 휴가를 간다고 생각해 보자.

파리, 스위스 오스트리아, 베네치아, 플로렌스, 로마를 모두 방문하고 싶은데

2주 안에 최대한 적은 거리로 방문할 수 있는 방법이 뭘까?

최단 거리 알고리즘을 활용해 본다면 가야 하는 거리를 최소화해 볼 수 있다.

BFS로 최단 거리 찾기

bfs의 경우 자동으로 하나의 vertex에서 다른 vertex로 가는 최단 거리를 찾게 된다.

예를 들어 A vertex에서 D로 가는 최단 거리를 구할 때, 두 vertex로 가능 edge가 1개인 경우부터 그다음에는 2개인 경우 그다음은 3개... 이런 방식으로 거리를 구한다. bfs가 동작하는 방식과 동일하기 때문에 bfs를 조금 수정해서 최단 거리 알고리즘을 구현해 보자.

class Graph {
    constructor(v){
        this.vertices = v; 
        this.edges = 0;
        this.adj = [];    
        for(let i=0; i<this.vertices; ++i){
            this.adj[i] = [];
        }
        this.visited = [];    
        for(let i=0; i<this.vertices; ++i){
            this.visited[i] = false;
        }
        this.edgeTo = [];
    }
    
    // 출력 헬퍼 함수
    print(item){
        console.log(item);
    }
    
    // edge 추가
    addEdge(v, w){
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    }
    
    // 그래프 그리기
    showGraph(){
        for(let i=0; i< this.vertices; ++i){
            this.print(`${i} -> ${this.adj[i].join(', ')}`);
        }
    }
    
    // dfs 
    dfs(v){
        this.visited[v] = true;
        if(this.adj[v] != undefined){
            this.print(`visited vertex: ${v}`);
        }
        this.adj[v].forEach((w)=>{
            if(!this.visited[w]){
                this.dfs(w);
            }
        });
    }
    
    // bfs 
    bfs(s){
        let queue = [];
        this.visited[s] = true;
        queue.push(s);    // 맨 뒤에 추가
        while(queue.length > 0){
            let v = queue.shift(); // 맨 앞에서 꺼내오기
            if(v != null){
                this.print(`visited vertex: ${v}`);
            }
            this.adj[v].forEach((w)=>{
                if(!this.visited[w]){
                    this.edgeTo[w] = v; 
                    this.visited[w] = true;
                    queue.push(w);
                }
            });
        }
    }
    /////////////////////////// 💖추가 ///////////////////////////
    // 방문 여부 리턴 헬퍼 함수
    hasPathTo(v) { 
        return this.visited[v];
    }
    
    // 시작점에서 목적지까지의 path 
    pathTo(v){
        let source = 0;
        if(!this.hasPathTo(v)){
            return undefined;
        }
        let path = [];
        for(let i = v; i != source; i = this.edgeTo[i]){
            path.push(i);
        }
        path.push(source); // source를 path에 추가 
        return path.reverse(); // source에서 destination 까지의 path 
    }
    /////////////////////////// 💖추가 ///////////////////////////
}

const graph = new Graph(5);
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(1,3);
graph.addEdge(2,4);

// 0부터 bfs
graph.bfs(0);

let vertex = 4;
let paths = graph.pathTo(vertex);

if (paths) {
    let pathString = paths.join('-');
    graph.print(pathString);
} else {
    graph.print("No path found");
}

/**
Expected output:
0-2-4
*/

Topological Sorting (위상 정렬)

위상정렬은 방향이 있는 그래프의 vertice들을 정렬한 건데, 가리키고 있는 vertice들이 없다면 먼저 위치시키고, 다른 vertex가 가리키고 있는 vertex들은 모두 이후에 정렬하는 방식이다.

위상 정렬을 하면 그래프는 다음과 같다.

CS1
CS2
Assembly language
Data structures
Operating systems
Algorithms

3번 수업 (Assembly language)와 4번 수업(Data structure)은 동시에 수강이 가능하고, 5번 수업 (Operating systems)와 6번 수업(Algorithms)도 동시에 수강이 가능하다. 하지만 CS2를 수강하지 않고서는 Data structures를 수강할 수는 없다.

이 문제를 precedence-constrained scheduling라고 한다.

위상 정렬 알고리즘은 dfs와 비슷하다. 하지만 방문한 vertex를 바로 출력하는 대신

현재 vertex와 인접한 vertice를 모두 방문하고 나서 현재 vertex를 스택에 추가하는 방식이다.

위상정렬 알고리즘은 두 개의 메서드가 핵심이다.

topSort : 정렬 과정을 하는 topSortHelper를 호출하는 헬퍼 함수
topSortHelper : 정렬된 vertice들 리스트를 보여준다. 현재 vertex를 방문 처리하고 재귀적으로 현재 vertex의 인접 리스트에 인접한 vertex를 방문하고 방문처리를 한다. 마지막으로 현재 vertex를 스택에 추가한다.

class Graph {
    constructor(v){
        this.vertices = v; 
        this.edges = 0;
        this.adj = [];    
        for(let i = 0; i < this.vertices; ++i){
            this.adj[i] = [];
        }
        this.visited = [];    
        for(let i = 0; i < this.vertices; ++i){
            this.visited[i] = false;
        }
        this.edgeTo = [];
        this.vertexList = [];
    }
    
    print(item){
        console.log(item);
    }
    
    addEdge(v, w){
        this.adj[v].push(w);
        this.edges++;
    }

    addVertex(v){
        this.vertexList.push(v);
    }
    
    showGraph(){
        for(let i = 0; i < this.vertices; ++i){
            this.print(`${this.vertexList[i]} -> ${this.adj[i].map(v => this.vertexList[v]).join(', ')}`);
        }
    }
    
    dfs(v){
        this.visited[v] = true;
        if(this.adj[v] != undefined){
            this.print(`visited vertex: ${this.vertexList[v]}`);
        }
        this.adj[v].forEach((w) => {
            if(!this.visited[w]){
                this.dfs(w);
            }
        });
    }
    
    
    bfs(s){
        let queue = [];
        this.visited[s] = true;
        queue.push(s);    
        while(queue.length > 0){
            let v = queue.shift(); 
            if(v != null){
                this.print(`visited vertex: ${this.vertexList[v]}`);
            }
            this.adj[v].forEach((w) => {
                if(!this.visited[w]){
                    this.edgeTo[w] = v; 
                    this.visited[w] = true;
                    queue.push(w);
                }
            });
        }
    }

    // vertex로 가는 path 있는 지 확인하는 헬퍼 함수
    hasPathTo(v) { 
        return this.visited[v];
    }
    
    // vertex로가는 path 구하기
    pathTo(v){
        let source = 0;
        if(!this.hasPathTo(v)){
            return undefined;
        }
        let path = [];
        for(let i = v; i != source; i = this.edgeTo[i]){
            path.push(i);
        }
        path.push(source); // source로가는 path 추가
        return path.reverse(); // source에서 destination 가는 Path 
    }
     /////////////////////////// 💖추가 ///////////////////////////
    // Topological sort
    topSort(){
        let stack = [];
        let visited = new Array(this.vertices).fill(false);
        for (let i = 0; i < this.vertices; i++) { 
            if (visited[i] == false) {
                this.topSortHelper(i, visited, stack); 
            }
        }
        while(stack.length > 0) {
            this.print(this.vertexList[stack.pop()]);
        }
    }
    
    topSortHelper(v, visited, stack) { 
        visited[v] = true;
        this.adj[v].forEach((w) => {
            if(!visited[w]){
                this.topSortHelper(w, visited, stack);
            }
        });
        stack.push(v);
    }
     /////////////////////////// 💖추가 ///////////////////////////
}


const graph = new Graph(6);

graph.addVertex("CS1"); // 0
graph.addVertex("CS2"); // 1
graph.addVertex("Data Structures"); // 2
graph.addVertex("Assembly Language"); // 3
graph.addVertex("Operating Systems"); //4
graph.addVertex("Algorithms"); // 5

graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(2, 5);

graph.topSort();

/**
CS1
CS2
Assembly Language
Data Structures
Algorithms
Operating Systems
*/

📚 Reference

'🪲 debug' 카테고리의 다른 글

[Jest + RTL (next/link)] TypeError: Cannot read properites of null (reading 'useContext') ft. jest.mock (0)	2024.08.02
[jest + rtl + monorepo + next + ts]SyntaxError : Unexpected token '<' (ft. "jsx": "react-jsx") (0)	2024.07.31
Warning: React.jsx: type is invalid -- expected a string (for built-in components) or a class/function (for composite components) but got: undefined... (1)	2024.07.23
ReferenceError: __dirname is not defined in ES module scope (0)	2024.07.16
[turboRepo scss] Cannot find module './mybutton.module.scss' or its corresponding type declarations.ts(2307) (0)	2024.07.11

🥕 pyotato's dev farm

Data Structures & Algorithms with Javascript : Graphs and Graph Algorithms

🕸️ 그래프란?

🗺️ 그래프 구현

Vertex 구현

Edge 구현

그래프 구현

그래프 탐색

최단 거리 구하기

Topological Sorting (위상 정렬)

📚 Reference

'🪲 debug' 카테고리의 다른 글

티스토리툴바

Data Structures & Algorithms with Javascript : Graphs and Graph Algorithms

🕸️ 그래프란?

🗺️ 그래프 구현

Vertex 구현

Edge 구현

그래프 구현

그래프 탐색

최단 거리 구하기

Topological Sorting (위상 정렬)

📚 Reference

'🪲 debug' 카테고리의 다른 글

'🪲 debug' Related Articles

티스토리툴바