그래프 자료구조 구현

위와 같이 vertex(정점)과 edge(정점간의 연결하는 선)으로 구성되어 있는 자료구조를 그래프라고 부릅니다. 그래프 자료구조는 방향성 유무, 무게 유무, 그래프 모양 등에 따라 달라지기 때문에 여러 종류가 있습니다. 또한 다양한 모습의 그래프 자료구조 덕분에 최단거리를 통해 목적을 도달하기 위한 알고리즘,  최소한의 가중치로 목적에 이동하는 알고리즘 등 필요한 목적에 따라 구현한 알고리즘들도 많습니다.  이번 글을 통해 그래프의 기본용어, 자바스크립트를 통한 그래프 구현을 정리해보았습니다.

그래프 기본용어

• vertex (정점) : 위 그림의 a, b, c 등의 노드를 부름
• edge (간선): 노드 a와 노드 b를 연결하는 선을 부름
• degree of vertex (차수): 노드의 간선 개수. 노드 a의 차수는 2, 노드 c의 차수는 4
• weight(가중치): 간선에 대한 값. ex) 노드 a에서 노드 b로 가는데 비용/시간 등의 값
• path(경로): 노드 a에서 시작하여 노드 e로 끝나는 여정/방문/순회. 여러개의 경로가 존재할 수 있음
• incident (부속/근접/결합): 두 edge(간선)가 하나의 노드를 공유하고 있으면 incident라고 표현. 서로 연결된 간선을 지칭
• adjacent(인접): 두 vertex(정점)가 특정 간선으로 연결되어 있으면 adjacent라고 표현. 서로 연결된 노드를 지칭

그래프의 종류

방향의 유무에 따라 무방향 그래프와 방향 그래프로 나누어집니다

 

가중치의 유무에 따라 가중치 그래프와 비 가중치 그래프로 나누어집니다.

무방향 가중치 그래프

정점과 간선 추가

class UndirectedGraph {
  constructor() {
    this.edges = {};
  }

  // 정점 추가하기
  addVertex(vertex) {
    this.edges[vertex] = {};
  }

  // 간선 추가하기
  addEdge(vertex1, vertex2, weight) {
    if (weight === undefined) {
      weight = 0;
    }
    this.edges[vertex1][vertex2] = weight;
    this.edges[vertex2][vertex1] = weight;
  }
}

const graph1 = new UndirectedGraph();
graph1.addVertex("a");
graph1.addVertex("b");
graph1.addVertex("c");
graph1.addVertex("d");
graph1.addVertex("e");
graph1.addVertex("f");

graph1.addEdge("a", "b", 3);
graph1.addEdge("a", "d", 1);
graph1.addEdge("b", "c", 2);
graph1.addEdge("b", "f", 3);
graph1.addEdge("c", "d", 1);
graph1.addEdge("c", "f", 1);
graph1.addEdge("c", "e", 2);
graph1.addEdge("e", "f", 5);

console.log(graph1.edges);
// {
//   a: { b: 3, d: 1 },
//   b: { a: 3, c: 2, f: 3 },
//   c: { b: 2, d: 1, f: 1, e: 2 },
//   d: { a: 1, c: 1 },
//   e: { c: 2, f: 5 },
//   f: { b: 3, c: 1, e: 5 }
// }

1. 정점 추가

// 정점 추가하기
addVertex(vertex) {
  this.edges[vertex] = {};
}

• 위의 코드를 통해 a: {}, b: {} 등 그래프의 정점들을 객체로 나타냅니다.

 

2. 간선 추가

// 간선 추가하기
addEdge(vertex1, vertex2, weight) {
  if (weight === undefined) {
    weight = 0;
  }
  this.edges[vertex1][vertex2] = weight;
  this.edges[vertex2][vertex1] = weight;
}

• 위 코드를 통해 a 노드에서 b의 노드로 연결한 간선과 해당 간선의 무게를 나타냅니다.
• a: {b: 3}은 a노드에서 b노드가 연결된 간선 및 간선의 무게(3)를 나타냅니다.
• 무방향 그래프의 경우 두 방향 서로 연결되기에 반대 방향도 같이 추가합니다. b: {a: 3}
• 만약에 비 무게 그래프의 경우 weight 값을 주지 않아도 0으로 나타납니다. a: {b: 0}

정점과 간선 삭제

위 class와 연결...

// 간선 삭제하기
removeEdge(vertex1, vertex2) {
  if (this.edges[vertex1] && this.edges[vertex1][vertex2] !== undefined) {
    delete this.edges[vertex1][vertex2];
  }
  if (this.edges[vertex2] && this.edges[vertex2][vertex1] !== undefined) {
    delete this.edges[vertex2][vertex1];
  }
}

// 정점 삭제하기
removeVertex(vertex) {
  for (let adjacentVertex in this.edges[vertex]) {
    this.removeEdge(adjacentVertex, vertex);
  }
  delete this.edges[vertex];
}

graph1.removeVertex("f");
graph1.removeVertex("e")
graph1.removeVertex("c");
graph1.removeEdge("b", "a");

console.log(graph1.edges);
// { 
//  a: { d: 1 }, 
//  b: {}, 
//  d: { a: 1 } 
// }

1. 간선 삭제

// 간선 삭제하기
removeEdge(vertex1, vertex2) {
  if (this.edges[vertex1] && this.edges[vertex1][vertex2] !== undefined) {
    delete this.edges[vertex1][vertex2];
  }
  if (this.edges[vertex2] && this.edges[vertex2][vertex1] !== undefined) {
    delete this.edges[vertex2][vertex1];
  }
}

• 정점의 존재유무와 간선의 존재유무를 확인합니다. 만약에 있으면 해당 간선을 삭제합니다
• 무방향 그래프의 경우 두 방향 서로 연결되기에 반대 방향도 같이 삭제합니다

 

2. 정점 삭제

// 정점 삭제하기
removeVertex(vertex) {
  for (let adjacentVertex in this.edges[vertex]) {
    this.removeEdge(adjacentVertex, vertex);
  }
  delete this.edges[vertex];
}

• 정점을 지우기 전에 해당 정점과 연결된 간선들을 모두 지웁니다.
• 삭제할 정점에 연결된 간선들은 기존에 만든 removeEdge() 함수를 통해 지웁니다.
• 간선들을 다 지운 후 delete를 통해 해당 정점 객체를 삭제합니다.

방향 가중치 그래프

방향 그래프와 무방향 그래프의 구현은 크게 다르지 않습니다.

무방향의 경우 addEdge와 removeEdge에서 하나의 간선이 두 방향을 나타내기에 동시에 두 방향을 추가/삭제 했지만,

방향의 경우에는 어디에서 시작하여 어디로 갔는지의 하나의 방향의 간선만 추가하면 됩니다.

간선과 정점 추가

// 간선 추가하기
addEdge(originVertex, destinationVertex, weight) {
  if (weight === undefined) {
    weight = 0;
  }
  this.edges[originVertex][destinationVertex] = weight;
}

• originVertex(시작 정점)에서 destinationVertex(도착 정점)을 구현하면 됩니다.

간선과 정점 삭제

// 간선 삭제하기
removeEdge(originVertex, destinationVertex) {
  if (this.edges[originVertex] && this.edges[originVertex][destinationvertex] !== undefined) {
    delete this.edges[originVertex][destinationVertex];
  }
}

• 방향 그래프는 하나의 방향을 나타내는 간선을 삭제하면 됩니다.

무방향 비가중치 그래프

가중치가 없이 그래프 자료구조를 다시 구현했습니다. 무게를 따로 표시하지 않아도 되기에 그래프의 관계를 오브젝트와 배열을 활용하여 나타냈습니다.

class UndirectedGraph2 {
  constructor() {
    this.edges = {};
  }

  // 정점 추가하기
  addVertex(vertex) {
    this.edges[vertex] = [];
  }

  // 간선 추가하기
  addEdge(vertex1, vertex2) {
    this.edges[vertex1].push(vertex2);
    this.edges[vertex2].push(vertex1);
  }

  // 간선 삭제하기
  removeEdge(vertex1, vertex2) {
    if (this.edges[vertex1]) {

      let index1 = this.edges[vertex1].indexOf(vertex2);
      if (index1 != -1) {
        this.edges[vertex1].splice(index1, 1);
      }

      let index2 = this.edges[vertex2].indexOf(vertex1);
      if (index2 != -1) {
        this.edges[vertex2].splice(index2, 1);
      }
    }
  }

  // 정점 삭제하기
  removeVertex(vertex) {
    let connectedVertex = [...this.edges[vertex]]
    for (let adjacentVertex of connectedVertex) {
      this.removeEdge(adjacentVertex, vertex);
    }
    delete this.edges[vertex];
  }
}

 

틀은 크게 변화하지 않습니다만 배열 관련 메서드를 활용하여 필요한 곳들을 바꾼 것을 확인할 수가 있습니다.

 

객체를 생성하여 확인해 보시면 정상적으로 작동하는 것을 확인할 수가 있습니다!

const graph1 = new UndirectedGraph2();
graph1.addVertex("a");
graph1.addVertex("b");
graph1.addVertex("c");
graph1.addVertex("d");
graph1.addVertex("e");
graph1.addVertex("f");

graph1.addEdge("a", "b");
graph1.addEdge("a", "d");
graph1.addEdge("b", "c");
graph1.addEdge("b", "f");
graph1.addEdge("c", "d");
graph1.addEdge("c", "f");
graph1.addEdge("c", "e");
graph1.addEdge("e", "f");
console.log(graph1.edges);
// {
//   a: [ 'b', 'd' ],
//   b: [ 'a', 'c', 'f' ],
//   c: [ 'b', 'd', 'f', 'e' ],
//   d: [ 'a', 'c' ],
//   e: [ 'c', 'f' ],
//   f: [ 'b', 'c', 'e' ]
// }

graph1.removeVertex("f");
graph1.removeVertex("e")
graph1.removeVertex("c");
graph1.removeEdge("b", "a");
console.log(graph1.edges);
// { 
//   a: [ 'd' ], 
//   b: [], 
//   d: [ 'a' ] 
// }

 

참고자료

• http://www.ktword.co.kr/test/view/view.php?m_temp1=4725

그래프 용어

• https://makemethink.tistory.com/141#:~:text=%EA%B0%81%20%EB%B2%84%ED%85%8D%EC%8A%A4%EA%B0%80%20%EC%84%9C%EB%A1%9C%20%EC%97%B0%EA%B2%B0,%ED%95%98%EA%B3%A0%20%EC%9E%88%EB%8B%A4%EB%A9%B4%20incident%20%ED%95%98%EB%8B%A4%EA%B3%A0%20%EB%A7%90%ED%95%9C%EB%8B%A4.

[자료구조] 12-2. 그래프의 용어

• https://nyang-in.tistory.com/231

[자료구조] 그래프 (자바스크립트/javascript)