그래프

트리는 사이클이 없는 연결 그래프이다.

그래프는 노드와 노드를 연결하는 간선을 하나로 모은 것이다.

사이클이 없는 그래프를 비순환 그래프라고 한다.

모든 정점 간에 경로가 존재하는 그래프를 연결 그래프라고 한다.

--

인접 리스트

#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
    node *next, *prev;
    int num;
};
 
node *head[9], *foot;
 
void init();
 
int main()
{
    node *now, *newnode;
    init();
    int n, x, y, z;
    printf("1부터 9까지의 거점 사이에 존재하는 경로를 기록한다.\n경로의 갯수는?  ");
    for (scanf("%d", &n); n--;)
    {
        printf("경로의 출발 거점과 도착 거점을 적어주세요 : ");
        scanf("%d %d", &x, &y);
        printf("경로가 일방통행이면 1, 아니면 2를 입력해주세요 : ");
        scanf("%d", &z);
        while(z--)
        {
            now = head[x-1];
            while (1)
            {
                if (now->next->num == 0)
                {
                    newnode = new node;
                    newnode->prev = now;
                    newnode->next = foot;
                    now->next = newnode;
                    newnode->num = y;
                    break;
                }
                else
                {
                    if (now->next->num == y)
                        break;
                    else
                        now = now->next;
                }
            }
            swap(x, y);
        }
    }
    for (int i = 0; i < 9; ++i)
    {
        printf("%d : ", i + 1);
        now = head[i];
        while (1)
        {
            if (now->next->num != 0)
            {
                printf("%d  ", now->next->num);
                now = now->next;
            }
            else
            {
                printf("\n");
                break;
            }
        }
    }
}
void init()
{
    foot = new node;
    foot->num = 0;
    foot->next = foot;
    for (int i = 0; i < 9; ++i)
    {
        head[i] = new node;
        head[i]->next = foot;
        head[i]->prev = head[i];
        head[i]->num = 0;
    }
    
}

--

인접 행렬

#include <cstdio>
int main()
{
    bool num[9][9];
    for (int i = 0; i < 9; ++i)
        for (int j = 0; j < 9; ++j)
            num[i][j] = 0;
    int n, x, y, z;
    printf("1부터 9까지의 거점 사이에 존재하는 경로를 기록한다.\n경로의 갯수는?  ");
    for (scanf("%d", &n); n--;)
    {
        printf("경로의 출발 거점과 도착 거점을 적어주세요 : ");
        scanf("%d %d", &x, &y);
        printf("경로가 일방통행이면 1, 아니면 2를 입력해주세요 : ");
        scanf("%d", &z);
        if (z == 1)
            num[x - 1][y - 1] = 1;
        else if (z == 2)
        {
            num[x - 1][y - 1] = 1;
            num[y - 1][x - 1] = 1;
        }
    }
    for (int i = 0; i < 9; ++i)
    {
        printf("%d : ", i + 1);
        for(int j = 0; j < 9; ++j)
            if (num[i][j])
                printf("%d   ", j + 1);
        printf("\n");
    }
}

--

그래프 탐색

깊이 우선 탐색(DFS) : 각 분기를 완벽하게 탐색 후 다른 분기를 탐색

너비 우선 탐색(BFS) : 루트 노드의 인접한 노드들 부터 탐색 후, 그 노드들의 인접한 노드를 이어가듯 탐색

--

DFS

DFS를 재귀로 하면, 저번 글에 작성했던 전위, 중위, 후위 순회와 같다고 보면 됨.

BFS는 큐를 이용

#include <cstdio>
#include <queue>
using namespace std;
 
void dfs(int nx);
void bfs(int nx);
 
bool num1[9][9], num2[9][9];
queue<int> q;
 
int main()
{
    for (int i = 0; i < 9; ++i)
        for (int j = 0; j < 9; ++j)
        {
            num1[i][j] = 0;
            num2[i][j] = 0;
        }
    int n, x, y;
    printf("1부터 9까지의 거점 사이에 존재하는 경로를 기록한다.\n경로의 갯수는?  ");
    for (scanf("%d", &n); n--;)
    {
        printf("경로의 출발 거점과 도착 거점을 적어주세요 : ");
        scanf("%d %d", &x, &y);
        num1[x-1][y-1] = 1;
        num1[y-1][x-1] = 1;
        num2[x-1][y-1] = 1;
        num2[y-1][x-1] = 1;
    }
    printf("\n탐색을 시작할 경로의 시작점을 적어주세요 : ");
    scanf("%d", &n);
    printf("\n\ndfs : ");
    dfs(n - 1);
    printf("\n\nbfs : ");
    bfs(n - 1);
    printf("\n");
}
void dfs(int nx)
{
    printf("%d   ", nx + 1);
    for (int i = 0; i < 9; ++i)
        num1[i][nx] = 0;
    for (int i = 0; i < 9; ++i)
        if (num1[nx][i])
            dfs(i);
}
void bfs(int nx)
{
    int a;
    q.push(nx);
    for (int i = 0; i < 9; ++i)
        num2[i][nx] = 0;
    while (!q.empty())
    {
        a = q.front();
        q.pop();
        printf("%d   ", a + 1);
        for (int i = 0; i < 9; ++i)
            if (num2[a][i])
            {
                q.push(i);
                for (int j = 0; j < 9; ++j)
                    num2[j][i] = 0;
            }
    }
}

--

양방향 탐색

이건 코딩까진 안하겠음

너비 우선 탐색 시 출발지와 도착지에서 동시에 너비 탐색을 하면 두 탐색 지점이 충돌하는 경우가 최단 경로가 됨.

4단계 떨어진 곳이면 출발지에서 2단계, 도착지에서 2단계로 2단계만에 찾을 수 있음.

그런 식으로 같은 단계 깊이동안 찾을 경로의 길이가 늘어난다고 표현되어 있음.