[그래프] DFS : 배열로 구현

DFS

: 깊이 우선 탐색으로 자식의 자식을 끝까지 탐색한 후 다시 돌아오는 방식.

기본적으로 정점과 간선의 개념을 알아야 한다.

 

- 정점 : 노드(?) 비슷한 개념 

- 간선 : 정점과 정점을 이으는 선.

 

 

Java 코드로 구현하면 다음과 같다.

package practice;

class dfsGraph {
    int num;
    // 2차원 배열로 간선 표현. 0/1 이면 정점을 연결하는 간선 없음/있음.
    int graph[][];
    boolean visited[];

    dfsGraph(int num) {
        this.num = num;
        this.graph = new int[num+1][num+1];
        this.visited = new boolean[num+1];
    }

    //연결 정점
    void putLine(int a, int b) {
        this.graph[a][b] = 1;
        this.graph[b][a] = 1;
    }

    // 방문 배열 초기화
    void initVisited() {
        for(int i=0; i<=this.num; i++) {
            visited[i] = false;
        }
    }

    //재귀 탐색
    void dfs(int idx) {
        this.visited[idx] = true;
        // 방문한 노드 프린트 
        System.out.print(idx+" ");

        for(int i=0; i<= this.num; i++) {
            // 연결된 다른 정점이 있고 && 방문하지 않았다면
            if(graph[idx][i]==1 && !visited[i]) {
                dfs(i);
            }
        }
    }
}


public class DFS2 {
    public static void main(String[] args) {

    }
}

기초만 세웠고 아직은 구현 전 예정.

추후 업로드 예정.