[C++] DFS 구현해보기

오늘 수업때 인접리스트로 DFS구현을 해보라 하셨는데 뭔가 생각한대로 잘되서 기분이가 좋았음

#include <iostream>
#include <vector>

using namespace std;

void 재귀(int start, const vector<vector<int>>& edges, vector<bool>& visited)
{
    if (visited[start]) return;
    visited[start] = true;
    cout << start << ", ";
    for (int i = 0; i < edges[start].size(); i++)
    {
        재귀(edges[start][i], edges, visited);
    }
}

void DFS(int start, const vector<vector<int>>& edges)
{
    vector<bool> visited(edges.size(), false);
    재귀(start, edges, visited);
}

int main()
{
    vector<vector<int>> edges;
    edges.push_back({ 1, 2 });      //0
    edges.push_back({ 3, 6, 7 });   //1
    edges.push_back({ 4, 5 });      //2
    edges.push_back({ 6, 7 });      //3
    edges.push_back({ 8, 9 });      //4 
    edges.push_back({ 10, 11 });    //5
    edges.push_back({ });           //6
    edges.push_back({ });           //7
    edges.push_back({ });           //8
    edges.push_back({ });           //9
    edges.push_back({ });           //10
    edges.push_back({ });           //11

    cout << "DFS: ";
    DFS(0, edges);
    cout << endl;

    return 0;
}

 

위와 같은 그래프가 있다 하고 인접리스트를 작성했다 ㅋㅋ;

 

근데 실수로 무향그래프인데 단방향그래프라 생각하고 짜버림 그리고 너무 쉽게 생겨먹음

그래서 좀 이상한 무방향그래프를 가져와봄

이걸 기반으로 해보자

 

된다 ㅋㅋ 기모띠 기분 굿 나이스입니다 좋은 하루 되세요~