[Data Structure] 그래프와 기본 연산 (BFS, DFS)

그래프

그래프 정의와 용어

• 그래프 G는 공집합이 아닌 정점 집합 V와 간선 집합 E로 구성된다.
  • G = (V,E)
• 두 정점이 간선으로 연결되었다면 두 정점은 인접(adjacent)하다고 한다.
• 자기 자신을 간선으로 연결하는 것을 Self-loop(또는 Self-edge)라고 한다.
• V(G`)⊆ V(G)이고 E(G`)⊆ E(G)인 그래프 G`를 그래프 G의 부분 그래프(subgraph)라 한다.

G1, G2, G3는 모두 G의 부분 그래프

• 정점 u부터 정점 v까지의 경로(path)는 정점 순서 u, i1, i2, ..., ik, v를 말한다.
• 한 경로의 길이(length)는 경로 상에 있는 간선의 수이다.
• 경로 상에서 처음과 마지막을 제외한 모든 정점들이 서로 다를 때, 그 경로를 단순 경로(simple path)라 한다.
• 처음과 마지막 정점이 같은 단순 경로를 사이클(cycle)이라 한다.

무방향 그래프(undirected graph)

• 방향 없는 간선을 가짐
• Self-loop(Self-edge) 불가능
• (u, v) = (v, u)

방향 그래프(directed graph, Digraph)

• 방향 있는 간선을 가짐
• Self-loop(Self-edge) 가능
• <u, v> ≠ <v, u>

https://yozm.wishket.com/magazine/detail/2411/

최대 간선 개수

• 무방향 그래프의 정점이 n개일 때, 간선의 개수는 n(n-1) / 2
• 방향 그래프의 정점이 n개일 때, 간선의 개수는 n(n-1)

#pragma once

struct Edge // 정점의 정보를 하나로 묶을 구조체
{
    int u, v, weight;

    bool operator< (const Edge& other) // 비교
    {
        return weight < other.weight;
    }

    bool operator> (const Edge& other) // 비교
    {
        return weight > other.weight;
    }

    bool operator<= (const Edge& other) // 비교
    {
        return weight <= other.weight;
    }

    bool operator>= (const Edge& other) // 비교
    {
        return weight >= other.weight;
    }

    bool operator== (const Edge& other)
    {
        return (u == other.u && v == other.v) || (u == other.v && v == other.u); // 무방향 그래프이므로 순서 바뀌어도 같음
    }

    bool operator!= (const Edge& other)
    {
        return !operator==(other);
    }
};

#include <iostream>
#include <algorithm>
#include <vector>
#include "Edge.hpp"

#define INF 99999999

class Graph
{
public:
    // 그래프에 정점이 없으면 true 리턴
    bool IsEmpty() const
    {
        return n == 0;
    }

    // 정점 수 리턴
    int NumberOfVertices() const
    {
        return n;
    }

    // 간선 수 리턴
    int NumberOfEdges() const
    {
        return e;
    }

    // 정점 u에 인접한 간선 수 리턴
    virtual int Degree(int u) const = 0; // 순수 가상 함수

    // 그래프에 간선 (u,v)가 있으면 true 리턴
    virtual bool ExistsEdge(int u, int v) const = 0;

    // 간선 (u,v)를 그래프에 삽입
    virtual void InsertEdge(int u, int v) = 0;

    // 가중치 w인 간선 (u,v)를 그래프에 삽입
    virtual void InsertEdge(int u, int v, int w) = 0;

    // 그래프에서 간선 (u,v) 삭제
    virtual void DeleteEdge(int u, int v) = 0;

protected:
    int n; // 정점의 수
    int e; // 간선의 수
    std::vector<Edge> edges; // 모든 간선 집합
};

 

그래프 표현법

인접 행렬(Adjacency Matrix)

• 정점이 n개 있을 때, n x n 정방 행렬(2차원 배열)로 인접 여부를 표현한다.
• 정점 i와 j 사이에 간선이 있을 경우 1, 없는 경우 0을 저장

• 가중치 그래프의 경우 간선이 있는 경우 가중치 값, 없는 경우 0을 저장
• 무방향 그래프일 때는 인접 행렬이 대칭이고, 방향 그래프일 때는 대칭이 아닐 수도 있다.
• 인접 행렬의 모든 간선을 조사하는데 O(n^2)의 시간이 필요
  • 간선이 많지 않은 희소 그래프(sparse graph)의 경우 인접 행렬보다 인접 리스트가 더 효율적

가중치 없는 무방향 그래프

가중치 있는 무방향 그래프

가중치 없는 방향 그래프

가중치 있는 방향 그래프

#include "Graph.hpp"

class MatrixWGraph : public Graph
{
public:
    MatrixWGraph(int vertexCnt)
    {
        n = vertexCnt; // 정점 개수 설정
        e = 0; // 간선 개수 설정

        // 이차원 배열 동적 할당
        adjMatrix = new int*[n + 1];
        for (int i = 0; i <= n; i++)
        {
            adjMatrix[i] = new int[n + 1];
            std::fill(adjMatrix[i], adjMatrix[i] + n + 1, 0); // 0으로 채우기
        }
    }

    ~MatrixWGraph()
    {
        for (int i = 0; i <= n; i++)
        {
            delete adjMatrix[i];
        }
        delete adjMatrix;
    }

    void PrintAdjMatrix()
    {
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                std::cout << adjMatrix[i][j] << " ";
            }
            std::cout << "\n";
        }
    }

    // 정점 u에 인접한 간선 수 리턴
    virtual int Degree(int u) const
    {
        int edgeCnt = 0;
        for (int i = 0; i < n+1; i++)
        {
            if (adjMatrix[u][i] != 0)
                edgeCnt++;
        }

        return edgeCnt;
    }

    // 그래프에 간선 (u,v)가 있으면 true 리턴
    virtual bool ExistsEdge(int u, int v) const
    {
        if (adjMatrix[u][v] != 0)
            return true;
        else
            return false;
    }

    // 간선 (u,v)를 그래프에 삽입
    virtual void InsertEdge(int u, int v)
    {
        adjMatrix[u][v] = 1; // 무방향 그래프
        adjMatrix[v][u] = 1;
        edges.push_back({u, v, 1}); // 간선 리스트 추가
    }

    // 가중치가 w인 간선 (u,v)를 그래프에 삽입
    virtual void InsertEdge(int u, int v, int w)
    {
        adjMatrix[u][v] = w; // 무방향 그래프
        adjMatrix[v][u] = w;
        edges.push_back({u, v, w}); // 간선 리스트 추가
    }

    // 그래프에서 간선 (u,v) 삭제
    virtual void DeleteEdge(int u, int v)
    {
        adjMatrix[u][v] = 0; // 무방향 그래프
        adjMatrix[v][u] = 0;
    }

private:
    int** adjMatrix; // 인접 행렬
};

인접 리스트(Adjacency List)

• 각 노드마다 연결 리스트를 가진다.
• i번째 연결 리스트는 i번째 노드와 인접한 정점들을 리스트로 연결한다.
• 각 체인에서의 정점들의 순서는 중요하지 않다.
• 인접 리스트의 노드 개수는
  • 무방향 그래프: 2 * E (출발, 도착 노드의 인접 리스트에 추가)
  • 방향 그래프: E (출발 노드의 인접 리스트에만 추가)
• 가중치 있는 그래프인 경우, 각 노드에 가중치 정보를 저장할 필드를 추가한다.

#include "Graph.hpp"
#include "../../Chapter4/4.10/DoublyLinkedList.hpp"

class LinkedWGraph : public Graph
{
public:
    LinkedWGraph(int vertexCnt)
    {
        n = vertexCnt; // 정점 개수 설정
        e = 0;
        adjList = new DoublyLinkedList<int>[n]; // 인접 리스트 할당
        for (int i = 0; i <= n; i++)
        {
            adjList[i].head = new BidirectionalNode<int>(i);
        }
    }

    ~LinkedWGraph()
    {
        delete adjList; // 인접 리스트 삭제
    }

    void PrintAdjList()
    {
        for (int i = 0; i <= n; i++)
        {
            std::cout << i << ": ";

            BidirectionalNode<int>* curr = adjList[i].head->right;
            while (curr)
            {
                std::cout << curr->data << " -> ";
                curr = curr->right;
            }
            std::cout << "nullptr\n";
        }
    }

    // 정점 u에 인접한 간선 수 리턴
    virtual int Degree(int u) const
    {
        int edgeCnt = 0;
        BidirectionalNode<int>* curr = adjList[u].head->right; // 뒤에 연결된 인접한 정점부터 시작
        while (curr)
        {
            edgeCnt++;
            curr = curr->right;
        }    
        return edgeCnt;
    }

    // 그래프에 간선 (u,v)가 있으면 true 리턴
    virtual bool ExistsEdge(int u, int v) const
    {
        BidirectionalNode<int>* curr = adjList[u].head;
        while (curr)
        {
            if (curr->data == v) // 연결된 인접 정점 중 v가 있으면
                return true;
            curr = curr->right;
        }

        return false; // 없는 경우
    }

    // 간선 (u,v)를 그래프에 삽입
    // 양방향 그래프이므로 양쪽에 삽입
    virtual void InsertEdge(int u, int v)
    {
        BidirectionalNode<int>* uVert = new BidirectionalNode<int>(u); // 새로운 정점 노드
        BidirectionalNode<int>* vVert = new BidirectionalNode<int>(v);
        adjList[u].Insert(vVert, adjList[u].GetLastNode()); // 리스트 맨 뒤에 추가
        adjList[v].Insert(uVert, adjList[v].GetLastNode());
        edges.push_back({u, v, 1});
    }

    // 가중치가 w인 간선 (u,v)를 그래프에 삽입
    // 양방향 그래프이므로 양쪽에 삽입
    virtual void InsertEdge(int u, int v, int w)
    {
        BidirectionalNode<int>* uVert = new BidirectionalNode<int>(u, w); // 새로운 정점 노드
        BidirectionalNode<int>* vVert = new BidirectionalNode<int>(v, w);
        adjList[u].Insert(vVert, adjList[u].GetLastNode()); // 리스트 맨 뒤에 추가
        adjList[v].Insert(uVert, adjList[v].GetLastNode());
        edges.push_back({u, v, w});
    }

    // 그래프에서 간선 (u,v) 삭제
    virtual void DeleteEdge(int u, int v)
    {
        BidirectionalNode<int>* vNode = adjList[u].Find(v);
        adjList[u].Delete(vNode);
    }
    
private:
    DoublyLinkedList<int>* adjList;
};

그래프의 기본 연산

DFS와 BFS를 활용하면 그래프 G=(V,E)와 V(G)의 한 정점 v가 주어졌을 때, 이 v에서 도달할 수 있는 G의 모든 정점들을 방문 할 수 있다.

깊이 우선 탐색 (Depth First Search, DFS) 

그래프에서 한쪽 방향으로 깊게 파고들며 탐색하는 알고리즘.

스택 또는 재귀 호출을 사용해 구현한다.

인접 행렬로 표현한 그래프의 경우에는 다음과 같다.

void DFSWrapper(int v)
{
    bool* visited = new bool[n + 1];
    DFS(v, visited);
    delete visited;
}

void DFS(int v, bool* visited)
{
    visited[v] = true;
    std::cout << v << " ";

    for(int i = 0; i <= n; i++)
    {
        if (adjMatrix[v][i] && !visited[i]) // 인접한 정점 중 방문하지 않은 정점이 있으면
            DFS(i, visited);
    }
}

인접 리스트로 표현한 그래프의 경우에는 다음과 같다.

// DFS
void DFSWrapper(int v)
{
    bool* visited = new bool[n + 1];
    DFS(v, visited);
    delete visited;
}

void DFS(int v, bool* visited)
{
    visited[v] = true; // 방문 처리
    std::cout << v << " ";

    BidirectionalNode<int>* curr = adjList[v].head->right; // 인접한 정점의 노드부터 시작
    while (curr)
    {
        if (!visited[curr->data]) // 방문하지 않았으면
            DFS(curr->data, visited);
        curr = curr->right;
    }
}

너비 우선 탐색 (Breadth First Search, BFS)

그래프의 같은 레벨에 있는 정점들을 순서대로 방문하는 알고리즘.

큐를 사용해 시작 정점부터 가까운 정점 순서대로 탐색 => 최단 거리 찾는데 유용

 

인접 행렬로 표현한 그래프의 경우에는 다음과 같다.

void BFS(int v)
{
    bool* visited = new bool[n + 1];

    std::queue<int> q;

    // 시작 정점 큐에 추가
    q.push(v);
    visited[v] = true;

    while (!q.empty())
    {
        int front = q.front();
        q.pop();
        std::cout << front << " ";

        for (int i = 0; i <= n; i++)
        {
            if (adjMatrix[front][i] && !visited[i]) // 인접한 정점 중 방문하지 않은 정점이 있다면
            {
                q.push(i);
                visited[i] = true; // 방문 처리
            }
        }
    }

    delete visited;
}

인접 리스트로 표현한 그래프의 경우에는 다음과 같다.

// BFS
void BFS(int v)
{
    bool* visited = new bool[n + 1];

    std::queue<int> q;

    // 시작 정점 큐에 추가
    q.push(v);
    visited[v] = true;

    while (!q.empty())
    {
        int front = q.front();
        q.pop();
        std::cout << front << " ";

        BidirectionalNode<int>* curr = adjList[front].head->right; // 인접한 정점의 노드부터 시작
        while (curr)
        {
            if (!visited[curr->data]) // 인접한 정점 중 방문 안 한 노드가 있으면
            {
                q.push(curr->data); // 큐 추가
                visited[curr->data] = true; // 방문 처리
            }
            curr = curr->right;
        }
    }

    delete visited;
}