그래프(graph)

---

그래프의 정의

그래프는 연결되어 있는 원소 간 관계를 표현하는 자료구조이다.

실세계의 지하철 노선도, 컴퓨터 네트워크 등의 예를 생각하면 된다.

그래프의 구성 요소

 

그래프는 vertex(정점)과 정점들을 잇는 edge(간선)으로 구성된다.

위 사진에서 0,1,2,3,4가 정점에 해당하고, 정점을 잇는 선이 간선이다.

 

그래프 G가 있을 때, 

G에 포함된 모든 정점들의 집합을 V(G), 모든 간선들의 집합을 E(G)라고 표기한다.

G = (V,E)라고 쓰기도 한다.

 

그래프의 종류

그래프는 무방향성 그래프와 방향성 그래프로 나뉜다.

무방향성 그래프

무방향성 그래프는 각 vertex가 서로 연결됐음만을 나타내는 그래프이다.

이 때 vertex 0과 1에 대해서 (0,1)과 (1,0)는 동일한 edge를 표현한다.

방향성 그래프

 

방향성 그래프는 edge에 방향성이 존재하는 그래프이다.

이제 <0,1>는 vertex 0에서 1로 가는 edge를 표현한다.

그래프 관련 용어

완전 그래프(complete graph)

완전그래프

Edge의 수가 최대인 그래프이다.

vertex의 수가 n개일 때,
완전 그래프 edge의 수 = n(n-1)/2

사이클(cycle)

처음과 마지막이 동일한 경로를 뜻한다.

연결(connected)

그래프 G

Vertex u와 v 사이에 경로가 존재할 경우, u와 v는 연결되었다고 표현한다.

위 그래프 G에서 0과 3은 연결되었지만, 0과 4는 연결되어있지 않다.

연결 요소(connected component)

위 그래프 G에는 2개의 연결 요소가 존재한다.

(0 1 2 3)과 (4 5 6)이 각각 연결 요소이다.

Vertex v의 차수(degree)

특정 vertex에 부속된 edge의 수를 차수로 표현한다.

방향성 그래프에서는 in-degree와 out-degree로 나누어 표현할 수 있다.

in-degree는 말 그대로 vertex를 향해 들어오는 edge를 의미하고, out-degree는 vertex에서 나가는 edge를 의미한다.

 

위 그래프에서 vertex 0의 in-degree는 3, out-degree는 1이다.

---

그래프 구현 방법

그래프는 리스트를 사용하거나, 배열을 사용하여 구현할 수 있다.

배열, 인접 행렬(Adjacency Matrix)

n개의 vertex를 갖는 그래프 G에 대해서 arr[n][n]의 인접 행렬을 만들어 사용한다. 

0으로 초기화된 배열에, 만일 G에 (u,v)의 edge가 존재한다면 arr[u][v] = 1로 표현할 수 있다.

• 무방향성 그래프의 경우, [u][v]가 1이라면 [v,u] 또한 1이 된다. 따라서 대칭 행렬이 된다. 따라서 원한다면 n(n-1)/2 크기를 갖는 1차원 배열의 형태로도 구현이 가능하다. 
• 방향성 그래프의 경우, 비대칭 행렬이 된다.

리스트, 인접 리스트(Adjacency List)

n개의 vertex를 갖는 그래프 G에 대해 그래프의 vertex마다 연결 리스트를 만들어 사용한다.

즉 n개 크기를 갖는 배열이 있으며, 각 요소는 해당 vertex의 연결 리스트이다.

각 연결 리스트는 해당 vertex와 연결된 vertex에 대한 정보를 담고 있다. 

방향성 그래프의 경우, (0,1)의 edge가 있는 경우 0의 연결 리스트에 1의 정보가, 1의 연결리스트에 0의 정보가 담기게 된다.

무방향성 그래프의 경우, <0,1>의 edge가 있는 경우 0의 연결 리스트에 1의 정보가 담기게 된다. 즉, out-degree를 표현하게 되는 것이다.

역인접 리스트(Inverse Adjacency List)

무방향 그래프의 in-degree만을 표현하는 인접 리스트이다.

<0,1>의 edge가 존재하는 경우, 역인접 리스트에는 1의 연결 리스트에 0의 정보가 담기게 된다.

 

리스트를 이용한 그래프 구현

public interface Graph {
    int size();                     // vertex의 수
    void addEdge(int v, int w);     // v와 w를 연결하는 edge 추가
    Iterable<Integer> adj(int v);   // v에 연결된 정점들 순회
    String toString();              // 전체 그래프 출력
}

 

모든 그래프를 구현할 때 쓰일 인터페이스이다.

 

package graph;

import java.util.LinkedList;

public class ListGraph implements Graph{
    int size;
    boolean directed;
    LinkedList<Integer>[] adj; 	// 인접 리스트
    LinkedList<Integer>[] inv;  // 역인접 리스트

    public ListGraph(int size, boolean directed) {
        this.size = size;           // vertex의 수
        this.directed = directed;   // true: 방향성 그래프, false: 무방향성 그래프
        adj = new LinkedList[size];
        inv = new LinkedList[size];
        for(int i = 0; i < size; i++) {
            adj[i] = new LinkedList<Integer>();
            inv[i] = new LinkedList<Integer>();
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void addEdge(int v, int w) {
        adj[v].add(w);
        if(!directed) {
            adj[w].add(v);
        } else {
            inv[w].add(v);
        }
    }

    @Override
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i< size; i++) {
            sb.append(i).append(" -> ( ");
            for(int k: adj[i])
                sb.append(k).append(" ");
            sb.append(")\n");
        }
        return sb.toString();
    }

    public int inDegree(int v) {    // vertex v로 들어오는 edge의 수
        if(v < 0 || v >= size) {
            throw new IllegalArgumentException("잘못된 vertex 번호입니다.");
        }
        return inv[v].size();
    }

    public int outDegree(int v) {   // vertex v에서 나가는 edge의 수
        if(v < 0 || v >= size) {
            throw new IllegalArgumentException("잘못된 vertex 번호입니다.");
        }
        return adj[v].size();
    }
}

 

배열을 이용한 그래프 구현

package graph;

import java.util.ArrayList;

public class MatrixGraph implements Graph{
    int size;
    boolean directed;
    int[][] adj;		// 인접 행렬

    public MatrixGraph(int size, boolean directed) {
        this.size = size;
        this.directed = directed;
        adj = new int[size][size];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void addEdge(int v, int w) {
        adj[v][w] = 1;
        if(!directed) {
            adj[w][v] = 1;
        }
    }

    @Override
    public Iterable<Integer> adj(int v) {
        // array를 Iterable한 자료구조로 바꿔서 리턴
        ArrayList<Integer> L = new ArrayList<Integer>(size);
        for(int i = 0; i < size; i++) {
            if(adj[v][i]==1)
                L.add(i);
        }
        return L;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < size; i++) {
            sb.append(i).append(" -> ( ");
            for(int k = 0; k < size; k++) {
                if(adj[i][k] == 1)
                    sb.append(k).append(" ");
            }
            sb.append(")\n");
        }
        return sb.toString();
    }

    public int inDegree(int v) {
        int count = 0;
        for(int i = 0; i < size; i++) {
            count += adj[i][v];
        }
        return count;
    }

    public int outDegree(int v) {
        int count = 0;
        for(int i = 0; i < size; i++) {
            count += adj[v][i];
        }
        return count;
    }
}

 

테스트

 

위와 같은 그래프를 만들어보자.

public class GraphTestDriver {
    public static void main(String[] args) {
        MatrixGraph G = new MatrixGraph(4,true);
        G.addEdge(0,1);
        G.addEdge(0,3);
        G.addEdge(1,2);
        G.addEdge(1,3);
        G.addEdge(3,2);
        System.out.println(G);
        for(int x: G.adj(0)) {
            System.out.print(x+ " ");
        }
        System.out.println();
        System.out.println("3의 out degree = "+G.outDegree(3));
        System.out.println("3의 out degree = "+G.inDegree(3));
    }
}

 

실행 결과