DFS(Depth First Search)

Pseudo code

DFS(v)

    for(i=0;i<n;i++)

        visited[i] = false

    Stack = creaetStack()

    Visited[v]  = true

    v 방문

    while(not isEmpty(stack))

        If(visited[v의 인접정점 w] == false)

            push(stack, v)

            visited[w] = true

            w 방문

            v = w

        Else

            v = pop(stack)

인접 리스트(재귀)

//DFS(인접리스트) 내가 구현한 코드 [재귀]

#include <iostream>

#include <vector>

using namespace std;

/*7 7 1

1 2

1 3

2 4

2 5

3 6

3 7

6 7

*/

class graph{

    public:

        int vertex;              //정점의 갯수

        vector<vector<int>> edge; //간선 목록

        vector<bool> visited;    //방문 여부

        graph(int n){

            vertex = n;

            edge.resize(n + 1);

            visited.resize(n + 1, false);

        }

        void dfs(int v){

            cout << v << " ";

            visited[v] = true;

            for (auto i : edge[v]){

                if (!visited[i])

                    dfs(i);

            }

        }

};

int main(){

    int n, m, v, i, a, b;

    graph* g;

    cin >> n >> m >> v;

    g = new graph(n);

    for (i = 0; i < m; i++){

        cin >> a >> b;

        g->edge[a].push_back(b);

        g->edge[b].push_back(a);

    }

    g->dfs(v);

}

인접리스트(스택)

//DFS(인접리스트) 내가 구현한 코드

//O(v+e)

#include <iostream>

#include <stack>

#include <vector>

#include <algorithm>

using namespace std;

/*

7 7 1

1 2

1 3

2 4

2 5

3 6

3 7

6 7

*/

class graph{

    public:

        int size;                //vertex 갯수

        vector<vector<int>> head; //각 vertex에 연결된 vertex들이 저장된 배열 (인접리스트)

        vector<int> visited;     //방문했는지

        graph(int size);

};

graph::graph(int size){

    this->size = size;

    this->head.resize(size + 1);

    this->visited.resize(size + 1, false);

}

void printGraph(graph* g){

    for (int i = 1; i <= g->size; i++){

        cout << i << " : ";

        for (auto j : g->head[i])

            cout << j << " ";

        cout << endl;

    }

}

void dfs(graph* g, int v){

    stack<int> s;

    bool flag;

    s.push(v);

    cout << v << " ";

    g->visited[v] = true;

    while (1){

        flag = true;

        for (auto i : g->head[v]){

            if (!g->visited[i]){ //해당 vertex를 방문 안했다면

                s.push(i);

                cout << i << " ";

                g->visited[i] = true;

                v = i; //해당 vertex의 head에서부터 다시 탐색하겠다는 의미

                flag = false;

                break;

            }

        }

        if (flag){ //flag가 true가 되는경우는 해당 vertex에 연결된 vertex들을 모두 방문했을때 stack에서 pop

            if (!s.empty()){

                v = s.top();

                s.pop();

            }

            else

                break;

        }

    }

    cout << endl;

}

int main(){

    int i, n, m, v, a, b;

    graph* g;

    cin >> n >> m >> v;

    g = new graph(n);

    for (i = 1; i <= m; i++){

        cin >> a >> b;

        g->head[a].push_back(b);

        g->head[b].push_back(a); //방향 연결리스트시 삭제

    }

    for (i = 1; i <= m; i++)

        sort(g->head[i].begin(), g->head[i].end()); //탐색시 오름차순으로 탐색할때 정렬해야함

    printGraph(g);

    dfs(g, v);

}

인접행렬(스택)

//DFS(인접행렬) 내가 구현한 코드

//O(v^2)

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

/*

7 7 1

1 2

1 3

2 4

2 5

3 6

3 7

6 7

*/

class graph{

public:

int v;//vertex의 갯수

int **adjArr;//인접 행렬

graph(int v);

};

graph::graph(int v){

this->v = v;

this->adjArr = new int *[v + 1];

for (int i = 0; i < v + 1; i++){

this->adjArr[i] = new int[v + 1];

memset(this->adjArr[i], 0, v + 1);

}

}

void dfs(graph* g, int v){

int i;

stack<int> s;

vector<bool> check;

check.resize(g->v + 1, false);

s.push(v);

check[v] = true;

cout << v << " ";

while (!s.empty()){

v = s.top();

for (i = 1; i < g->v + 1; i++){//방문한 vertex의 모든 vertex을 탐색

if (g->adjArr[v][i] == 1){//방문한 vertex에 연결된 vertex일때

if (check[i] == false){//연결된 vertex가 방문되지 않았을때

s.push(i);

check[i] = true;

cout << i << " ";

v = i; //해당 vertex를 탐색

break;

}

}

}

if (i == g->v + 1)s.pop();//stack의 top에 있는 vertex부터 다시 탐색

}

}

int main(){

int n, m, v, i, a, b;

cin >> n >> m >> v;

graph* g = new graph(n);

for (i = 0; i < m; i++){

cin >> a >> b;

g->adjArr[a][b] = 1;

g->adjArr[b][a] = 1;

}

dfs(g, v);

}