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

그래프 순회(Graph Traversal)

2. 너비 우선 탐색

BFS(Breadth First Search)

시작 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서

방문했던 정점을 시작으로 다시 인접한 정점들을 차례로 방문하여 가까운 정점들을 번저 방문하는 방법

인접한 정점들에 대해 차례로 다시 너비 우선 탐색을 반복해야 하므로 FIFO 구조를 갖는 Queue를 사용합니다.

너비 우선 탐색 과정 

초기 상태

visited를 초기화하고 공백 큐 생성

1. 정점 A를 시작으로 너비 우선 탐색 시작

visited[A] = true;

A 방문

2. 정점 A에서 방문하지 않은 모든 인접 정점 B, C를 방문하고  큐에 enQueue

visited[B & C] = true;

B & C 방문

enQueue(B & C);

3. 정점 A에 대한 인접 정점들을 처리헀으므로 탐색을 계속할 다음 정점을 찾기 위해 deQueue하여 B를 받음

vertex = deQueue();

4. 정점 B에서 방문하지 않은 모든 인접 정점 D, E를 방문하고 큐에 enQueue

visited[D&E] = true;

D & E 방문

enQueue(D & E);

5. 정점 B에 대한 인접 정점을 처리했으므로 탐색을 계속할 다음 정점을 찾기위해 큐를 deQueue

vertex = deQueue();

6. 정점 C에 방문하지 않은 정점이 없으므로 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue

vertex = deQueue();

7. 정점 D에 방문하지 않은 정점 G를 방문하고 큐에 enQueue

visited[G] = true;

G 방문

enQueue(G);

8. 정점 D에 대한 인접 정점들을 처리했으므로 탐색을 계속할 다음 정점을 찾기위해 큐를 deQueue

vertex = deQueue();

9. 정점 E에는 방문하지 않은 인접 정점이 없으므로 탐색을 계속할 다음 정점을 찾기 위해 큐를 deQueue

vertex = deQueue();

10. 정점 G에서 방문하지 않은 인접 정점 F를 방문하고 큐에 enQueue

visited[F] = true;

F 방문

enQueue(F);

11. 정점 G에 대한 인접 정점을 처리했으므로 탐색을 계속할 정점을 찾기 위해 큐를 deQueue

vertex = deQueue();

12. 정점 F는 모든 인접 정점을 방문했으므로 다음 정점을 찾기 위해 deQueue, 하지만 큐가 공백이므로 탐색 종료

링크드 리스트로 표현된 너비 우선 탐색 예제를 봅시다.

 * Graph2.java

package ssww;
 
 
public class Graph2 {
    GraphType g;
    
    public Graph2() {
        g = new GraphType();
        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 breadthFirstSearch(int v) {
        GraphNode tmp;
        Queue queue = new Queue();
        g.visited[v] = true;
        System.out.print(" " + (char)(v + 65));
        queue.enQueue(v);
        
        while (! queue.isEmpty()) {
            v = queue.deQueue();
            
            for (tmp = g.adjList[v]; tmp != null; tmp = tmp.link) {
                if (!g.visited[tmp.vertex]) {
                    g.visited[tmp.vertex] = true;
                    System.out.print(" " + (char) (tmp.vertex + 65));
                    queue.enQueue(tmp.vertex);
                }
            }
        }
    }
}
 
class QueueNode {
    int data;
    QueueNode link;
    
    public QueueNode(int data) {
        this.data = data;
    }
}
 
class Queue {
    QueueNode front, rear;
    
    public Queue() {
        front = null;
        rear = null;
    }
    
    public boolean isEmpty() {
        if (front == null) return true;
        return false;
    }
    
    public void enQueue(int data) {
        QueueNode node = new QueueNode(data);
        node.link = null;
        
        if (front == null) {
            front = node;
            rear = node;
        } else {
            rear.link = node;
            rear = node;
        }
    }
    
    public int deQueue() {
        QueueNode oldNode = front;
        int data;
        
        if (isEmpty()) return 0;
        else {
            data = oldNode.data;
            front = front.link;
            
            if (front == null) 
                rear = null;
            oldNode = null;
            
            return data;
        }
    }
}
 
 
 
 

 * GraphMain2.java

package ssww;
 
 
public class GraphMain2 {
 
    public static void main(String[] args) {
        Graph2 graph = new Graph2();
        
        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("\n 인접 리스트: ");
        graph.printAdjList();
        
        System.out.println("\n너비 우선 탐색: ");
        graph.breadthFirstSearch(0);
    }
 
}
 
 
 

* 클래스 다이어그램

 

end

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