C++] 인접 리스트 구현

 

 

 

 

인접리스트는 그래프의 한 종류입니다. 

 

인접리스트를 쓰는 가장 큰 이유는 바로 탐색 때문인데, 우리는 인접리스트를 통해 연결된 모든 노드들을 확인할 수 있습니다.

 

우선 아래의 그림의 그래프를 만들어 보겠습니다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

enum { A, B, C, D ,E};

void AddGraph(vector<int> * v, int x, int y) {
    v[x].push_back(y);
    v[y].push_back(x);
}

int main(void) {

    vector<int> g[5];

    AddGraph(g, A, B);    //A <-> B 연결
    AddGraph(g, A, D);    //A <-> D 연결
    AddGraph(g, B, C);    //B <-> C 연결
    AddGraph(g, C, D);    //C <-> D 연결
    AddGraph(g, D, E);    //D <-> E 연결
    AddGraph(g, E, A);    //E <-> A 연결

    for (int i = 0; i <= E; i++) {
        printf("%c와 연결된 정점 : ", i + 65);
        for_each(g[i].begin(), g[i].end(), [&](auto& s) {
            printf("%c ", s + 65);
        });
        cout << endl;
    }

    return 0;
}

 

 

위 코드는 백터를 배열(2차원 백터)로 선언해 해당 노드마다 연결한 모습입니다.

구현 방법은 간단하게 서로 연결시켜주면 됩니다. 

 

 

그럼 다음은 좀 더 노드 수를 늘리고 탐색하는 코드를 만들어 보겠습니다.

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <stack>

using namespace std;

enum { A, B, C, D, E, F };

void AddGraph(vector<int> * v, int x, int y) {
    v[x].push_back(y);
    v[y].push_back(x);
}

void ShowGraphLine(vector<int> * v) {
    for (int i = 0; i <= F; i++) {
        printf("%c와 연결된 정점 : ", i + 65);
        for_each(v[i].begin(), v[i].end(), [&](auto& s) {
            printf("%c ", s + 65);
            });
        cout << endl;
    }
}

void ShowGraphDFS(vector<int> * v, int index) {
    stack<int> s;
    bool flag[6] = { false, };

    s.push(index);
    flag[index] = true;
    printf("%c ", index + 65);

    while (!s.empty()) {
        int num = s.top();
        s.pop();
        for (int i = 0; i < v[num].size(); i++) {
            if(flag[v[num][i]] == false){
                printf("%c ", v[num][i] + 65);
                flag[v[num][i]] = true;
                s.push(num);
                s.push(v[num][i]);
                break;
            }
        }
    }
    cout << endl;
}

int main(void) {

    vector<int> g[6];

    AddGraph(g, A, B);    //A <-> B 연결
    AddGraph(g, A, D);    //A <-> D 연결
    AddGraph(g, B, C);    //B <-> C 연결
    AddGraph(g, C, D);    //C <-> D 연결
    AddGraph(g, D, E);    //D <-> E 연결
    AddGraph(g, E, F);    //E <-> A 연결


    ShowGraphLine(g);

    ShowGraphDFS(g, A);
    ShowGraphDFS(g, B);
    ShowGraphDFS(g, F);


    return 0;
}
​

 

 

해당 코드는 노드들을 연결한 후 노드 하나를 기준으로 깊은탐색을 하는 코드입니다.

 

방문한 노드는 true로 설정해 두어 중복탐색을 막는 코드가 되겠습니다.

 

해당 코드는 for문과 재귀함수를 통해 구현이 가능한데, 저는 for문을 이용해 구현했습니다.

 

그럼 코드에 대해 설명해 보겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

모든 요소들을 다 찾았으므로 이제 스택에 있는 요소들을 빼주면 됩니다.

 

 

 

 

 

 

 

 

 

이런식으로 계속 된다면 결국 스택에는 모든 요소들이 제거가 되며 함수가 종료됩니다.

(그리는거 너무 빡세다... ㅠ.ㅠ)

 

이렇게 되면 연결되어 있는 모든 요소들을 탐색하는 완전 탐색이 완료가 됩니다.

 

여기에 가중치를 추가하고 조금만 수정해 준다면 위상정렬로도 사용이 가능합니다.

 

이 글을 보고 도움이 되셨으면 좋겠습니다!!.

 

긴 글 봐주셔서 감사합니다.