[자료구조] Graph

Graph의 특성

• Directed, Undirected
  Graph는 방향이 있을 수도 없을 수도 있다. (Tree는 Directed Graph이다.)

• Cyclic, Acyclic
  하나 이상의 cicle이 있는 그래프는 Cyclic Graph 없는 Graph는 Acyclic Graph라고 하낟.

• Adjacency Matrix, Adjacency List
  Adjacency Matrix: 2차원 배열에 표현하는 방법
  Adjacency List: 배열의 노드를 나열하고 관계를 Linked List로 표현하는 방법

Graph의 검색

DFS(Depth-First Search): 깊이 우선 검색

Binary Tree를 순회할 때 사용했던 inorder, preorder, postorder 방법이 깊이 우선 검색에 속한다. => 하나의 child node를 방문했으면 이 해당의 child node의 child 노드들은 끝까지 파고 드는 것

• DFS: Stack을 이용해 구현
• DFS를 REcursion(재귀 호출)을 이용하면 더 세련되진다.

BFS(Breadth-First Search): 넓이 우선 검색

시작점에서 자기 child node들을 먼저 다 방문하고 그 다음에 child의 child를 방문하고 하는 식으로 level단위로 검색하는 것

• BFS: Queue를 이용해 구현

import java.util.LinkedList;
import java.util.Iterator;
import java.util.Stack;
import java.util.NoSuchElementException;

class Queue<T> {...
}

class Graph{
	class Node{
    	int data;
        LinkedList<Node> adjacent;
        boolean marked;
        
        Node(int data){
        	this.data = data;
            this.marked = false;
            adjacent = new LinkedList<Node>();
        }
    }
    
    Node[] nodes;
    
    Graph(int size){
    	nodes = new Node[size];
        for(int i = 0;i < size;i++){
        	nodes[i] = new Node(i);
        }
    }
    
    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);
        }
    }
    
    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 == false){
                	n.marked = true;
                    stack.push(n);
                }
            }
            visit(r);
        }
    }
    
    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 == false){
                	n.marked = true;
                    queue.enqueue(n);
                }
            }
            visit(r);
        }
    }
    
    void dfsR(Node r){
    	if (r == null) return;
        r.marked = true;
        visit(r);
        for(Node n : r.adjacent){
        	if(n.marked == false){
            	dfsR(n);
            }
        }
    }
    
    void dfsR(int index){
    	Node r = nodes[index];
        dfsR(r);
    }
    
    void dfsR(){
    	dfsR(0);
    }
    
    void visit(Node n){
    	System.out.print(n.data + " ");
    }
    
}

# 테스트 클래스
/*
   0
 /
1 -- 3   7
|  / |\ /
| /  | 5
2 -- 4  \
         6 - 8
-----------------
DFS(0)
0 1 3 5 7 6 8 4 2
BFS(0)
0 1 2 3 4 5 6 7 8
DFS(0) - Recursive
0 1 2 4 3 5 6 8 7
*/
public class GraphTest{
	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();
        g.bfs();
        g.dfsR();
    }
}