Graph - DFS(Depth First Search) 구현

DFS

1. 탐색

그래프의 탐색은 하나의 정점에서 시작하여 모든 정점들을 간선을 따라 한 번씩 방문하는 것을 의미합니다.

주로 트리, 그래프와 같은 자료구조에서 데이터를 탐색할 때 사용됩니다.

이번 시간에는 대표적인 그래프 탐색 방법인 DFS(Depth First Search)에 대해 알아보겠습니다. 

 

2. DFS(Depth First Search : 깊이 우선 탐색)

DFS는 시작 정점을 방문한 후, 인접한 정점들 중 방문하지 않은 정점을 다시 시작 정점으로 하여 재귀적으로 탐색을 합니다.

 

DFS 알고리즘 특징

루트 노드나 임의의 노드에서 시작하여 더 이상 진행할 길이 없을 때까지 찾아가면서 탐색.

만약, 진행할 길이 존재하지 않는다면 이전의 위치로 돌아와 찾아가지 않은 길로 뻗어 나가며 탐색.

 

DFS는 인접 행렬과 인접 리스트로 구현할 수 있는데 각 특징들은 아래와 같습니다.

인접 행렬	인접 리스트
정점의 개수가 n인 그래프를 n X n 행렬로 표시 이해하기 쉽고 간선의 존재 여부를 상수 시간에 알 수 있다. 간선의 밀도가 높은 고밀도 그래프에 적절	정점의 개수가 n인 그래프를 n개의 연결 리스트 배열로 표현 정점 i에 인접한 정점들을 i번째 연결 리스트에 저장 간선의 수가 적은 저밀도 그래프에 적절 실생활의 그래프는 대체로 저밀도

 

3. 인접 리스트를 이용한 DFS 구현

 
public class Node {
    int vertex;
    Node next;
}
 
public class AdjList {
    public Node head; //리스트의 헤드
    
    //인접리스트의 헤드로 새 정점 삽입
    public void insert(int v) {
        Node new_node = new Node();
        new_node.vertex = v;
        new_node.next = head;
        head = new_node;
    }
}
 
public class Graph {
    public int V; //정점의 개수
    public int E; //간선의 개수
    public AdjList[] adj; //정점별 인접리스트의 배열
    
    //주어진 정점 개수로 그래프 생성하기
    public Graph(int V) {
        this.V = V;
        this.E = 0;
        adj = new AdjList[V]; 
        
        for(int v=0;v<V;v++)
            adj[v] = new AdjList();
    }
    
    //비방향 그래프 : 정점 v와 정점 w를 잇는 양방향 간선 추가
    public void addEdge(int v, int w) {
        adj[v].insert(w); //v->w
        adj[w].insert(v); //w->v
        
        E++;
    }
}
 
 
public class DFS {
    public boolean[] visited; //정점의 방문여부
    public int[] edgeTo; //DFS에 포함되는 간선(edgeTo[i]->i)
    
    //시작정점을 s로 하는 깊이우선탐색
    public DFS(Graph G, int s) {
        visited = new boolean[G.V];
        edgeTo = new int[G.V];
        
        dfs(G, s);
    }
    
    //정점 v로부터 시작하는 깊이우선탐색 재귀 함수
    private void dfs(Graph G, int v) {
        visited[v] = true;
        
        System.out.print(v + " "); //방문순서:코드 확인용
        
        Node node = G.adj[v].head; 
        
        while(node != null) {
            int w = node.vertex;
            
            if(!visited[w]) { //정점 w를 아직 방문하지 않았으면
                edgeTo[w] = v;
                dfs(G, w);
            }
            node = node.next;
        }
    }
}
 
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
 
public class GraphTraversalTest {
 
    public static void main(String[] args) {
        String fname = "Graph_2.txt"; 
        BufferedReader in = null;
        
        try {
            in = new BufferedReader(new FileReader(fname));
            int n = Integer.parseInt(in.readLine()); 
            int m = Integer.parseInt(in.readLine()); 
            Graph g = new Graph(n); 
            for(int i=0;i<m;i++) {
                String[] vs = new String[2]; String line = in.readLine();
                vs = line.split(" ");
                g.addEdge(Integer.parseInt(vs[0]), Integer.parseInt(vs[1]));
            }
            in.close();
            
            System.out.println("<Graph>"); 
            for(int v=0;v<g.V;v++) {
                System.out.print(v + " : ");
                Node node = g.adj[v].head; 
                while(node != null) {
                    System.out.print(node.vertex + " ");
                    node = node.next;
                }
                System.out.println();
            }
            
            System.out.println("<DFS>");
            DFS dfs = new DFS(g, 0);
            System.out.println("");
            for(int v=0; v< g.V; v++) {
                System.out.println(v + " | " + dfs.edgeTo[v]);
            }
        } catch(IOException e) {
            System.err.println("File Error");;
            System.exit(1);
        }
    }
}