[Data Structure] 그래프 순회, 탐색(DFS) - 자료 구조

그래프 순회(Graph Traversal)

하나의 정점에서 그래프의 모든 정점을 한 번씩 방문하는 것을 그래프 순회라고 합니다.

탐색 방법에는 

'깊이 우선 탐색(DFS)'

'너비 우선 탐색(BFS)'

1. 깊이 우선 탐색

DFS(Depth First Search)

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 탐색하다 막히면 

가장 마지막 갈림길 간선이 있는 정점으로 돌아와서 다른 방향의 간선으로 탐색을 계속하는 탐색 방법

이 탐색 방법에서는 스택(Stack)을 이용하여서 탐색합니다.

깊이 우선 탐색 과정

1. 초기 배열 visited를 False로 초기화하고 공백 스택 생성

2. 정점 A를 시작으로 깊이 우선 탐색 시작

visited[A] = true;

3. 정점 A에 방문하지 않은 정점 B, C가 있으므로 A를 스택에 push하고, 인접 정점 B와 C 중 오름차순에 따라 B를 선택하여 탐색

 push(stack, A);

visited[B] = true;

4. 정점 B에 방문하지 않은 정점 D, E가 있으므로 B를 스택에 push하고, D와 E 중 오름차순에 따라 D를 선택하여 탐색

push(stack, B);

visited[D] = true;

5. 정점 D에서 방문하지 않은 정점 G가 있으므로 D를 스택에 push하고, G를 선택하여 탐색

push(stack, D);

visited[G] = true;

6. 정점 G에 방문하지 않은 정점 E, F가 있으므로 G를 스택에 push하고, E와 F 중 오름차순에 따라 E를 선택하여 탐색

push(stack, G);

visited[E] = true;

7. 정점 E에 방문하지 않은 정점 C가 있으므로 E를 스택에 push하고, C를 선택하여 탐색

push(stack, E);

visited[C] = true;

8.  정점 C에 방문하지 않은 인접 정점이 없으므로 스택에서 pop하여 이전 정점에서 방문하지 않은 인접 정점이 있는지 확인

pop(stack);

E의 인접 정점은 B, C, G 인데 배열을 보면 모두 True로 방문 되어 있음.

9. 현재 정점 E에서 방문할 수 있는 인접 정점이 없으므로, 스택을 pop하여 받은 정점 G에 대해 방문하지 않은 인접 정점이 있는지 확인

pop(stack);

G의 인접 정점은 D, E, F 인데 F는 False로 방문하지 않은 것으로 되어 있음

10. 현재 정점 G에서 방문하지 않은 정점 F가 있으므로 G를 스택에 push하고, 정점 F를 선택하여 탐색

push(stack, G);

visited[F] = true;

11. 현재 정점 F에서 방문하지 않은 정점이 없으므로, 스택을 pop하여 받은 정점 G에 대해 방문하지 않은 정점이 있는지 확인

pop(stack);

이와 같은 방법으로 스택을 pop하고 방문확인을 하여 탐색

링크드 리스트로 구현한 DFS 예제를 보도록 합시다.

 * Graph.java

 

package ssww;
 
 
public class Graph {
    
    GraphType g;
    
    public Graph() {
        g = new GraphType();
    }
    
    public void createGraph() {
        g.n = 0;
        
        for (int i = 0; i < g.MAXVERTEX; i++) {
            g.visited[i] = false;
            g.adjList[i] = null;
        }
    }
    
    public void insertVertex(int v) {
        if ((g.n + 1) > g.MAXVERTEX) {
            System.out.println("그래프의 정점의 갯수 초과!");
            return;
        }
        
        g.n++;
    }
    
    public void insertEdge(int u, int v) {
        GraphNode node;
        
        if (u >= g.n || v >= g.n) {
            System.out.println("그래프에 없는 정점!");
            return;
        } 
        node = new GraphNode();
        node.vertex = v;
        node.link = g.adjList[u];
        g.adjList[u] = node;
    }
    
    public void printAdjList() {
        GraphNode tmp;
        
        for (int i = 0; i < g.n; i++) {
            System.out.println("\n\t 정점 " + (char)(i + 65) + "의 인접 리스트");
            tmp = g.adjList[i];
            
            while (tmp != null) {
                System.out.print(" -> " + (char) (tmp.vertex + 65));
                tmp = tmp.link;
            }
        }
    }
    
    public void depthFirstSearch(int v) {
        GraphNode tmp;
        Stack stack = new Stack();
        stack.top = null;
        stack.push(v);
        
        g.visited[v] = true;
        System.out.print(" " + (char) (v + 65));
        
        while (stack.top != null) {
            tmp = g.adjList[v];
            
            while (tmp != null) {
                if (!g.visited[tmp.vertex]) {
                    stack.push(tmp.vertex);
                    g.visited[tmp.vertex] = true;
                    System.out.print(" " + (char) (tmp.vertex + 65));
                    v = tmp.vertex;
                    tmp = g.adjList[v];
                } else tmp = tmp.link;
            }
            v = stack.pop();
        }
    }
}
 
class GraphType {
    final int MAXVERTEX = 10;
    
    int n;
    GraphNode adjList[];
    boolean visited[];
    
    public GraphType() {
        adjList = new GraphNode[MAXVERTEX];
        visited = new boolean[MAXVERTEX];
    }
 
}
 
class GraphNode {
    int vertex;
    GraphNode link;
    
}
 
class StackNode {
    int data;
    StackNode link;
    
    public StackNode(int data) {
        this.data = data;
    }
}
 
class Stack {
    StackNode top;
    
    public void push(int data) {
        StackNode tmp = new StackNode(data);
        tmp.link = top;
        top = tmp;
    }
    
    public int pop() {
        int data;
        StackNode tmp = top;
        
        if (top == null) {
            System.out.println("Stack is Empty!!");
            return 0;
        } else {
            data = tmp.data;
            top = tmp.link;
            tmp = null;
            return data;
        }
    }
}
 
 
 

 * GraphMain.java

 
 
 
 
 
 
 
 
 
 
 
 
package ssww;
 
public class GraphMain {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.createGraph();
        
        for (int i = 0; i < 7; i++) 
            graph.insertVertex(i);
        
        graph.insertEdge(0, 2);
        graph.insertEdge(0, 1);
        graph.insertEdge(1, 4);
        graph.insertEdge(1, 3);
        graph.insertEdge(1, 0);
        graph.insertEdge(2, 4);
        graph.insertEdge(2, 0);
        graph.insertEdge(3, 6);
        graph.insertEdge(3, 1);
        graph.insertEdge(4, 6);
        graph.insertEdge(4, 2);
        graph.insertEdge(4, 1);
        graph.insertEdge(5, 6);
        graph.insertEdge(6, 5);
        graph.insertEdge(6, 4);
        graph.insertEdge(6, 3);
        
        System.out.print("Graph의 인접 리스트: ");
        graph.printAdjList();
        
        System.out.println("\n\n Depth First Search:");
        graph.depthFirstSearch(0);
    }
}
 
 
 

Class Diagram

end

tags: Data Structure, 그래프, Graph, 자료 구조, 간선, 정점, Vertex, Edge, Graph Traversal, Graph Search, Traverse, 그래프 순회, DFS, DepthFirstSearch