그래프와 그래프 알고리즘

그래프의 정의

그래프는 정점과 간선으로 이루어져 있다. 도로로 연결된 마을을 표시한 지도를 떠올려보자. 지도도 일종의 그래프라 할 수 있다. 지도에서 각마을은 정점이며 도로가 간선이다. 간선은 (v1,v2)와 같은 쌍으로 정의하며, 여기서 v1, v2는 그래프의 정점이다. 정점은 무게(weight)또는 비용(cost)을 포함할 수 있다. 간선에서 정점의 순서를 따지는 그래프를 방향성 그래프라 한다. 방향성 그래프에서는 화살표로 간성을 표시한다. 이간선은 정점간의 흐름을 의미한다.

방향성이 없는 그래프를 무방향성 그래프 또는 그래프라고 한다.

경로는 그래프에 있는 일련의 정점을 모아 놓은 것으로 경로에 포함된 모든 정점은 간선으로 연결되어있다. 경로의 길이는 경로의 첫번째 정점에서 마지막 정점까지의 간선 수를 의미한다. 경로는 정점 자신으로 향하는 경로 즉, 루프도 포함한다. 이때 루프의 길이는 0이다.

첫번째 정점에서 마지막 정점으로 도달하는 하나이상의 간선으로 이루어졌으며 경로가 같은 상황을 싸이클이라고 한다. 그래프(방향성,무방향성 모두)에서 간선이나 정점이 반복되지 않는 경로를 단순 싸이클이라고 한다. 첫 정점과 마지막 정점을 제외한 다른 정점이 반복되는 경로를 일반 싸이클 이라한다.

한정점이나 다른 정점이 서로 연결되어 있으면 두정점은 서로 강하게 연결되어있다고 말한다. 방향성 그래프의 모든 정점이 강하게 연결되어 있다면 방향성 그래프가 강하게 연결되어 있다고 표현한다.

실생활에서 사용되는 그래프

신호등이 한가지 예다. 정점은 교차로, 간선은 도로를 의미할 수 있다. 가중치를 포함하는 간선으로 속도제한이나 도로의 차선수를 표현할 수 있다. 우리는 그래프를 이용해 교통 체증을 최소화할 수 있는 최적의 경로와 도로를 결정할 수 있다.

다양한 이동수단 시스템도 그래프로 표현할 수 있다. 예를 들어 항공사의 비행 시스템도 그래프로 만들 수 있다. 공항을 정점으로 정점간의 비행을 간선으로 표현할 수 있다. 가중치를 포함하는 간선으로 공항간을 비행하는 비용이나 공항 간의 거리를 표현할 수 있다.

그래프 클래스

얼핏보면 그래프는 트리와 비슷하보인다. 따라서 본인도 모르게 그래프를 트리처럼 만드는 상황이 종종 벌어진다. 이와같은 객체기반 접근방식이 처음에는 괜찮아 보일 수 있지만, 그래프의 크기가 커지면 문제가 발생한다.

객체로 그래프를 표현하면 효율성이 금새 떨어질 수 있다. 따라서 정점과 간선을 표현하는 색다른 방식을 살펴볼 것이다.

정점 표현

그래프클래스를 만들려면 가장 먼저 그래프의 정점을 저장할 vertex 클래스를 만들어야 한다. vertex클래스는 연결리스트와 이진탐색트리의 node클래스와 같은 역할을 담당한다. vertex클래스에는 정점을 식별할 수 있는 데이터 멤버와 정점을 방문했는지 여부를 확인할 수 있는 데이터 멤버가 필요하다. 이 두멤버를 각각 label, wasVisited라 부른다.

function Vertex(label){
    this.label = label
}

간선 표현

그래프의 구조를 표현하는 것은 간선이므로 실제 정보는 간선에 저장된다. 이전에도 설명했듯이 자신도 모르게 그래프를 이진트리처럼 만들려는 욕망이 생길수도 있느나 이는 바람직하지 않다. 이진트리에서 부모노드는 오직 두개 이하의 노드를 가질수 있으므로 대부분의 이진트리 구현은 비슷한 편이다. 하지만 그래프는 이진트리에 비해 훨씬 유연한 구조를 가진다. 예를 들어 한 정점에 여러 간선이 연결될 수 도 있거나 한 정점에 하나의 간선만 연결되어 있을 수도 있다.

우리는 인접리스트 또는 인접리스트 배열이라고 불리는 방법으로 그래프의 간선을 표현할 것이다. 인접리스트에서는 인접한 각 정점의 배열리스트에 정점을 인덱스로 이용해 간선을 저장한다. 프로그램에서는 이와 같은 특성을 이용해 어떤정점에서도 모든 정점에 효율적으로 접근할 수 있다. 예를들어 정점 2가 정점 0,1,3,4로 연결되고 인덱스는 2에 저정되어있다고 가정하면, 배열의 인덱스 2에는 정점 0,1,3,4의 정보가 들어있을 것이다.

0 -> [2]

1 -> [2]

2 -> [0,1,3,4]

3 -> [2]

4 -> [2]

간선으 구현하는 또 다른 방법으로 인접 행렬이라는 방식도 있다. 인접 행렬이란 두 정점간의 간선이 존재하는지 여부를 알려주는 요소를 포함하는 이차원 배열이다.

그래프 구현

그래프를 어떤 방식으로 구현할지 결정하면 쉽게 그래프를 구현할 수 있다. 다음은 그래프 클래스의 정의다.

function Graph(v){
    this.vertices = v
    this.edges = 0

    this.adj = []
    for(var i = 0; i < this.vertices; ++i){
        this.adj[i] = []
        this.adj[i].push("")
    }    
    this.addEdge = addEdge
    this.toString = toString    
}

그래프 클래스는 그래프의 정점수를 나타내는 배열 길이를 이용해 그래프의 간선수, 정점수 정보를 유지한다. 배열의 각요소를 for문으로 반복하면서 각요소에 인접 정점을 저장할 서브배열을 추가한 다음 각요소를 빈문자열로 초기화 한다.

function addEdge(v,w){
    this.adj[v].push(w)
    this.adj[w].push(v)
    this.edges++
}

a,b라는 두개의 정점을 인자로 addEdge()한수를 호출하면 정점 a와 인접한 b를 인접리스트에 추가한 다음 b와 인접한 a를 인접리스트에 추가한다. 마지막으로 간선의 수를 1만큼 증가 시킨다.

showGraph()함수는 그래프의 모든 정점리스트와 이를 정점에 인접한 모든 정점을 출력한다.

function showGraph(){
    for(var i = 0; i < this.vertices; i++){
        console.log(i + "->")
        for(var j = 0; j < this.vertices; j++){
            if(this.adj[i][j] != undefined){
                console.log(this.adj[i][j])
            }
            console.log(" ")
        }
    }
}

var g = new Graph(5)
g.addEdge(0,1)
g.addEdge(0,2)
g.addEdge(1,3)
g.addEdge(2,4)
g.showGraph()