비선형 구조 : 그래프 DFS, BFS, 다익스트라

선형 구조 : 자료를 순차적으로 나열한 형태

• 배열
• 연결 리스트
• 스택/큐

비선형 구조 : 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태

• 트리
• 그래프

 

그래프 구성 요소

정점(Vertex) : 데이터

간선(Edge) : 정점들을 연결하는데 사용

 

가중치 그래프 : 각 간선에 가중치(중요도, 거리등)가 있는 그래프

방향 그래프 : 정점간의 방향이 있는 그래프

 

구글

DFS 깊이 우선 탐색

Depth First Search

• 막다른 길(더이상 연결된 간선이 없을 때 까지)이 나올 때까지 정점을 계속 방문 하는 그래프
• 끝까지 갔다가 다시 시작 정점으로 돌아오는 부분은 재귀함수로 구현할 수 있다.
• 그래프의 전체적인 모양을 파악하기 쉽다.

void Dfs(int here)
{
    // 방문
    visited[here] = true;
    cout << "Visited : " << here << endl;

   //  모든 인접 정점을 순회한다
    for (int i = 0; i < adjacent[here].size(); i++)
    {
       // 아직 방문하지 않은 곳이 있으면 방문한다
       int there = adjacent[here][i];
       if (visited[there] == false)
          Dfs(there);
    }
}

BFS 너비 우선 탐색

Breadth First Search

• 시작정점기준 가까운 정점을 먼저 탐색하는 그래프(비슷한 깊이의 정점들이 비슷한 시기에 탐색되겠지?)
• 어쨌든 BFS또한 발견한 정점은 다시 방문할 필요가 없으므로, 큐로 구현하는 예약시스템을 통해 설계할 수 있다.
• 길찾기 알고리즘에 매우 적합하다.

void Bfs(int here)
{
    // 누구에 의해 발견 되었는지?
    vector<int> parent(6, -1);
    // 시작점에서 얼만큼 떨어져 있는지?
    vector<int> distance(6, -1);

    // 발견한 정점here 을 담을 큐
    queue<int> q;
    q.push(here);
    discovered[here] = true;

    // 초기 설정
    parent[here] = here;
    distance[here] = 0;

    while (q.empty() == false)
    {
        here = q.front();
        q.pop();

        cout << "Visited : " << here << endl;

        for (int there : adjacent[here])
        {
            if (discovered[there])
                continue;

            q.push(there);
            discovered[there] = true;

            // 부모 정점 = here
            parent[there] = here;
            // 시작점으로부터 거리 = 부모 정점의 거리 + 1
            distance[there] = distance[here] + 1;
        }
    }
}

Dijikstra 다익스트라 알고리즘

그래프에는 간선에 가중치(비용)를 줄 수 있다. 다만, DFS에는 가중치에 대응할 기능이 없다.

이를 해결하기 위한 알고리즘이 다익스트라 알고리즘이다.

(일단은 list로 구현했지만, 우선순위큐로 구현하는게 훨씬 효율적이다.(2중 반복문 때문))

while (discovered.empty() == false)
{
    // 제일 좋은 후보를 찾는다
    // 리스트 대신 우선순위 큐(priority_queue를 사용할 수 있음(이게 더 효율적))
    list<VertexCost>::iterator bestIt;
    int bestCost = INT32_MAX;

    for (auto it = discovered.begin(); it != discovered.end(); it++)
    {
        if (it->cost < bestCost)
        {
            bestCost = it->cost;
            bestIt = it;
        }
    }

    // 위 for문을 통해 찾은 bestIt를 방문
    int cost = bestIt->cost;
    here = bestIt->vertex;
    discovered.erase(bestIt);   // 방문할거니까 discovered에서 삭제

    // 방문하기전 더 짧은 경로를 뒤늦게 찾았다면 스킵.
    if (best[here] < cost)
        continue;

    // 방문!
    for (int there = 0; there < 6; there++)
    {
        // 연결되지 않았으면 스킵.
        if (adjacent[here][there] == -1)
            continue;

        // 더 좋은 경로를 과거에 찾았으면 스킵.
        int nextCost = best[here] + adjacent[here][there];
        if (nextCost >= best[there])
            continue;

        discovered.push_back(VertexCost{ there, nextCost });
        best[there] = nextCost;
        parent[there] = here;
    }
}

 

다익스트라는 DFS와 다르게 가장 효율적인(가까운) 정점부터 방문을 하기 때문에 가중치를 계산해서 가장 짧은 경로를 찾는 코드가 필요하다. 위 코드가 구현한 예시이다.