그래프

thsamajiki·2022년 10월 25일

그래프

인접 리스트(Adjacency List)

인접 행렬(Adjacency Matrix)

알고리즘

목록 보기

2/8

그래프

사실, 트리(tree)는 그래프(graph)의 한 종류 입니다. 하지만 그렇다고 모든 그래프가 트리는 아닙니다. 트리는 사이클(cycle)이 없는 하나의 연결 그래프 입니다. 그래프는 단순히 노드와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 것과 같습니다.

아래의 그림은 그래프의 예시입니다.

그래프는 방향성이 있을 수도 있고, 없을 수도 있습니다. 방향성이 있는 간선은 일방통행, 방향성이 없는 간선은 양방향 통행 도로라고 생각하면 됩니다.
그래프는 여러 개의 고립된 부분 그래프(isolated subgraphs)로 구성될 수 있습니다. 모든 정점 쌍(pair of vertices)간에 경로가 존재하는 그래프는 ‘연결 그래프’라고 부릅니다.
그래프에는 사이클이 존재할 수도 있고 존재하지 않을 수도 있습니다. 사이클이 없는 그래프는 ‘비순환 그래프(acyclic graph)라고 부릅니다.

프로그래밍 관점에서 그래프를 표현할 때는 일반적으로 다음 2가지 방법을 사용합니다.

인접 리스트(Adjacency List)

인접 리스트는 그래프를 표현할 때 사용되는 가장 일반적인 방법 입니다. 모든 정점(혹은 노드)을 인접 리시트에 저장 합니다. 무방향 그래프에서 (a, b) 간선은 두 번 저장됩니다. 한 번은 a 정점에서 인접한 간선을 저장하고, 다른 한 번은 b에 인접한 간선을 저장합니다.그래프에서 노드를 정의하는 간단한 클래스는 트리의 노드 클래스와 궁극적으로 같아 보입니다. 트리에서는 루트 노드에서 모든 노드로 접근이 가능해서 따로 클래스를 두지 않았지만 그래프에서는 가능하지 않아 Graph 클래스를 사용합니다.

class Graph{
    public Node[] nodes;
}

class Node{
    public String name;
    public Node[] children;
}

인접 행렬(Adjacency Matrix)

인접 행렬은 NxN boolean Matrix 로써 matrix[i][j]가 true라면 연결되어 있다는 뜻 입니다.

위와 같은 그래프는 인접행렬에서 다음과 같이 표현 될 수 있습니다.

	0	1	2
0	0	1	0
1	0	0	1
2	1	0	0
3	0	0	1

그래프 탐색

그래프를 탐색하는 일반적인 방법 두 가지로는 깊이 우선 탐색(depth-first search)과 너비 우선 탐색(breadth-first search)가 있습니다.

DFS(깊이 우선 탐색) : 루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 입니다.
BFS(너비 우선 탐색) : 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 입니다. 인접한 노드가 여러 개일 때는 노드의 번호 순서대로 순회한다고 가정 합니다.

DFS와 BFS는 서로 다른 상황에서 사용되는 경향이 있습니다. DFS는 그래프에서 모든 노드를 방문하고자 할 때 좀 더 선호되는 편이며, 둘 중 아무거나 사용해도 상관 없지만 깊이 우선 탐색이 좀 더 간단하기는 합니다.

아래의 그래프를 토대로 한번 확인해 보겠습니다.

class Graph{
    public Node nodes[];

    public static void main(String[] args) {
        Node node = new Node("0");
        Node node1 = new Node("1");
        Node node2 = new Node("2");
        Node node3 = new Node("3");
        Node node4 = new Node("4");
        Node node5 = new Node("5");

        node.children = new Node[]{node1, node4, node5};
        node1.children = new Node[]{node3, node4};
        node2.children = new Node[]{node1};
        node3.children = new Node[]{node2, node4};

        Graph graph = new Graph();
        graph.nodes =new Node[]{node, node1, node2, node3, node4, node5};

        new DFS().search(graph.nodes[0]);
        // new BFS().search(graph.nodes[0]);
    }
}

class Node{
    public String name;
    public Node children[];
    public boolean visited;

    public Node(String name){
        this.name = name;
    }
}

깊이 우선 탐색(DFS)

DFS는 a 노드를 방문한 뒤 a와 인접한 노드들을 차례로 순회 합니다. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 합니다. 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻 입니다.

public class DFS {

    public void search(Node root){
        if(root == null) return;

        System.out.println(root.name);
        root.visited = true;

        if(root.children == null) return;
        for (Node n:root.children) {
            if(n.visited == false){
                search(n);
            }
        }
    }
}

재귀 함수 search를 이용하여 탐색했으며, visited를 이용하여 방문 여부를 확인 합니다.

결과는 다음과 같습니다.

0 1 3 2 4 5

너비 우선 탐색(BFS)

BFS도 재귀적으로 동작할 것이라 생각하여 애를 먹는 경우가 많습니다. 그러나 BFS는 재귀적으로 동작하지 않고 큐(queue)를 사용하여 동작하게 됩니다. a 노드에서 시작한다고 했을 때, BFS는 a 노드의 이웃 노드를 모두 방문한 다음 이웃의 이웃들을 방문 합니다.

class BFS{

    public void search(Node root){
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);

        while(!queue.isEmpty()){
            Node r = queue.poll();
            r.visited = true;
            System.out.println(r.name);
            if(r.children == null) continue;
            for (Node n : r.children){
                if(n.visited == false){
                    n.visited = true;
                    queue.add(n);
                }
            }
        }
    }

}