[11] [알고리즘 - 자료구조] 그래프(graph)란? (비선형구조) javascript 구현

그래프란?

 

https://terms.naver.com/entry.naver?docId=4383213&cid=59941&categoryId=59941

자료 간의 관계가 망구조와 같이

복잡한 경우에 사용하며,

연결되어 있는 정점과 정점 간의 관계를

표현할 수 있는 자료구조입니다.

 

트리와 그래프의 차이점을 살펴보면

그래프는 루트 노드가 존재하지 않고,

방향 또는 무방향 그래프가 모두 존재합니다.

 

예시로 위 사진과 같은 최단 경로를 예시로 들 수 있습니다.

 

 

그래프는 vertex와 edge로 구성됩니다.

 

 

 

그래프는 대표적으로

위와 같은 종류의 그래프가 있습니다.

 

무방향 그래프 - 방향이 없는 그래프.

방향 그래프 - 정점 간의 간선이 방향을 갖고 있는 그래프.

가중치 그래프 - 정점 간의 간선에 가중치를 부여한 그래프.

순환 그래프 - 순환이 존재하는 그래프.

비순환 그래프 - 순환이 없는 그래프.

 

---

그래프 표현 방법

 

인접 행렬 (Adjacency Matrix)

2차원 배열에 각 노드가

연결된 형태를 표현하는 방식입니다.

구현이 빠르고 검색속도가 빠르나,

2차원 배열의 공간이 필요하여

낭비가 비교적 심하다는

특징을 가지고 있습니다.

 

인접 리스트(Adjacency List)

모든 노드에 연결된 노드에 대한 정보를

연결 리스트로 표현하는 방식입니다.

 

 

공간의 낭비가 효율 적이지만

조회의 시간이 오래걸리고,

구현이 비교적 어렵다는

특징을 가지고 있습니다.

 

 

---

그래프 탐색 방법

그래프 탐색 방법으로는

대표적으로

깊이 우선 검색(Depth-First Search),

너비 우선 검색(Breadth-First Search)

가 존재합니다.

 

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 검색(DFS)은

한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고

끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색.

쉽게 말해서

하나의 깊이를 계속 파고들면서

검색하는 방법입니다.

Stack을 이용해서 구현합니다.

 

 

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

너비 우선 검색(BFS)은

하나로 시작 정점을 방문한 후

시작 정점에 인접한 모든 정점들을

우선 방문하는 방법

쉽게말해서

트리의 레벨 단위로 검색하는 방법입니다.

Queue를 이용해서 구현합니다.

 

 

---

 

Javascript 구현

 

인접 리스트 그래프로 구현해보겠습니다.

 

class AdjacencyListGraph {
    constructor() {
        this.list = {};
    }

    // 정점 추가
    addVertex(v) {
        this.list[v] = [];  //  "v" : []   > map 과 같은 키와 밸류 형태
    }

    // 간선 추가
    addEdge(v, w) {
        this.list[v].push(w);
        this.list[w].push(v); // 무방향 그래프 경우 양쪽 추가용
    }

    // 인접 리스트 그리기
    print() {
        let keys = Object.keys(this.list);
        for (let i = 0; i < keys.length; i++) {
            let value = this.list[keys[i]];
            let result = "";
            for (let j of value) result += j + " ";
            console.log(keys[i] + " -> " + result);
        }
    }

    // Depth-First Search 깊이우선탐색
    dfs(startingNode) {

        let visited = {}; // 방문 기록

        const search = (node, visited) => {
            visited[node] = true;

            // 인접 vertex 가져오기
            let getNeighbours = this.list[node];

            for (let i in getNeighbours) {
                let getNode = getNeighbours[i];
                // 깊이 탐색
                if (!visited[getNode]) search(getNode, visited);
            }
        }

        search(startingNode, visited);
        console.log('DFS = ', Object.keys(visited).join(" => "));
    }

    // Breath-First Search 너비우선탐색
    bfs(startingNode) {

        let visited = {};
        let result = []; // 순서 기록

        let q = new Queue();

        visited[startingNode] = true;
        q.in(startingNode);

        while (!q.isEmpty()) {
            let getQueueElement = q.out();
            result.push(getQueueElement);

            let getList = this.list[getQueueElement];

            for (let i in getList) {
                let neigh = getList[i];

                if (!visited[neigh]) {
                    visited[neigh] = true;
                    q.in(neigh);
                }
            }
        }

        console.log("BFS =  ", result.join(" -> "));
        // A B D E C F
    }
}

 

이제 바로 실행 결과를 확인해보겠습니다.

 

이러한 그래프를 탐색해보죠!

 

var graph = new AdjacencyListGraph();
var vertices = ['A', 'B', 'C', 'D', 'E'];

for (var i = 0; i < vertices.length; i++) {
    graph.addVertex(vertices[i]);
}

graph.addEdge('A', 'B');
graph.addEdge('A', 'E');
graph.addEdge('A', 'C');
graph.addEdge('B', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'D');
graph.addEdge('D', 'E');

graph.print();
// A -> B E C 
// B -> A C D 
// C -> A B D
// D -> B C E
// E -> A D

// DFS
graph.dfs('A');
// DFS =  A => B => C => D => E

// BFS
graph.bfs('A');
// BFS =   A -> B -> E -> C -> D

 

잘 확인되었나요??

 

점점 어려워지는 자료구조..

다양한 케이스로 다양하게 접해봐야 할 것 같습니다. ㅠㅠ

 

 

[12] [알고리즘 - 자료구조] 파일구조란? 순차파일, 색인파일, 직접파일