그래프 (Graph)의 개념 및 구현

그래프(Graph)의 개념 및 구현

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성된 자료 구조로, 데이터 요소 간의 관계를 표현하는 데 사용됩니다. 그래프는 다양한 문제에서 데이터 간 연결성을 모델링하는 데 매우 유용하며, 중요한 자료 구조 중 하나입니다.

---

1. 그래프의 개념

1.1 그래프의 정의

• 그래프는 정점(노드)들의 집합과 이들을 연결하는 간선들의 집합으로 표현됩니다.
• 정점: 데이터를 저장하는 기본 단위.
• 간선: 정점 간의 관계를 나타내는 연결.

1.2 그래프의 특징

• 방향성:
  • 방향 그래프(Directed Graph): 간선에 방향이 존재 (A → B).
  • 무방향 그래프(Undirected Graph): 간선에 방향이 없음 (A — B).
• 가중치:
  • 가중 그래프(Weighted Graph): 간선에 가중치가 할당된 그래프.
  • 비가중 그래프(Unweighted Graph): 간선에 가중치가 없는 그래프.

1.3 그래프의 표현 방법

1. 인접 행렬(Adjacency Matrix):
   • 정점을 2D 행렬로 표현.
   • 정점 iii와 jjj가 연결되어 있으면 행렬의 값이 1 (또는 가중치).
   • 메모리 사용량: O(V^2)
2. 인접 리스트(Adjacency List):
   • 각 정점에 연결된 정점들을 리스트로 표현.
   • 메모리 사용량: O(V+E), E는 간선의 수.

---

2. 그래프의 구현

2.1 그래프 구현 (C#)

다음은 인접 리스트를 이용한 그래프 구현입니다.

using System;
using System.Collections.Generic;

public class Graph
{
    private int vertices; // 정점의 개수
    private List<int>[] adjacencyList; // 인접 리스트

    public Graph(int v)
    {
        vertices = v;
        adjacencyList = new List<int>[v];
        for (int i = 0; i < v; i++)
        {
            adjacencyList[i] = new List<int>();
        }
    }

    // 간선 추가 (무방향 그래프)
    public void AddEdge(int v, int w)
    {
        adjacencyList[v].Add(w);
        adjacencyList[w].Add(v);
    }

    // 그래프 출력
    public void PrintGraph()
    {
        for (int i = 0; i < vertices; i++)
        {
            Console.Write($"정점 {i}: ");
            foreach (var node in adjacencyList[i])
            {
                Console.Write($"{node} ");
            }
            Console.WriteLine();
        }
    }

    // 깊이 우선 탐색 (DFS)
    public void DFS(int start)
    {
        bool[] visited = new bool[vertices];
        DFSUtil(start, visited);
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        Console.Write($"{v} ");

        foreach (var neighbor in adjacencyList[v])
        {
            if (!visited[neighbor])
            {
                DFSUtil(neighbor, visited);
            }
        }
    }

    // 너비 우선 탐색 (BFS)
    public void BFS(int start)
    {
        bool[] visited = new bool[vertices];
        Queue<int> queue = new Queue<int>();

        visited[start] = true;
        queue.Enqueue(start);

        while (queue.Count > 0)
        {
            int current = queue.Dequeue();
            Console.Write($"{current} ");

            foreach (var neighbor in adjacencyList[current])
            {
                if (!visited[neighbor])
                {
                    visited[neighbor] = true;
                    queue.Enqueue(neighbor);
                }
            }
        }
    }
}

// 사용 예제
public class Program
{
    public static void Main()
    {
        Graph graph = new Graph(5);

        graph.AddEdge(0, 1);
        graph.AddEdge(0, 4);
        graph.AddEdge(1, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(1, 4);
        graph.AddEdge(2, 3);
        graph.AddEdge(3, 4);

        Console.WriteLine("그래프 출력:");
        graph.PrintGraph();

        Console.WriteLine("\nDFS(0부터 시작):");
        graph.DFS(0);

        Console.WriteLine("\n\nBFS(0부터 시작):");
        graph.BFS(0);
    }
}

---

2.2 출력 결과

그래프 출력:
정점 0: 1 4 
정점 1: 0 2 3 4 
정점 2: 1 3 
정점 3: 1 2 4 
정점 4: 0 1 3 

DFS(0부터 시작):
0 1 2 3 4 

BFS(0부터 시작):
0 1 4 2 3

---

3. 그래프의 응용

그래프는 다음과 같은 다양한 문제에 활용됩니다.

1. 네트워크:
   • 인터넷, 소셜 네트워크, 통신 네트워크 모델링.
2. 경로 찾기:
   • 최단 경로 알고리즘 (예: 다익스트라, 벨만-포드).
3. 스케줄링:
   • 작업 스케줄링 및 의존성 해결 (위상 정렬).
4. AI와 게임 개발:
   • 상태 공간 탐색 및 경로 찾기.

---

4. 그래프 알고리즘

1. 최단 경로:
   • 다익스트라(Dijkstra), 플로이드-워셜(Floyd-Warshall).
2. 최소 신장 트리(MST):
   • 크루스칼(Kruskal), 프림(Prim).
3. 강 연결 요소(SCC):
   • 코사라주(Kosaraju), 타잔(Tarjan).

---

그래프는 연결성을 다룰 때 가장 강력한 도구 중 하나로, 다양한 문제를 해결하는 데 사용됩니다.
인접 리스트와 행렬을 이해하고, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 활용하는 것이 그래프의 기본을 다지는 첫걸음입니다.