Vector로 그래프 관계 표현

인접 행렬로 표현하기 어렵고 복잡하기에 인접리스트 형태인 vector를 사용하여 표현하면 편하다.

또한, 실제 값만 연결되어 있기에 조금 더 빠르다.

 

그러나 둘중 하나가 익숙하지 않다면 익숙하지 않은 것으로 사용하여 익히는 것이 좋은 것 같다.

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> map;
int num[4] = {6, 3, 7, 6};
int main()
{
    int n;
    cin >> n;
    for(int i=0; i<4; i++)
    {
        map.push_back({});
    }
    map[0] = {2, 3};
    map[1] = {2};
    map[2] = {3};
    map[3] = {0};
    for(int j=0; j<map[n].size(); j++)
        {
            cout << num[map[n][j]] << ' ' ;
        }
    return 0;
}

 

트리는 계층형 구조로 단방향이다.

#include <iostream>
#include <vector>
using namespace std;
char name[8] = "ABCEDGF";
vector<vector<int>> map(7);

void dfs(int now)
{
    cout << name[now] << ' ';
    for(int i=0; i<map[now].size(); i++)
    {
        int next = map[now][i];
        dfs(next);
    }
}
int main()
{
    map[0] = {1, 2, 3, 4};
    map[3] = {5, 6};
    dfs(0);
    return 0;
}