[비선형] 4. 그래프

in 자료구조 on 비선형




1. 그래프 (Graph)

  • 정점과 간선으로 구성되어 네트워크 구조를 추상화한 비선형 자료 구조
  • 정점(Vertex)과 간선(Edge)의 집합
  • 다양한 그래프 종류를 혼합하여 표현 가능
  • 길찾기, 게임, 지도, 네비게이션, 네트워크 채팅


그래프 종류

그래프

그래프

  • 방향 그래프 (Directed Graph) : 간선에 특정 방향이 존재하는 그래프 (A -> B로 표현, A에서 B로만 이동 가능)
  • 무방향 그래프 (Undirected Graph) : 간선에 특정 방향이 존재하지 않는 그래프 (A - B로 표현, 양방향 이동 가능)
  • 가중치 그래프 (Weighted Graph) : 간선에 비용이나 가중치가 할당된 그래프
  • 연결 그래프 (Connected Graph) : 무방향 그래프에 있는 모든 정점쌍에 대해 항상 경로가 존재하는 그래프
  • 비연결 그래프 (Disconnected Graph) : 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 그래프
  • 순환 그래프 (Cycle) : 단순 경로의 시작 정점과 종료 지점이 동일하여 순환 지점이 존재하는 그래프
  • 비순환 그래프 (Acyclic Graph) : 순환 지점이 존재하지 않는 그래프
  • 완전 그래프 (Commplete Graph) : 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프


그래프 표현 방법


그래프

  • 인접 리스트 (Adjacency List) : 정점에 연결된 다른 정점을 리스트로 표현
  • 인접 행렬(Adjacency Matrix) : 정점에 연결된 다른 정점은 정점x정점 크기의 매트릭스로 표현


구현 메서드

  • 정점/간선 추가 : Graph.addVertex(), Graph.addEdge()
  • 정점/간선 삭제 : Graph.removeVertex(), Graph.removeEdge()
  • 정점/간선 개수, 그래프 출력 : Graph.sizeVertex(), Graph.sizeEdge(), Graph.print()



2. 그래프 구현하기


그래프

생성자, addVertex(), addEdge()

// 방향 그래프
// Graph() : edge object 객체 저장을 위한 생성자
// key : 정점 (vertex)
// value : list 형태로 연결된 vertex를 표현하여 edge 연결 관계 표현
function Graph(){
    this.edge = {}
    // 객체에 key-value 로 저장
}

// addVertex() : 정점(vertex) 추가
Graph.prototype.addVertex = function (v) {
    this.edge[v] = []
}

// addEdge() : 간선(edge) 추가
Graph.prototype.addEdge = function (v1, v2){
    this.edge[v1].push(v2)
}

let graph = new Graph()
let vertices = ["A", "B", "C", "D", "E", "F"]

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

graph.addEdge("A", "B")
graph.addEdge("A", "C")
graph.addEdge("A", "D")
graph.addEdge("B", "E")
graph.addEdge("B", "F")
graph.addEdge("C", "G")
graph.addEdge("D", "G")
graph.addEdge("D", "H")
graph.addEdge("E", "I")

console.log(graph.edge)
// {
//     A: [ 'B', 'C', 'D' ],
//     B: [ 'E', 'F' ],
//     C: [ 'G' ],
//     D: [ 'G', 'H' ],
//     E: [ 'I' ],
//     F: []
//   }



removeEdge(), removeVertex()

// removeEdge() : 간선(edge) 삭제
Graph.prototype.removeEdge = function (v1, v2) {
  if (this.edge[v1]) {
    let idx = this.edge[v1].indexOf(v2);

    if (idx != -1) {
      this.edge[v1].splice(idx, 1);
    }

    if (this.edge[v1].length === 0) {
      delete this.edge[v1];
    }
  }
};

// removeVertex() : 정점(vertex) 삭제
Graph.prototype.removeVertex = function (v) {
  if (this.edge[v] === undefined) return;

  let length = this.edge[v].length;
  let connectedVertex = [...this.edge[v]];

  for (let i = 0; i < length; i++) {
    this.removeEdge(v, connectedVertex[i]);
  }
};

let graph = new Graph();
let vertices = ["A", "B", "C", "D", "E", "F"];

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

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("B", "E");
graph.addEdge("B", "F");
graph.addEdge("C", "G");
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("E", "I");

console.log(graph.edge);
// {
//     A: [ 'B', 'C', 'D' ],
//     B: [ 'E', 'F' ],
//     C: [ 'G' ],
//     D: [ 'G', 'H' ],
//     E: [ 'I' ],
//     F: []
//   }

graph.removeEdge("B", "E");
console.log(graph.edge); //B: [ 'F' ],
graph.removeEdge("B", "F");
console.log(graph.edge); //B 사라짐

graph.removeVertex("D")
console.log(graph.edge); //{ A: [ 'B', 'C', 'D' ], C: [ 'G' ], E: [ 'I' ], F: [] }



sizeVertex(), sizeEdge(), print()

// sizeVertex() : vertex 개수 반환
Graph.prototype.sizeVertex = function () {
    return Object.keys(this.edge).length
};

// sizeEdge() : edge 개수 반환
Graph.prototype.sizeEdge = function (vertex) {
    return this.edge[vertex] ? Object.keys(this.edge[vertex]).length : 0
};

// print() : 현재 graph 연결 상태 출력
Graph.prototype.print = function (vertex) {
    for (let vertex in this.edge){
        let neighbors = this.edge[vertex]
        if (neighbors.length ==0) continue

        process.stdout.write(`${vertex} -> `)
        for (let i = 0; i<neighbors.length; i++){
            process.stdout.write(`${neighbors[i]} `)
        }

        console.log("")
    }
};


let graph = new Graph();
let vertices = ["A", "B", "C", "D", "E"];

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

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("B", "E");
graph.addEdge("B", "F");
graph.addEdge("C", "G");
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("E", "I");

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

graph.removeEdge("B", "E");
graph.print()
// A -> B C D 
// B -> F 
// C -> G 
// D -> G H 
// E -> I 

graph.removeEdge("B", "F");
graph.print()
// A -> B C D 
// C -> G 
// D -> G H 
// E -> I 

console.log(graph.sizeVertex()) //4
console.log(graph.sizeEdge("C")) //1
console.log(graph.sizeEdge("B")) //0



방향그래프 > 무방향그래프로 바꾸기

// addEdge() : 간선(edge) 추가
Graph.prototype.addEdge = function (v1, v2) {
  this.edge[v1].push(v2);
  this.edge[v2].push(v1);
};

// removeEdge() : 간선(edge) 삭제
Graph.prototype.removeEdge = function (v1, v2) {
    // v1 > v2 삭제
  if (this.edge[v1]) {
    let idx = this.edge[v1].indexOf(v2);

    if (idx != -1) {
      this.edge[v1].splice(idx, 1);
    }

    if (this.edge[v1].length === 0) {
      delete this.edge[v1];
    }
  }
  // v2 > v1 삭제
  if (this.edge[v2]) {
    let idx = this.edge[v2].indexOf(v1);

    if (idx != -1) {
      this.edge[v2].splice(idx, 1);
    }

    if (this.edge[v2].length === 0) {
      delete this.edge[v2];
    }
  }
};