깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

깊이 우선 탐색(DFS, Depth First Search)

• 수행 순서
  1. 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색
  2. 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴.
  3. 그 정점에서 다른 방향의 간선으로 탐색을 계속하여 모든 정점을 방문
• 스택 사용
  • 깊이 우선 탐색을 반복하기 위해 가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가야한다.

 

너비 우선 탐색(BFS, Breadth First Search)

• 수행 순서
  1. 시작 정점으로부터 인접한 정점들을 모두 차례로 방문
  2. 그 후 방문했던 정점을 다시 시작점으로 설정
  3. 그 시작점에서 인접한 정점들을 차례대로 방문
• 큐 사용
  • 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야한다.

출처: vivadifferences

 

 

DFS, BFS 구현

// 인접 리스트로 표현한 그래프의 깊이 우선 탐색과 너비 우선 탐색
public class DFS_BFS {
    public static void main(String[] args) {
        AdjListForFs G = new AdjListForFs();
        for (int i = 0; i < 6; i++) {
            G.insertVertex(i);
        }
        G.insertEdge(0,2);
        G.insertEdge(0,1);
        G.insertEdge(1,4);
        G.insertEdge(1,3);
        G.insertEdge(2,5);


        G.printAdjList();

        System.out.printf("\nDFS >>> ");
        G.DFS(0);

        System.out.printf("\nBFS >>> ");
        G.BFS(0);
    }
}

class StackNode{
    int data;
    StackNode link;
}

class LinkedStack {
    StackNode top;

    public boolean isEmpty() {
        return top == null;
    }

    public void push(int data) {
        StackNode newNode = new StackNode();
        newNode.data = data;
        newNode.link = top;
        top = newNode;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("LinkedStack is empty");
            return 0;
        } else {
            int popNode = top.data;
            top = top.link;
            return popNode;
        }
    }
}

class QNode {
    int data;
    QNode link;
}

class LinkedQueue {
    QNode front;
    QNode rear;

    public LinkedQueue() {
        front = null;
        rear = null;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public void enQueue(int data) {
        QNode newNode = new QNode();
        newNode.data = data;
        newNode.link = null;

        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.link = newNode;
            rear = newNode;
        }
    }

    public int deQueue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return 0;
        } else {
            int deQueuedData = front.data;
            front = front.link;
            if (front == null) {
                rear = null;
            }
            return deQueuedData;
        }
    }
}

class GraphNodeForFS {
    int vertex;
    GraphNodeForFS link;
}

class AdjListForFs {
    GraphNodeForFS head[] = new GraphNodeForFS[10];
    private int totalVertex = 0;

    // vertex 값 삽입 발생x, totalVertex 카운트 용 메소드
    public void insertVertex(int data) {
        totalVertex++;
    }

    public void insertEdge(int vertex1, int vertex2) {
        if (vertex1 >= totalVertex || vertex2 >= totalVertex) {
            System.out.println("There is no vertex");
        } else {
            GraphNodeForFS newNode = new GraphNodeForFS();
            newNode.vertex = vertex2;
            newNode.link = head[vertex1];
            head[vertex1] = newNode;
        }
    }

    public void printAdjList() {
        for (int i = 0; i < totalVertex; i++) {
            System.out.printf("\n정점 "+ i +"의 인접리스트 ");
            GraphNodeForFS temp = head[i];

            while (temp != null) {
                System.out.printf("-> " + temp.vertex);
                temp = temp.link;
            }
            System.out.println();
        }
    }

    public void DFS(int vertex) {
        GraphNodeForFS gNode = new GraphNodeForFS();
        LinkedStack stack = new LinkedStack();
        boolean visited[] = new boolean[10];

        stack.push(vertex);
        visited[vertex] = true;
        System.out.printf(vertex + " ");
        while (stack.top != null) {
            gNode = head[vertex];
            while (gNode != null) {
                if (visited[gNode.vertex]==false) {
                    visited[gNode.vertex] = true;
                    System.out.printf(gNode.vertex + " ");
                    stack.push(gNode.vertex);
                    gNode = head[gNode.vertex];
                } else {
                    gNode = gNode.link;
                }
            }
            vertex = stack.pop();
        }
    }

    public void BFS(int vertex) {
        GraphNodeForFS gNode = new GraphNodeForFS();
        LinkedQueue queue = new LinkedQueue();
        boolean visited[] = new boolean[10];

        visited[vertex] = true;
        System.out.printf(" %d", vertex);
        queue.enQueue(vertex);

        while (queue.isEmpty()==false) {
            vertex = queue.deQueue();
            for (gNode = head[vertex]; gNode != null; gNode = gNode.link) {
                if (visited[gNode.vertex]==false) {
                    visited[gNode.vertex] = true;
                    System.out.printf(" %d", gNode.vertex);
                    queue.enQueue(gNode.vertex);
                }
            }
        }
    }
}

 

 

 

학습 교재

자바로 배우는 쉬운 자료구조 - 이지영 지음

누구나 자료구조와 알고리즘 - 제이 웬그로우 지음