Graph | 그래프

Edit on GitHub

그래프는 비선형 자료구조이다.

그래프 용어

그래프는 네트워크 구조를 추상화한 모델로 간선(edge)으로 연결된 노드(vertex)의 집합이다.

도로, 항로, 통신을 나타낼 때 그래프를 많이 사용한다.

그래프는 G = (V,E)로 구성되어 있다.

V: 정점의 집합

E: V의 정점들을 연결한 간선의 집합

간선으로 연결된 정점을 인접 정점이라고 한다.

인접 정점의 개수를 정점의 차수라고 한다.

경로는 일련의 연속된 정점이다.

단순 경로란 반복된 정점을 포함하지 않는 경로를 말한다.

사이클은 처음과 마지막 정점이 같은 단순 경로다.

사이틀이 없는 그래프를 비사이클 그래프라고 하고 모든 정점 간에 경로가 존재할 때 그래프는 연결되었다 라고 한다.

방향/무방향 그래프

간선들이 한쪽으로 방향을 가진 그래프를 방향그래프라 하며 반대로 무방향 그래프는 간선에 방향성이 없다.

두 정점이 양방향으로 경로를 갖고 있을 때 강결합되었다 고 한다.

지금까지는 가중치가 없는 그래프였는데 간선마다 가중치가 있는 그래프도 있다.

그래프 나타내기

인접 행렬

가장 일반적인 표현 방법은 인접 행렬로, 각 노드에 정수형 배열 인덱스를 세팅한다.

그리고 정점 간 연결 상태는 2차원 배열의 값으로 표시하는데, 배열[i][j] === 1은 인덱스 i인 노드와 인덱스 j인 노드 사이에 간선이 존재함을 의미하며

그 외에는 배열[i][j] === 0이다.

강결합이 아닌 그래프의 인접 행렬에는 0이 아주 많을 것이다.

즉 존재하지도 않는 간선을 표시하기 위해 컴퓨터 메모리를 쓸데없이 많이 점유한다.

그래서 어떤 정점의 인접 정점을 찾을 떄 이 정점에 이웃한 정점이 하나뿐인 경우에도 전체 행을 순회해야 하는 문제가 있다.

그래프의 정점 개수는 계속 변할 수 있는데다 2차원 배열 자체가 유연한 구조가 이나므로 인접 행렬은 효과적인 표현 방법이 아니다.

인접 리스트

동적 그래프 자료 구조는 인접 리스트로 표현한다.

인접 리스트는 각 정점별로 인접 정점들의 리스트를 저장하는데 이를 자료 구조로 표현하는 방법은 배열, 연결 리스트, 해시 맵, 딕셔너리 중 어느 것을 선택하느냐에 달라진다.

근접 행렬

근접 행렬은 그래프의 정점을 행으로, 간선은 열로 표시하고, 두 정점간 연결 상태는 2차원 배열로 나타내는 방법이다.

배열[v][e] === 1 은 정점 v가 간선 e에 근접해 있음을 의미하며 그 외에는 모두 배열[v][e] === 0이다.

보통 정점보다 간선이 상대적으로 많은 그래프에서 저장 공간과 메모리를 절약하기 위해 사용한다.

Graph 클래스 만들기

function Graph() {
  var vertices = [];
  var adjList = new Dictionaray(); // 이전 딕셔너리 설명했을때 사용한 클래스
}

정점의 명칭은 배열로, 인접 리스트는 딕셔너리로 각각 저장한다.

여기서 딕셔너리는 정점 명칭과 인접 정점 리스트를 키-값으로 갖는다.

vertices 배열, adjList 딕셔너리 모두 Graph 클래스의 프라이빗 프로퍼티다.

그래프에 정점을 추가하는 메서드와 정점 간 간선을 추가하는 메서드를 구현한다.

정점을 추가하는 addVertex 메서드다

this.addVertex = function(v) {
  vertices.push(v);
  adjList.set(v, []);
};

인자로 받은 정점 v를 배열에 넣고, 키가 v이고 값은 빈 배열인 딕셔너리를 인접 리스트로 세팅한다.

다음은 간선을 추가하는 addEdge 메서드다

this.addEdge = function(v, w) {
  adjList.get(v).push(w);
  adjList.get(w).push(v);
};

v와 w 두 정점을 받아서 우선 w를 v의 인접 리스트에 넣고 v -> w 방향으로 간선을 추가한다.

this.toString = function() {
  var s = "";
  for (var i = 0; i < vertices.length; i++) {
    s += vertices[i] + " -> ";
    var neighbors = adjList.get(vertices[i]);
    for (var j = 0; j < neighbors.length; j++) {
      s += neighbors[j] + " ";
    }
    s += "\n";
  }
  return s;
};

그래프 순회

트리처럼 그래프 역시 각 정점을 방문할 수 있다.

이러한 순환 알고리즘으로 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 두가지가 있다.

어떤 정점 또는 두 정점 사이의 경로를 찾거나 그래프가 연결되었는지 사이클이 존재하는지 확인할때 그래프를 순회한다.

그래프 순회는 처음 정점을 방문한 이후 아직 탐사할 정점이 남아 있는지 계속 추적하는 일이다.

BFS,DFS 모두 최초로 방문할 정점을 신중하게 정해야한다.

한 정점을 완전히 탐사하려면 이 정점에 연결된 간선들을 잘 살펴야 한다.

간선을 따라가면서 아직 방문하지 않은 정점은 방문 대상으로 표시하고 방문객 리스트에 추가한다.

BFS와 DFS 두 알고리즘 모두 기본 원리는 같지만, 방문을 마친 정점의 리스트를 저장하는 자료 구조가 다르다.

알고리즘	자료 구조	설명
DFS	스택	정점을 스택에 저장함으로써 경로를 따라 정점을 찾아가면서 인접 정점이 있으면 방문
BFS	큐	정점을 큐에 저장함으로써 가장 오래전에 방문하지 않은 정점을 가장 먼저 방문

이미 방문한 정점은 다음 세 가지 색깔로 상태를 표시한다.

흰색: 아직 방문하지 않은 정점

회색: 방문은 했으나 탐색하지 않은 정점

흑색: 탐색을 마친 정점

정점당 방문 횟수는 2회를 초과해선 안된다.

너비 우선 탐색(BFS)

시작 정점에서 순회를 시작해 그래프를 한 번에 한 층씩, 우선 이웃한 정점들을 모두 방문한다.

일단 너비 방향으로 먼저 방문하고 그 다음 깊이 방향으로 내려간다.

큐를 생성한다
v를 방문했음 을 표시하고 큐에 v를 추가한다.
큐는 비어 있지 않으므로 다음 과정을 밟는다.
1. u를 큐에서 삭제한다.
2. u를 방문했음 으로 표시한다.
3. u의 방문하지 않은 모든 인접 정점을 큐에 넣는다.
4. u를 탐색했음으로 표시한다

var initializeColor = function() {
  var color = [];
  for (var i = 0; i < vertices.length; i++) {
    color[vertices[i]] = "white";
  }
  return color;
};
this.bfs = function(v, callback) {
  var color = initializeColor(),
    queue = new Queue();
  queue.enqueue(v);
  while (!queue.isEmpty()) {
    var u = queue.dequeue(),
      neighbors = adjList.get(u);
    color[u] = "grey";
    for (var i = 0; i < neighbors.length; i++) {
      var w = neighbors[i];
      if (color[w] === "white") {
        color[w] = "grey";
        queue.enqueue(w);
      }
    }
    color[u] = "black";
    if (callback) {
      callback(u);
    }
  }
};

BFS, DFS 모두 정점을 마친 정점을 표시하기 위해 color라는 헬퍼 배열을 선언한다.

처음에 모든 정점을 방문하지 않은 상태이므로 색깔을 흰색으로 초기화하는 헬퍼 함수 initializeColor를 정의한다.

bfs 메서드는 알고리즘 출발 지점이 될 시작 정점 v를 인자로 받아 큐에 넣는다.

큐가 비어 있지 않다면 큐에서 맨 앞의 정점을 꺼내, 이 정점을 인접 리스트를 가져온다.

그리고 이 정점은 이미 방문했음이므로 색깔을 grey로 표시한다.

u의 인접 리스트를 순회하면서 추출한 각 인접 정점에 대해 아직 방문하지 않은 상태라면 방문했음으로 표시하고 큐에 추가한다.

이 정점의 탐색이 끝나면 이 큐에서 삭제된다.

해당 정점과 그 인접 정점 모두 확인 끝나면 탐색했음으로 표시한다.

BFS로 최단 경로 찾기

그래프 G의 시작 정점이 v일 떄 v와 u 간 최단 경로를 따라 v에서 각 정점 u I G까지의 거리를 구해보자

BFS 알고리즘으로 정점 v에서 거리가 1인 모든 정점을 방문한 다음, 거리가 2인 모든 정점을 방문하는 식으로 해결할 수 있다.

v에서 u까지의 거리: d[u]

v에서 다른 모든 정점 u까지의 최단 경로를 계산하기 위한 선행자 pred[u]

this.BFS = function(v) {
  var color = initializeColor(),
    queue = new Queue(),
    d = [],
    pref = [];
  queue.enqueue(v);
  for (var i = 0; i < vertices.length; i++) {
    d[vertices[i]] = 0;
    pred[vertices[i]] = null;
  }
  while (!queue.isEmpty()) {
    var u = queue.dequeue(),
      neighbors = adjList.get(u);
    color[u] = "gray";
    for (i = 0; i < neighbors.length; i++) {
      var w = neighbors[i];
      if (color[w] === "white") {
        color[w] = "gray";
        d[w] = d[u] + 1;
        pred[w] = u;
        queueu.enqueue(w);
      }
    }
    color[u] = "black";
  }
  return {
    distances: d,
    predecessors: pred
  };
};

거리를 나타내는 배열 d와 선행자를 나타내는 배열 pred를 차례로 선언한다.

그래프의 모든 정점에 대해 d는 0으로 pred는 null로 초기화한다.

정점 u의 인접 정점 w를 발견하면 w의 선행자를 u로 세팅하고 v와 w 사이의 거리를 1만큼 증가시킨다.

선행자 배열을 갖고 다음 코드를 돌리면 정점 A에서 다른 정점들까지의 경로를 알 수 있다.

var fromVertex = myVertices[0];
for (var i = 1; i < myVertices.length; i++) {
  var toVertex = myVertices[i],
    path = new Stack();
  for (var v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) {
    path.push(v);
  }
  path.push(fromVertex);
  var s = path.pop();
  while (!path.isEmpty()) {
    s += " - " + path.pop();
  }
  console.log(s);
}

시작 정점은 A이다. A를 제외한 다른 모든 정점에 대해 A로부터의 거리를 계산한다.

루프의 현재 정점을 toVertex에 담고 경로를 저장할 스택을 생성한다.

그리고 toVertext -> fromVertex 방향으로 경로를 따라간다. v에는 자신의 선행자가 세팅되므로 똑같은 경로를 다시 되돌아갈 수 있다.

이제 v를 경로 스택에 추가한다. 마지막으로 경로를 완성하기 위해 시작 정점 역시 스택에 넣는다.

문자열 변수 s를 선언하고 시작 정점을 꺼내 할당한다.

스택이 빈 상태가 될떄까지 스택에서 원소를 꺼내 s에 붙인다.

최단 경로 알고리즘 관련 보충

가중치 그래프에서 최단 경로를 계산할 때는 BFS는 무용지물이다.

단일 소스 최단 경로 문제는 다익스트라 알고리즘, 간선 가중치가 음의 값일 경우의 단일 소수 문제는 벨만-포트 알고리즘

검색 속도를 빠르게 하려면 휴리스틱을 이용해 정점의 단일 쌍에 대한 최단 경로를 찾는 A 검색 알고리즘,

모든 정점 간의 최단 경로를 찾는 플로이드-워셜 알고리즘도 있다.

깊이 우선 탐색

BFS 알고리즘은 시작 정점에서 출발해 동일 경로의 마지막 정점까지 순회하고 다시 반대 방향으로 돌아와 다음 경로를 찾아가는 식으로 진행된다.

일단 깊이 방향으로 정점들을 방문한 후 너비 방향으로 움직인다.

DFS에서는 시작 정점이 필요 없다. 그래프 G에서 미방문 상태의 정점 v를 차례로 방문한다.

v를 방문했음으로 표시한다.
방문하지 않은 v의 인접 정점 w에 대해 정점 w를 방문한다.
v를 탐색했음 으로 표시한다.

DFS는 단계별로 재귀 호출을 하며 그때그때 스택에 저장한다.

this.dfs = function(callback) {
  var color = initializeColor();
  for (var i = 0; i < vertices.length; i++) {
    if (color[vertices[i]] === "white") {
      dfsVisit(vertices[i], color, callback);
    }
  }
};
var dfsVisit = function(u, color, callback) {
  color[u] = "gray";
  if (callback) {
    callback();
  }
  var neighbors = adjList.get(u);
  for (var i = 0; i < neighbors.length; i++) {
    var w = neighbors[i];
    if (color[w] === "white") {
      dfsVisit(w, color, callback);
    }
  }
  color[u] = "black";
};

BFS와 마찬가지로, 모든 정점의 색깔을 white로 초기화한다.

그리고 Graph 인스턴스의 방문하지 않은 정점에 대해 루프를 돌며 프라이빗 함수 dfsVisit를 호출한다.

정점과 color 배열, callback 함수를 인자로 전달한다.

정점 u를 방문했으니 방문했음으로 표시하고 방문한 정점을 출력하는 callback 함수를 실행한다.

그 다음 u의 인접 리스트를 조회하고 방문하지 않은 u의 인접 정점 w에 대해 dfsVisit 함수를 재귀호출하면서 w와 기타인자를 넘긴다.

해당 정점과 인접 정점을 깊이 방향으로 모두 방문한 후에는 탐사가 모두 끝났으니 백트랙하고 색깔을 black으로 바꾼다.

DFS 알고리즘 탐구

DFS 알고리즘은 그래프 G의 모든 정점을 순회하면서 시작 정점 집합과 함께 포레스트를 형성하고

방문 시간과 탐색 시간을 배열로 출력한다.

u의 방문 시간: d[u]

u의 탐색 시간: f[u]

u의 선행자: p[u]

var time = 0;
this.DFS = function() {
  var color = initializeColor(),
    d = [],
    f = [],
    p = [];
  time = 0;
  for (var i = 0; i < vertices.length; i++) {
    f[vertices[i]] = 0;
    d[vertices[i]] = 0;
    p[vertices[i]] = null;
  }
  for (i = 0; i < vertices.length; i++) {
    if (color[vertices[i]] === "white") {
      DFSVISIT(vertices[i], color, d, f, p);
    }
  }
  return {
    discovery: d,
    finished: f,
    predecessor: p
  };
};
var DFSVISIT = function(u, color, d, f, p) {
  console.log("방문 " + u);
  color[u] = "gray";
  d[u] = ++time;
  var neighbors = adjList.get(u);
  for (var i = 0; i < neighbors.length; i++) {
    var w = neighbors[i];
    if (color[w] === "white") {
      p[w] = u;
      DFSVISIT(w, color, d, f, p);
    }
  }
  color[u] = "black";
  f[u] = ++time;
  console.log("탐색 " + u);
};

방문 시간과 탐색 시간을 추적하기 위해 시간을 나타내는 변수를 선언한다.

자바스크립트에서 객체가 아닌 변수는 다른 메서드에 레퍼런스로 전달할 수 없으므로 시간을 인자로 넘길 수 없다.

d,f,p 배열은 선언하고 그래프의 모든 정점에 대해 배열 값을 초기화한다.

이 세 배열은 메서드끝에서 다시 쓸 수 있게 반환한다.

정점 방문시, 방문 시간을 기록한다. u와 연결된 간선을 타고 방문한 것이라면 선행자 역시 추적한다.

탐색이 끝나면 탐색 시간을 기록한다.

DFS 알고리즘의 기본적인 아이디어는 가장 최근에 방문한 정점 u에서부터 간선들을 탐색한다.

u의 간선을 전부 탐색하고 나서야 다른 간선을 탐색하기 위해 백트랙한다.

이 알고리즘은 다음 두 가지를 고려해 개선할 수 있다.

time 변수는 그래프의 정점 개수의 1배~ 2배 값을 가질 수 없다.
모든 정점 u에 대해 d[u] < f[u]이다.

DFS을 이용한 위상 정렬

어떤 업무나 작업의 실행 순서를 정하는 것을 위상 정렬이라고 한다.

graph = new Graph();
myVertices = ["A", "B", "C", "D", "E", "F"];
for (i = 0; i < myVertices.length; i++) {
  graph.addVertex(myVertices[i]);
}
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("B", "D");
graph.addEdge("B", "E");
graph.addEdge("C", "F");
graph.addEdge("F", "E");
var result = graph.DFS();

개선된 DFS 알고리즘의 수행결과를 result 변수에 저장한다.

탐색 시간을 내림차순으로 나열한 것이 이 그래프의 위상 정렬 결과이다.

B-A-D-C-F-E

Tree | 트리

Queue | 큐