[Data Structures] 챕터12. 그래프

• 트리와 달리 그래프는 한 정점(Vertex)가 여러 다른 정점을 가리킬 수 있다
• 그래프는 두 정점이 서로를 가르킬 수 있다
• 연결된 상태를 간선(Edge)으로 표시한다

 

인접 행렬(Adjacent Matrix Graph)

---

• 인접행렬은 정점간 연결관계를 행렬로 표시한다
• 2차원 배열을 사용하여 정점의 연결 관계를 나타낸다. X행의 X 정점과 다른 정점과 연결 여부를 표시한다
• 인접 행렬로 그래프 그리기 https://graphonline.ru/en/create_graph_by_matrix

visited_ 값은 traversal을 확인할 때 사용한다.

 

깊이 우선 탐색(Depth First Search)

• 방문한 정점을 깊이 파고든다
• 스택을 활용한다

 

너비 우선 탐색(Breadth First Search)

• 중심이 되는 정점과 연결되어있는 정점을 모두 방문한 뒤 다음 레벨로 파고든다
• 큐를 활용한다

 

구현하기

InsertEdge

void InsertEdge(int u, int v) // 여기서 u, v는 인덱스
{
    assert(u < n_ && v < n_);

    matrix_[u][v] = 1;
}

 

DepthFirstTraversal

void DepthFirstTraversal(int v) // v는 인덱스
{
    if (visited_[v]) return;

    visited_[v] = true;

    cout << vertices_[v].item << " ";

    for (int c = 0; c < n_; ++c)
        if (matrix_[v][c])
            DepthFirstTraversal(c);
}

 

IterDFS

void IterDFT()
{
    ResetVisited();

    int v = 0;

    Stack<int> s;
    s.Push(v);
    visited_[v] = true;

    while (!s.IsEmpty())
    {
        v = s.Top();
        s.Pop();

        cout << vertices_[v].item << " ";

        for (int c = n_-1; 0<= c; --c)
        {
            if (matrix_[v][c] && !visited_[c])
            {
                visited_[c] = true;
                s.Push(c);
            }
        }

        cout << "Stack :";
        s.Print();
    }
}

 

BreadthFirstTraversal

void BreadthFirstTraversal()
{
    int v = 0; // 0번에서 시작

    Queue<int> q;

    ResetVisited();

    visited_[v] = true;
    q.Enqueue(v);
    while (!q.IsEmpty())
    {
        v = q.Front();
        q.Dequeue();

        cout << v << " ";

        for (int c = 0; c < n_; ++c)
            if (matrix_[v][c] && !visited_[c])
            {
                visited_[c] = true;
                q.Enqueue(c);
            }

        cout << "Queue: ";
        q.Print();
    }
}

 

인접리스트(Adjacent List)

---

InsertEdge

기존의 Node를 뒤로 밀어넣는다

void InsertEdge(int u, int v) // 여기서 u, v는 인덱스
{
    assert(u < n_ && v < n_);

    Node* temp = new Node{ v, list_[u] };
    list_[u] = temp;
}

 

구현하기

DepthFirstTraversal

void DepthFirstTraversal(int v) // v는 인덱스
{
    if (visited_[v]) return;
    visited_[v] = true;

    cout << vertices_[v].item << " ";

    Node* current = list_[v];
    while (current)
    {
        DepthFirstTraversal(current->vertex);
        current = current->next;
    }
}

 

IterDFT

void IterDFT()
{
    ResetVisited();

    int v = 0;

    Stack<int> s;
    visited_[v] = true;
    s.Push(v);

    while (!s.IsEmpty())
    {
        v = s.Top();
        s.Pop();
        cout << vertices_[v].item << " ";

        Node* linked = list_[v];
        while (linked)
        {
            if (!visited_[linked->vertex])
            {
                visited_[linked->vertex] = true;
                s.Push(linked->vertex);
            }
            linked = linked->next;
        }

        cout << "Stack:";
        s.Print();
        cout << endl;
    }
}

 

BreathFirstTraversal

void BreadthFirstTraversal()
{
    ResetVisited();

    int v = 0;

    Queue<int> q;
    visited_[v] = true;
    q.Enqueue(v);

    while (!q.IsEmpty())
    {
        v = q.Front();
        q.Dequeue();

        cout << vertices_[v].item << " ";

        Node* linked = list_[v];
        while (linked)
        {
            if (!visited_[linked->vertex])
            {
                visited_[linked->vertex] = true;
                q.Enqueue(linked->vertex);
            }
            linked = linked->next;
        }

        cout << "Queue: ";
        q.Print();
        cout << endl;
    }
}