[Javascript] 그래프

이번에 구현할 자료구조는 그래프입니다. 그래프는 트리와 비슷하면서도 다른 성질의 자료구조 입니다.

2021.10.04 - [Programming/자료구조] - 그래프 Graph

그래프 Graph

2021.10.05 - [Programming/자료구조] - 그래프 구현2 - 인접 리스트로 그래프 구현하기

그래프 구현2 - 인접 리스트로 그래프 구현하기

 

마찬가지로 인접 리스트(연결 리스트)를 이용해서 방향 그래프를 구현해보겠습니다.

class Vertex {
    constructor(key) {
        this.nextVertex = null;
        this.edge = null;
        this.key = key;
    }
}

class Edge {
    constructor(data, destination) {
        this.nextEdge = null;
        this.data = data;
        this.destination = destination;
    }
}

class Graph {
    constructor() {
        this.size = 0;
        this.firstVertex = null;
    }

    //노드 삽입
    insertVertex(key) {
        const newVertex = new Vertex(key);
        //삽입 위치 직전의 노드 위치를 담은 변수 last
        let last = this.firstVertex;

        //빈 그래프이면 새 노드를 첫 노드로 삽입
        if (last === null) {
            this.firstVertex = newVertex;
        }
        else {
            //노드의 다음 노드가 null인 노드를 찾는 과정
            while (last.nextVertex !== null) {
                last = last.nextVertex;
            }
            //찾았다면 해당 노드의 다음 노드로 새 노드 삽입
            last.nextVertex = newVertex;
        }
        this.size++;
    }

    //간선 삽입
    insertEdge(data, tail, head) {
        let tailVertex = this.firstVertex;	//간선의 시작부분 노드
        let headVertex = this.firstVertex;	//간선의 도착부분 노드

        //삽입위치의 시작과 도착부분을 찾는 과정
        while (tailVertex && tailVertex.key !== tail) {
            tailVertex = tailVertex.nextVertex;
        }
        while (headVertex && headVertex.key !== head) {
            headVertex = headVertex.nextVertex;
        }

        if (tailVertex === null || headVertex === null) {
            return false;
        }

        const newEdge = new Edge(data, headVertex);
        let lastEdge = tail.edge;

        //시작부분 노드의 간선이 비어있지 않다면
        if (lastEdge !== null) {
            //빈 간선을 찾고 그곳에 삽입
            while (lastEdge.nextEdge !== null) {
                lastEdge = lastEdge.nextEdge;
            }
            lastEdge.nextEdge = newEdge;
        }
        else {
            tail.edge = newEdge;
        }
    }
}

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/data-structure/Graph.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록