[자료구조] Graph 개념과 DFS, BFS

출처 :  https://www.techyloud.com/why-do-students-need-help-with-a-data-structure-assignment/

 

[자료구조 알고리즘] 그래프(Graph)에 대해서

[자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java

 

본 포스팅은 위의 영상들을 정리한 글로 개인 공부를 목적으로 작성되었습니다.

---

Graph란

정점(vertex)와 edge(정점과 정점을 연결하는 간선)으로 구성된 한정된 자료구조이다. 만약 이전에 배웠던 트리가 루트도 없고 자식도 없고 방향성이 없어진다면 뭐가 될까? 그게 바로 그래프이다. 사실 트리는 그래프의 한 형태로 단지 사이클이 없고 방향이 정해져있다는 조건이 있는 상태인 것이다. 

 

Graph의 특성

1. Directed VS Undirected

그래프는 방향이 있을 수도 있고 없을 수도 있다. 방향이 있는 그래프는 Directed Graph, 없는 그래프는 Undirected Graphd이다. 그러니까 트리는 Directed Graph인 것이다. 참고로 방향 그래프는 self edge라고 자기 자신을 가리키는 경우도 있다.

 

2. Cyclic VS Uncyclic

그래프 내부에 하나 이상의 서클이 있는 그래프는 사이클릭 그래프, 하나도 없는 그래프는 에이사이클릭

 

 

Graph를 표현하는 방법

1. 인접 행렬(Adjacency Matrix)

노드들의 관계를 이차원 배열에 표현하는 방법이다.

인접 행렬

- self edge가 아닌 이상 본인과 본인의 관계는 연결되지 않았으니까 0이다.

- 그리고 인접된 숫자들은 1로 표현해 준다.

 

2. 인접 리스트(Adjacency List)

배열에 노드들을 나열하고 관계를 LinkedList로 표현하는 방법이다.

인접 리스트

- 각각의 노드를 배열에 적고 오른쪽으로 인접해있는 노드들을 순서 상관없이 나열하고 연결한다.

- edge가 m개 있으면 총 노드의 갯수는 2m개이다.

 

 

Graph를 검색하는 방법

1. 깊이 우선 탐색(DFS, Depth-Frist Search)

inorder, preorder, Postorder이 바로 이 깊이 우선 탐색에 속한다. 트리로 표현하자면 말 그대로 해당 노드의 차일드 노드, 그 이하 차일드 노드를 끝까지 파고들고 나와서 다음 줄기를 탐색하는 방법이다.

출처 : 위키백과

 

 

2. 너비 우선 탐색(Breadth-First Searh)

트리로 표현하자면 시작점에서 루트의 차일드 노드를 탐색하고 그 하위의 차일드 노드를 탐색하는 식으로 레벨 별로 탐색을 한다.

출처: 위키백과

 

 

 

아래 영상에서 DFS는 Stack으로 BFS는 Queue로 순회하는 과정을 자세히 설명해주니 꼭 꼭 보기!

 

 

자바로 구현하기

1) 우선 Queue를 구현한다.

class Queue<T> {
	class Node<T> {
    	private T data;
        private Node<T> next;
        
        public Node(T input) {
            this.data = input;
            this.next = null;
        }
    }
}

 

2) Graph 클래스를 선언하고 인접한 노드들과의 관계를 LinkedList로 표현하기로 한다.

marked는 해당 노드를 방문했는지에 대한 boolean 값이다.

class Graph {
	class Node {
    	int data;
        LinkedList<Node> adjacent;
        boolean marked;
       
      	Node (int data) {
            this.data = data;
            this.marked = false;
            adjacent = new LinkedList<Node>();
        }
    }
}

 

3) 이제 그래프를 만들어 보자. 그래프에는 노드들을 저장할 배열이 필요하다.

노드 갯수를 받아서 그 갯수만큼 배열 방을 만들어 준다.

Node[] nodes;
Graph(int size) {
    nodes = new Node[size];
    for (int i = 0; i < size; i++) {
        nodes[i] = new Node(i);
    }
}

 

4) 두 노드의 관계를 저장하는 함수이다. 데이터가 인덱스와 같으니까 받은 숫자를 인덱스로 사용하면 된다.

Node[] nodes;
Graph(int size) {
	...
    void addEdge(int i1, int i2) {
    	Node n1 = nodes[i1];
        Node n2 = nodes[i2];
        if (!n1.adjacent.contains(n2)) {
        	n1.adjacent.add(n2);
        }
        if (!n2.adjacent.contains(n1)) {
        	n2.adjacent.add(n1);
        }
    }
}

 

5) 시작 인덱스를 받아서 DFS 순회 결과를 출력하는 함수이다. 해당 인덱스로 노드를 가져오고 스택을 생성한다.

그리고 현재 노드를 스택에 추가하고 marked 값을 true로 바꾼다. 그래야 스택에 추가되었던 값은 피할 수 있음!

스택에서 데이터를 하나 가져오고 가져온 노드의 인접한 노드들을 스택에 추가한다.

Node[] nodes;
Graph(int size) {
	...
    void dfs() {
     dfs(0;)
    }
    
    void dfs(int index) {
        Node root = nodes[index];
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);
        root.marked = true;
        while (!stack.isEmpty()) {
            Node r = stack.pop();
            for (Node n : r.adjacent) {
                if (!n.marked) {
                    n.marked = true;
                    stack.push(n);
                }
            }
            visit(r);
        }
    }
}

 

6) 방문할 때 출력해 주는 함수이다.

Node[] nodes;
Graph(int size) {
	...
    void visit(Node n) {
    	System.out.print(n.data + " ");
    }
}

 

 

7) 시작 인덱스를 받아서 BFS 순회 결과를 출력하는 함수이다. 큐를 하나 생성하고 데이터를 큐에 추가한다.

추가했다고 marked 값을 true로 만들고 큐에 데이터 값이 없을 때까지 데이터를 가져오고 큐에서 꺼낸 노드의 인접 노드들을 추가하는 작업을 반복한다.

Node[] nodes;
Graph(int size) {
	...
    void bfs() {
    	bfs(0);
    }
    void bfs(int index) {
    	Node root = nodes[index];
        Queue<Node> queue = new Queue<Node>();
        queue.enqueue(root);
        root.marked = true;
        while (!queue.isEmpty()) {
            Node r = queue.dequeue();
            for (Node n : r.adjacent) {
                if (!n.marked) {
                    n.marked = true;
                    queue.enqueue(n);
                }	
            }
            visit(r);
        }
    }
}

 

8) 재귀호출을 이용한 DFS 함수를 구현해 보자. 재귀호출을 할 때는 Node를 매개변수로 받아야 한다.

Node[] nodes;
Graph(int size) {
	...
    void dfsR(Node r) {
     if (r == null) return;
     r.marked = true;
     visit(r);
     for (Node n : r.adjacent) {
         if (!n.marked) {
            dfsR(n);
        }
     }
    }
    
    void dfsR(int index) {
        Node r = nodes[index];
        dfsR(r);
    }
    void dfsR() {
    	dfsR(1);
    }
}

 

9) 테스트를 해보자.

public class Test {
	public static void main (String[] args) {
    	Graph g = new Graph(9);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        g.addEdge(5, 6);
        g.addEdge(5, 7);
        g.addEdge(6, 8);
        g.dfs();
    }
}

*한 번 명시해준 인접 관계는 중복해서 명시해 줄 필요가 없다.

1과 2가 인접해 있다고 할 때 2와 1을 또 다시 명시해 줄 필요가 없다는 뜻이다.