Graph Data Structure

About Graph

그래프는 Vertex(점:노드) 와 Edge(간선) 로 구성된다.

점과 점사이를 이어주는 역할을 선이 하게 되는데 선에 방향이 없을경우

무향 그래프(Undirected graph) 방향이 있으면 유향 그래프(Directed graph)

라고 부른다. 간선의 경우엔 가중치(Weighted value) 를 가질수 있다.

Adjacency List

간선에 가중치는 그래프의 이동경로를 포함하고 있다.

간선을 표현하는데에는 2가지 방식을 사용할수 있는데

인접 행렬과 인접 리스트 방식이 있다. 결론적으로 인접 리스트를 사용하는것이

좋은데 인접 행렬의 문제에 대해서 이야기 해보겠다.

인접 행렬 방식은 Matrix 즉 2차원 배열 형식을 가지고 있다.

그렇기 때문에 특정 노드와 연결된 노드를 찾기위해서 모든 노드를 찾아야한다.

노드가 많아지면 쓸대없는 방문이 늘어나게 된다. (시간복잡도가 증가한다)

그래프는 노드가 많을수밖에 없다. 그래서 인접 리스트를 사용하는데

LinkedList 나 Vector를 사용하여 구현하면 큰 어려움이 없다.

Topological Sorting

위상 정렬은 유향 그래프의 노드들이 간선의 방향을 거스르지 않도록 나열하는것

을 의미한다.

위상 정렬은 DAG(Directed Acyclic Graph) 에서 사용이 가능한데 약어가 말해주다 싶이

위상 정렬의 선제 조건은 유향그래프 이면서 노드가 순환되는것이 없어야 한다는것이다.

위상 정렬은 여러 가지 일들에 순서가 정해져 있을때 순서에 맞게끔 나열하는 것을

의미한다.

implemantation

class Graph {
    constructor() {
        this.vertices = [];
        this.adjList  = [];
    }

    addVertex(vertex) {
        this.vertices.push(vertex);
        this.adjList[vertex] = [];
    }

    addEdge(start, end) {
        this.adjList[start].push(end);
        this.adjList[end].push(start);

    }

    toString() {
        let str = '\n',
            len = this.vertices.length;

        for (let i = 0; i < len; i+=1) {
            str += `${this.vertices[i]} -> `;
            let nb = this.adjList[this.vertices[i]];
            for (let j = 0; j < nb.length; j+=1) {
                str += `${nb[j]} `;
            }
            str += '\n';
        }
        return str;
    }

}

var graph = new Graph();
Array.from(new Array(9), (v,i) => graph.addVertex(String.fromCharCode(i+65)));
graph.addEdge('A', 'B'); 
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

graph.toString();
/*
A -> B C D 
B -> A E F 
C -> A D G 
D -> A C G H 
E -> B I 
F -> B 
G -> C D 
H -> D 
I -> E
*/

A~I 까지 알파벳을 노드로 만들고 간선을 연결해서 출력한 결과이다.

그래프의 기본 형태이며 이 코드로 그래프의 검색을 진행해 보겠다.

Graph Traversals

그래프 검색은 깊이우선 검색(DFS)과 너비 우선 검색(BFS)으로 나뉜다.

DFS에서는 Stack을 BFS에서는 Queue 자료구조를 활용하지만 자바스크립트 배열이 가진

특성으로 모두 구현 가능 하기때문에 따로 클래스를 가져와 쓰진 않을것이다.

정석대로 하자면 앞서 설명했던 Dictionary , LinkedList, Stack, Queue 클래스를 모두 가져와서 써야한다.

먼저 구현에 앞서 검색할 대상과 검색 유무에 대한 식별이 필요하다.

규칙은 다음과 같다.

• 검색전에 아직 방문하지 않은 노드는 white 으로 표기한다.
• 방문 타겟이 되는 노드는 gray 으로 표기한다.
• 방문이 완료된 타겟은 black 으로 표기한다.

function initMark() {
    let color = [];
    for (var i = 0; i < this.vertices.length; i+=1) {
        color[this.vertices[i]] = 'white'; 
    }
    return color;
}

BFS (Breadth-frist search) :너비 우선 검색

function bfs(v) {
    let mark  = this.initMark(),
        queue = [];

        queue.push(v);
        while (!queue.length === 0) {
            let u  = queue.shift(),
                nb = this.adjList[u];
            mark[u] = 'gray';

            for (let i = 0; i < nb.length; i+=1) {
                 let w = nb[i];
                 if (mark[w] === 'white') {
                     mark[w] = 'gray';
                     queue.push(w);
                 }
            }
            mark[u] = 'black';
            console.log(`Visited ${u}`);
        }
}

Finding the shortest paths using BFS : BFS로 최단경로 구하기

function sbfs(target) {
    let mark  = this.initMark(),
        queue = [],
            d = [],
         pred = [];

         queue.push(target);

         for (let i = 0; i < this.vertices.length; i+=1) {
               d[this.vertices[i]] = 0;
            pred[this.vertices[i]] = null;
         }

         while (!queue.length === 0) {
            let u  = queue.shift(),
                nb = this.adjList[u];
                mark[u] = 'gray';

                for (let i = 0; i < nb.length; i+=1) {
                    let w = nb[i];
                    if (mark[w] === 'white') {
                        mark[w] = 'gray';
                           d[w] = d[u] + 1;
                        pred[w] = u;
                        queue.push(w);
                    }
                } 
                mark[u] = 'black';
         }
        //output
        for (let i = 1; i < this.vertices.length; i+=1) {
               let toVertex = this.vertices[i],
                   path = [];
                   for (let j = toVertex; j !== target; j = pred[j]) {
                        path.push(j);
                   }
                   path.push(target);
                   let str = path.pop();
                   while (!path.length === 0) {
                     str += ` - ${path.pop()}`;
                   }    
         console.log(str);
        }        
}    

DFS (Depath-frist search) :깊이 우선 검색

function dfs(v) {
       let mark = this.initMark();

       for (let i = 0; i < this.vertices.length; i+=1) {
            if(mark[this.vertices[i]] === 'white') {
                this.dfs_re(this.vertices[i], mark); //recursion
            }
       }
}

function dfs_re(u, mark) {
        mark[u] = 'gray';

        let nb = this.adjList[u];
        for (let j = 0; j < nb.length; j+=1) {
            let w = nb[i];
            if (mark[w] === 'white') {
                this.dfs_re(w, mark); //recursion
            }
        }
        mark[u] = 'black';
        console.log(`Visited ${u}`);
}

Exploring the DFS algorithm : 깊이 우선 검색 출력

function exp_dfs() {
       let [mark, d, f, p] = [this.initMark(), [], [], []];
       this.time = 0;

       for (let i = 0; i < this.vertices.length; i+=1) {
            d[this.vertices[i]] = 0;
            f[this.vertices[i]] = 0;
            p[this.vertices[i]] = null;
       } 

       for (let i = 0; i < this.vertices.length; i+=1) {
            if(mark[this.vertices[i]] === 'white') {
                this.exp_dfs_re(this.vertices[i], mark, d, f, p); //recursion
            }
       }
       return { discovery: d, finished: f, predecessors: p };
}

function exp_dfs_re(u, mark, d,f,p) {
        mark[u] = 'gray';
           d[u] = ++this.time;

        let nb = this.adjList[u];
        for (let j = 0; j < nb.length; j+=1) {
            let w = nb[i];
            if (mark[w] === 'white') {
                p[w] = u;
                this.exp_dfs_re(w, mark, d, f, p); //recursion
            }
        }
        mark[u] = 'black';
        f[u] = ++this.time;
        console.log(`Explored ${u}`);
}

Completed Code

class Graph {
    constructor() {
        this.vertices = [];
        this.adjList  = [];
        this.time = 0; //dfs
    }

    addVertex(vertex) {
        this.vertices.push(vertex);
        this.adjList[vertex] = [];
    }

    addEdge(start, end) {
        this.adjList[start].push(end);
        this.adjList[end].push(start);

    }

    toString() {
        let str = '\n',
            len = this.vertices.length;

        for (let i = 0; i < len; i+=1) {
            str += `${this.vertices[i]} -> `;
            let nb = this.adjList[this.vertices[i]];
            for (let j = 0; j < nb.length; j+=1) {
                str += `${nb[j]} `;
            }
            str += '\n';
        }
        return str;
    }

    initMark() {
        let color = [];
        for (let i = 0; i < this.vertices.length; i+=1) {
            color[this.vertices[i]] = 'white'; 
        }
        return color;
    }

    bfs(v) {
        let mark  = this.initMark(),
            queue = [];

            queue.push(v);
            while (queue.length !== 0) {
                let u  = queue.shift(),
                    nb = this.adjList[u];
                mark[u] = 'gray';
                for (let i = 0; i < nb.length; i+=1) {
                     let w = nb[i];
                     if (mark[w] === 'white') {
                         mark[w] = 'gray';
                         queue.push(w);
                     }
                }
                mark[u] = 'black';
                console.log(`Visited ${u}`);
            }
    }

    sbfs(target) {
        let mark  = this.initMark(),
            queue = [],
                d = [],
             pred = [];

             queue.push(target);

             for (let i = 0; i < this.vertices.length; i+=1) {
                   d[this.vertices[i]] = 0;
                pred[this.vertices[i]] = null;
             }

             while (queue.length !== 0) {
                let u  = queue.shift(),
                    nb = this.adjList[u];
                    mark[u] = 'gray';

                    for (let i = 0; i < nb.length; i+=1) {
                        let w = nb[i];
                        if (mark[w] === 'white') {
                            mark[w] = 'gray';
                               d[w] = d[u] + 1;
                            pred[w] = u;
                            queue.push(w);
                        }
                    } 
                    mark[u] = 'black';
             }

            for (let i = 1; i < this.vertices.length; i+=1) {
                   let toVertex = this.vertices[i],
                       path = [];
                       for (let j = toVertex; j !== target; j = pred[j]) {
                            path.push(j);
                       }
                       path.push(target);
                       let str = path.pop();
                       while (path.length !== 0) {
                         str += ` - ${path.pop()}`;
                       }    
             console.log(str);
            }        
    }

    dfs(v) {
       let mark = this.initMark();

       for (let i = 0; i < this.vertices.length; i+=1) {
            if(mark[this.vertices[i]] === 'white') {
                this.dfs_re(this.vertices[i], mark); //recursion
            }
       }
    }

    dfs_re(u, mark) {
        mark[u] = 'gray';

        let nb = this.adjList[u];
        for (let j = 0; j < nb.length; j+=1) {
            let w = nb[i];
            if (mark[w] === 'white') {
                this.dfs_re(w, mark); //recursion
            }
        }
        mark[u] = 'black';
        console.log(`Visited ${u}`);
    }    

    exp_dfs() {
       let [mark, d, f, p] = [this.initMark(), [], [], []];

       for (let i = 0; i < this.vertices.length; i+=1) {
            d[this.vertices[i]] = 0;
            f[this.vertices[i]] = 0;
            p[this.vertices[i]] = null;
       } 

       for (let i = 0; i < this.vertices.length; i+=1) {
            if(mark[this.vertices[i]] === 'white') {
                this.exp_dfs_re(this.vertices[i], mark, d, f, p); //recursion
            }
       }
       return { discovery: d, finished: f, predecessors: p };
    }

    exp_dfs_re(u, mark, d,f,p) {
        mark[u] = 'gray';
           d[u] = ++this.time;

        let nb = this.adjList[u];
        for (let j = 0; j < nb.length; j+=1) {
            let w = nb[i];
            if (mark[w] === 'white') {
                p[w] = u;
                this.exp_dfs_re(w, mark, d, f, p); //recursion
            }
        }
        mark[u] = 'black';
        f[u] = ++this.time;
        console.log(`Explored ${u}`);
    }
}

성능 테스트는 performance 를 활용하면 되는데 이부분은 따로 포스팅 할 예정이다.