📚 Graph 이론

📚 Graph 이론

• 노드(정점)와 간선(엣지)로 구성된 구조를 다룬다.

📚 그래프의 기본 개념

• 정점(Vertex) : 그래프에서 데이터를 나타내는 요소. 예를 들어 수업, 도시, 컴퓨터가 된다.
• 간선(Edge) : 정점들 사이의 관계를 나타내는 연결선. 예를 들어 도시 A와 도시 B가 도로로 연결되어 있음을 표현
• 그래프는 방향 그래프 와 무방향 그래프로 나눌 수 있다.
  1. 방향 그래프 : 간선에 방향이 있어서 한쪽 방향으로만 이동 가능
  2. 무방향 그래프 : 간선에 방향이 없어서, 두 정점 사이를 양방향으로 이동 가능

🚀 그래프 표현 방법

1. 인접 행렬
   • 배열을 사용하여 그래프 표현
   • 그래프 크기가 커지면 메모리 낭비가 발생할 수 있음.
2. 인접 리스트
   • 벡터나 연결 리스트를 사용하여 그래프 표현
   • 메모리 효율이 좋아 간선이 적은 그래프에서 사용한다.

📊 그래프 종류

1. 단방향 그래프 : 각 간선에 방향이 있는 그래프
2. 무방향 그래프 : 각 간선에 방향이 없는 그래프
3. 가중치 그래프 : 간선에 가중치가 부여된 그래프
4. 비가중치 그래프 “ : 간선에 가중치가 없는 그래프
5. 사이클이 없는 그래프 : 간선에 의해 순환이 없는 그래프
6. 연결 그래프 : 모든 정점이 서로 연결되어 있는 그래프
7. 비연결 그래프 : 일부 정점들이 연결되어 있지 않은 그래프

💻 그래프 탐색 알고리즘

기본적인 알고리즘은 너비 우선 탐색(BFS) 과 깊이 우선 탐색(DFS) 이다.

1. 너비 우선 탐색(BFS)
   • 탐색 방법 : 한 정점에서 시작하여, 그 정점에 인접한 모든 정점들을 차례대로 탐색
   • 특징 : 큐를 사용하여 탐색 진행, 각 레벨을 차례대로 탐색
   • 주용도 : 최단 경로 찾기, 연결요소 찾기, 그래프 너비 계산 등등…

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void bfs(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    queue<int> q;
    visited[start] = true;
    q.push(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " "; // 현재 노드를 출력
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int n = 5; // 노드 개수
    vector<vector<int>> graph(n); // 그래프 (인접 리스트)
    
    // 그래프 연결
    graph[0].push_back(1);
    graph[0].push_back(4);
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(4);

    vector<bool> visited(n, false); // 방문 여부 추적

    bfs(0, graph, visited); // 노드 0부터 BFS 시작

    return 0;
}

1. 깊이 우선 탐색(DFS)
   • 탐색 방법 : 한 정점에서 시작하여 , 그 정점에 인접한 정점들을 가능한 깊이까지 탐색 한 다음 더이상 탐색할 곳이 없으면 다시 돌아와서 다른 경로를 탐색한다.
   • 특징 : 스택을 사용하거나 재귀를 이용하여 탐색을 진행
   • 주용도 : 그래프 사이클 검사, 경로 찾기 등등…

#include <iostream>
#include <vector>

using namespace std;

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " "; // 현재 노드를 출력
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

int main() {
    int n = 5; // 노드 개수
    vector<vector<int>> graph(n); // 그래프 (인접 리스트)
    
    // 그래프 연결
    graph[0].push_back(1);
    graph[0].push_back(4);
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(4);

    vector<bool> visited(n, false); // 방문 여부 추적

    dfs(0, graph, visited); // 노드 0부터 DFS 시작

    return 0;
}

🛠 그래프 관련 알고리즘

• 최단 경로 알고리즘
  • 다익스트라 알고리즘 : 가중치가 있는 그래프에서 한 노드에서 다른 모든 노드로의 최단 경로를 구하는 알고리즘
  • 벨만-포드 알고리즘 : 다익스트라보다 일반화된 형태로, 음의 가중치가 있을 때 사용
  • 플로이드-위셜 알고리즘 : 모든 쌍의 노드에 대해 최단 경로를 구하는 알고리즘
• 위상 정렬(Topological Sort)
  • 목적 : 사이클이 없는 방향 그래프에서 노드를 선택적인 순서로 배치하는 알고리즘. 예를 들어, 작업 스케쥴링 문제에 사용됨
  • 알고리즘 : DFS 또는 큐를 이용한 알고리즘으로 구현됨

해당 알고리즘의 예시를 여기에 전부 소개하는 것보다 Graph 관련 알고리즘 문제를 풀다보면 해당 알고리즘을 접하게 된다.

📌 그래프의 사이클 검사

• 방향 그래프의 사이클 : DFS를 이용해 탐색하면서 역추적(Back Tracking) 을 통해 사이클을 검사
• 무방향 그래프의 사이클 : DFS를 이용해 부모 노드를 추적하며 사이클을 검사

💡 그래프 문제 해결에 C++ 자료구조 사용

1. 큐(queue) : BFS 구현시 사용된다. 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO 구조
2. 스택(stack) : DFS 반복 구현시 사용된다. 스택은 나중에 들어온 데이터가 먼저 나가는 LIFO 구조
3. 맵(map) : 간선 정보를 효율적으로 저장하거나(중복 확인 등), 방문 여부 추적에 응용
4. 셋(set) : 그래프에서 중복된 간선이나 노드를 처리할 때 유용

• stl
• c
• graph