02)DFS[Depth-First Search, 깊이 우선탐색]

▣Depth-First Search(깊이우선탐색)

: 그래프의 모든정점을 방문하는 알고리즘 중 하나이다.

-> 탐색의 기준 : 자신과 인접한 간선을 검사하여 visit하지 않은 정점을 찾아 visit해 나아간다.

                    : 더이상 visit할 정점이 없을 때 까지 반복한다.

<알고리즘 진행 순서>

                    

1번 정점에서 시작하여 2->3->5->7->6의 순서로 visit 가능한 정점까지 진행한다.

진행이 끝나면 다른 정점이 있는 곳까지 빠져나온 후 기존의 과정을 반복한다.

<소스코드>

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
 
#define MAX_VERTEX 101
#define VISIT 1
#define UN_VISIT 0
#define CONNECTED 1
using namespace std;
/*
기본적으로 행렬기반으로 구현
v : vertex
e : edge
n : vertex의 개수
m : edge의 개수

Edge_table : 간선 연결 여부 테이블
Vertex_table : 정점 visit 여부 확인 테이블
Finish_table : 탐색이 완료된 정점 순서대로 저장하는 테이블
Visit_table : visit 된 순서대로 vertex를 저장

UN_VISIT : 아직 탐색
VISIT : 자식 탐색이 종료
*/
int Edge_table[MAX_VERTEX][MAX_VERTEX];
int Vertex_table[MAX_VERTEX];
 
void DFS(int v_i) {
    Vertex_table[v_i] = VISIT;
    cout << v_i << " ";
    for (int i = 0; i < MAX_VERTEX; i++) {
        if (Edge_table[v_i][i] == CONNECTED && Vertex_table[i] == UN_VISIT) {
            DFS(i);
        }
    }
}
 
 
int main() {
    int n;
    int m;
    cout << "vertex 개수 : ";
    cin >> n;
    cout << "edge 개수 : ";
    cin >> m;
 
    cout << "edge 정보 입력" << endl;
    for (int i = 0; i < m; i++) {
        int v_1, v_2;
        cin >> v_1 >> v_2;
        Edge_table[v_1][v_2] = 1;
    }
 
    memcpy(Vertex_table, Vertex_table + MAX_VERTEX, UN_VISIT);
    for (int i = 1; i <= n; i++) {
        if (Vertex_table[i] == UN_VISIT) {
            DFS(i);
        }
    }
    cout << endl;
    return 0;
}

: 그래프 자체는 배열을 기반으로 구현하였습니다.

<성능>

모든 정점을 방문 하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)이다.

(그림 참고)https://www.codeground.org/common/popCodegroundNote