그래프 DFS 와 BFS

그래프 DFS(깊이우선탐색) 와 BFS(너비우선탐색)

---

1. 시작전

---

그래프를 구현하는 방법 중에는 크게 두 가지가 있습니다. 첫번째는 인접행렬을 이용하는 방법이고, 두번째는 인접리스트를 이용하는 방법입니다. 이 두가지 방법중 인접행렬을 이용한 DFS 와 BFS를 구현해보겠습니다.

---

2.DFS(깊이우선탐색)

---

package graph;
 
import java.util.Stack;
 
public class DFS {
    class Vertex{
        public char label;
        public boolean visited;
        public Vertex(char label) {
            this.label=label;
            this.visited=false;
        }
    }
    private final int maxVertices=20;
    private Vertex[] vertexList;
    private int Matrix[][];
    private int vertexCount;
    private Stack stack;
    public DFS() {
        vertexList=new Vertex[maxVertices];
        Matrix=new int[maxVertices][maxVertices];
        vertexCount=0;
        for(int y=0;y<maxVertices;y++) {
            for(int x=0;x<maxVertices;x++) {
                Matrix[x][y]=0;
            }
        }
        stack=new Stack();
    }
    public void addVertex(char label) {
        vertexList[vertexCount++]=new Vertex(label);
    }
    public void addEdge(int start, int end) {
        Matrix[start][end]=1;
        Matrix[end][start]=1;
    }
    public void displayVertex(int v) {
        System.out.println(vertexList[v].label);
    }
    public void dfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        stack.push(n-1);
        while(!stack.isEmpty()) {
            int v=getAdjUnvisitedVertex((int) stack.peek());
            if(v==-1) stack.pop();
            else {
                vertexList[v].visited=true;
                displayVertex(v);
                stack.push(v);
            }
        }
    }
    public int getAdjUnvisitedVertex(int v) {
        for(int j=0;j<vertexCount;j++) {
            if(Matrix[v][j]==1 && vertexList[j].visited==false) return j;
        }
        return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        DFS d=new DFS();
        d.addVertex('1');
        d.addVertex('2');
        d.addVertex('3');
        d.addVertex('4');
        d.addVertex('5');
        d.addVertex('6');
        d.addVertex('7');
        
        d.addEdge(0,1); //1->2
        d.addEdge(1,3); //2->4
        d.addEdge(0,2); //1->3
        d.addEdge(2,4); //3->5
        d.addEdge(2,5); //3->6
        d.addEdge(2,6); //3->7
        //1번 정점부터 방문시작
        d.dfs(1);
    }
 
}//결과 : 1 2 4 3 5 6 7
 

설명:  1번 정점부터 시작하므로 스택에 1번정점을 넣어준다. 그리고 스택에서 peek을 하여 1번정점을 꺼내어 1번정점에 대한 인접행렬의 행을 탐색하여 첫번째로 나오는 visited가 false인 연결정점(2번정점)을 visited=true로 바꿔주고 스택에 넣어준다. 그리고 다시 스택에서 peek을 하여 이전에 넣었던 2번정점을 읽어와 2번정점에 대한 인접행렬 행을 읽어 첫번째로 나오는 visited가 false인 연결정점(4번정점)을 visited=true로 바꿔 주고 스택에 넣어준다. 이런 과정을 진행하다가 막다른 지점이 나오면(4번정점) 그에 대한 인접행렬의 행에서 visited가 false 인접한 정점이 존재하지 않으므로 스택에서 pop해주어 백트래킹을 진행한다. 그러다 1번정점에서 다시 visited가 false 인접정점이 존재하므로 위의 과정을 반복하게 된다.

---

3.BFS(너비우선탐색)

---

package graph;
 
 
import java.util.LinkedList;
import java.util.Queue;
 
import graph.DFS.Vertex;
 
public class BFS {
    class Vertex{
        public char label;
        public boolean visited;
        public Vertex(char label) {
            this.label=label;
            this.visited=false;
        }
    }
    private final int maxVertices=20;
    private Vertex[] vertexList;
    private int Matrix[][];
    private int vertexCount;
    private Queue queue;
    public BFS() {
        vertexList=new Vertex[maxVertices];
        Matrix=new int[maxVertices][maxVertices];
        vertexCount=0;
        for(int y=0;y<maxVertices;y++) {
            for(int x=0;x<maxVertices;x++) {
                Matrix[x][y]=0;
            }
        }
        queue=new LinkedList();
    }
    public void addVertex(char label) {
        vertexList[vertexCount++]=new Vertex(label);
    }
    public void addEdge(int start, int end) {
        Matrix[start][end]=1;
        Matrix[end][start]=1;
    }
    public void displayVertex(int v) {
        System.out.println(vertexList[v].label);
    }
    public void bfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        queue.offer(n-1);
        int v2;
        while(!queue.isEmpty()) {
            int v1=(int) queue.poll();
            while((v2=getAdjUnvisitedVertex(v1))!=-1) {
                vertexList[v2].visited=true;
                displayVertex(v2);
                queue.offer(v2);
            }
        }
    }
    public int getAdjUnvisitedVertex(int v) {
        for(int j=0;j<vertexCount;j++) {
            if(Matrix[v][j]==1 && vertexList[j].visited==false) return j;
        }
        return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BFS d=new BFS();
        d.addVertex('1');
        d.addVertex('2');
        d.addVertex('3');
        d.addVertex('4');
        d.addVertex('5');
        d.addVertex('6');
        d.addVertex('7');
        
        d.addEdge(0,1); //1->2
        d.addEdge(1,3); //2->4
        d.addEdge(0,2); //1->3
        d.addEdge(2,4); //3->5
        d.addEdge(2,5); //3->6
        d.addEdge(2,6); //3->7
        d.bfs(1);
    }
 
}//결과: 1 2 3 4 5 6 7
 

설명: 시작정점 1번을 방문후 큐에 삽입해준다. 그리고 큐에서 poll을 해서 1번정점을 빼주고 1번노드 다음레벨에 해당하는(인접하고있는) 정점들을 모두 방문 후 큐에 삽입해준다.(2번정점 3번정점) 그리고 큐에서 poll을 해서 2번정점을 빼주고 2번 정점 다음레벨에 해당하는 정점들을 모두 큐에 삽입해준다.(4번정점) 그다음 큐에서 poll을 해 3번 정점을 빼주고 3번 정점 다음레벨에 해당하는 정점들을 모두 큐에 삽입해준다.(5,6,7번정점).. 이과정을 반복해준다.

---

4. 백준 1260번 DFS와 BFS  

---

package graph;
 
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
 
public class DFSBFS {
    class Vertex{
        public String label;
        public boolean visited;
        public Vertex(String label) {
            this.label=label;
            this.visited=false;
        }
    }
    private final int maxVertices=1000;
    private Vertex[] vertexList;
    private int Matrix[][];
    private int vertexCount;
    private Stack stack;
    private Queue queue;
    public DFSBFS() {
        vertexList=new Vertex[maxVertices];
        Matrix=new int[maxVertices][maxVertices];
        vertexCount=0;
        for(int y=0;y<maxVertices;y++) {
            for(int x=0;x<maxVertices;x++) {
                Matrix[x][y]=0;
            }
        }
        stack=new Stack();
        queue=new LinkedList();
    }
    public void addVertex(String label) {
        vertexList[vertexCount++]=new Vertex(label);
    }
    public void addEdge(int start, int end) {
        Matrix[start][end]=1;
        Matrix[end][start]=1;
    }
    public void displayVertex(int v) {
        System.out.print(vertexList[v].label+" ");
    }
    public void dfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        stack.push(n-1);
        while(!stack.isEmpty()) {
            int v=getAdjUnvisitedVertex((int) stack.peek());
            if(v==-1) stack.pop();
            else {
                vertexList[v].visited=true;
                displayVertex(v);
                stack.push(v);
            }
        }
        System.out.println();
        for(int j=0;j<vertexCount;j++) {
            vertexList[j].visited=false;
        }
    }
    public void bfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        queue.offer(n-1);
        int v2;
        while(!queue.isEmpty()) {
            int v1=(int) queue.poll();
            while((v2=getAdjUnvisitedVertex(v1))!=-1) {
                vertexList[v2].visited=true;
                displayVertex(v2);
                queue.offer(v2);
            }
        }
        System.out.println();
        for(int j=0;j<vertexCount;j++) {
            vertexList[j].visited=false;
        }
    }
    public int getAdjUnvisitedVertex(int v) {
        for(int j=0;j<vertexCount;j++) {
            if(Matrix[v][j]==1 && vertexList[j].visited==false) return j;
        }
        return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        DFSBFS ma=new DFSBFS();
        int n=sc.nextInt();
        int m=sc.nextInt();
        int v=sc.nextInt();
        
        for(int i=0;i<n;i++) {
            ma.addVertex(i+1+"");
        }
        while(m!=0) {
            ma.addEdge(sc.nextInt()-1,sc.nextInt()-1);
            m--;
        }
        ma.dfs(v);
        ma.bfs(v);
    }
 
}