Graph - BFS(Breadth-First Search : 너비 우선 탐색) 구현

BFS

1. BFS(Breadth-First Search : 너비 우선 탐색)

시작 정점으로부터 가까운 정점들을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법.

방문한 정점과 인접한 정점들 중 방문하지 않은 정점을 큐(FIFO)에 삽입.

 

https://commons.wikimedia.org/wiki/File:Animated_BFS.gif

File:Animated BFS.gif - Wikimedia Commons

 

노드를 넓게 탐색한다.
BFS는 시작 정점으로부터 다른 정점까지의 간선의 수를 최소로 하는 경로를 구한다.

# BFS 활용 사례

• 라우팅(routing) : 통신망에서 홉 카운트를 최소로 하는 경로
• 네트워크 브로드캐스트

 

 

2. BFS 장단점

# BFS 장점

• 답이 되는 경로가 여러 개인 경우에도 최단경로 보장

# BFS 단점

• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.

 

 

3. 인접 리스트를 이용한 BFS 구현 (Java)

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 Queue {
    public Node first; //큐의 맨 앞 노드
    public Node last; //큐의 마지막 노드
    public int size; //큐 사이즈
    
    //큐에 정점 v를 last로 삽입
    public void enqueue(int v) {
        Node new_node = new Node();
        new_node.vertex = v;
        new_node.next = null;
        
        if(size == 0)
            first = last = new_node;
        else {
            last.next = new_node;
            last = new_node;
        }
        size++;
    }
    
    //큐에서 (first) 삭제 (FIFO)
    public int dequeue() {
        int v = first.vertex;
        first = first.next;
        
        size--;
        
        if(size == 0) last = null;
        
        return v;
    }
}
 
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 BFS {
    public boolean[] visited; //정점의 방문여부
    public int[] edgeTo; //DFS에 포함되는 간선(edgeTo[i]->i)
    
    //시작정점을 s로 하는 너비우선탐색
    public BFS(Graph G, int s) {
        visited = new boolean[G.V];
        edgeTo = new int[G.V];
        Queue q = new Queue();
        visited[s] = true;
        
        q.enqueue(s); 
        
        while(q.size > 0) {
            int v = q.dequeue();
            System.out.print(v+ " "); //방문순서:코드 확인용
            Node node = G.adj[v].head; 
            
            while(node != null) {
                int w = node.vertex;
                
                if(!visited[w]) { //정점 w를 아직 방문하지 않았으면
                    edgeTo[w] = v;
                    visited[w] = true;
                    q.enqueue(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("<BFS>");
            BFS bfs = new BFS(g, 0);
            System.out.println("");
            for(int v=0; v< g.V; v++) {
                System.out.println(v + " | " + bfs.edgeTo[v]);
            }
        } catch(IOException e) {
            System.err.println("File Error");;
            System.exit(1);
        }
    }
}