인접 리스트, 인접 행렬 표현법

인접 리스트와 인접 행렬 표현법

그래프를 저장하고 표현하는 방법은 다양한데, 그중 가장 널리 사용되는 방식은 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)입니다. 이 두 가지 표현법은 그래프의 특성과 사용 목적에 따라 적합하게 선택됩니다. 이번 포스팅에서는 두 표현법의 개념, 구현 방법, 장단점, 그리고 선택 기준에 대해 다뤄보겠습니다.

---

1. 인접 리스트 (Adjacency List)

1.1 개념

인접 리스트는 각 정점(Vertex)에 대해 연결된 다른 정점들을 리스트(List)로 저장하는 방식입니다.

• 구조:
  • 각 정점은 리스트에 해당하며, 리스트 안에 연결된 정점들이 포함됩니다.
• 공간 복잡도: O(V+E)
  • V: 정점의 개수
  • E: 간선의 개수

1.2 구현 (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();
        }
    }
}

// 사용 예제
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);

        graph.PrintGraph();
    }
}

1.3 출력 결과

정점 0: 1 4 
정점 1: 0 2 3 4 
정점 2: 1 3 
정점 3: 1 2 4 
정점 4: 0 1 3

1.4 장단점

장점:

1. 공간 효율적: 희소 그래프(Sparse Graph)에 적합.
2. 연결된 정점만 저장하므로 불필요한 공간 낭비가 적음.
3. 연결된 정점에 대한 순회가 빠름.

단점:

1. 특정 두 정점 간의 연결 여부를 확인하는 데 O(V)O(V)O(V) 시간이 걸림.
2. 정점 수가 많고 조밀한 그래프(Dense Graph)에 비효율적.

---

2. 인접 행렬 (Adjacency Matrix)

2.1 개념

인접 행렬은 V×VV \times VV×V 크기의 2차원 배열로 그래프를 표현합니다.

• 구조:
  • 배열의 각 행과 열은 정점을 나타냅니다.
  • 값이 1이면 간선이 존재, 0이면 간선이 없음.
  • 가중치 그래프에서는 값에 간선의 가중치를 저장.
• 공간 복잡도: O(V2)

2.2 구현 (C#)

using System;

public class Graph
{
    private int[,] adjacencyMatrix;
    private int vertices;

    public Graph(int v)
    {
        vertices = v;
        adjacencyMatrix = new int[v, v];
    }

    // 간선 추가 (무방향 그래프)
    public void AddEdge(int v, int w)
    {
        adjacencyMatrix[v, w] = 1;
        adjacencyMatrix[w, v] = 1; // 방향 그래프라면 이 줄 제거
    }

    // 그래프 출력
    public void PrintGraph()
    {
        for (int i = 0; i < vertices; i++)
        {
            for (int j = 0; j < vertices; j++)
            {
                Console.Write($"{adjacencyMatrix[i, j]} ");
            }
            Console.WriteLine();
        }
    }
}

// 사용 예제
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);

        graph.PrintGraph();
    }
}

2.3 출력 결과

0 1 0 0 1 
1 0 1 1 1 
0 1 0 1 0 
0 1 1 0 1 
1 1 0 1 0

2.4 장단점

장점:

1. 특정 두 정점 간의 연결 여부를 O(1)O(1)O(1)에 확인 가능.
2. 구현이 간단하고, 조밀한 그래프(Dense Graph)에 적합.

단점:

1. 공간 비효율적: 희소 그래프(Sparse Graph)에서는 불필요한 공간 낭비.
2. 연결된 정점 순회가 O(V)로 느림.

---

3. 인접 리스트 vs. 인접 행렬

특징인접 리스트인접 행렬

특징	인접 리스트	인접 행렬
공간 복잡도	O(V+E)	O(V2)
간선 추가	O(1)	O(1)
간선 존재 여부	O(V)	O(1)
연결된 정점 탐색	빠름	느림
적합한 그래프	희소 그래프(Sparse)	조밀 그래프(Dense)

---

4. 선택 기준

1. 희소 그래프:
   • 간선이 적은 그래프라면 인접 리스트가 더 적합합니다.
   • 공간 효율성을 극대화하고, 연결된 정점 탐색 속도를 높일 수 있습니다.
2. 조밀 그래프:
   • 간선이 많거나 모든 정점 간 연결 여부를 자주 확인해야 한다면 인접 행렬이 더 효율적입니다.
   • 정점 간의 연결 여부를 빠르게 확인할 수 있습니다.

---

그래프를 효율적으로 표현하기 위해서는 문제의 특성과 그래프의 구조를 잘 이해하고 적합한 표현법을 선택하는 것이 중요합니다. 인접 리스트는 공간 효율성과 탐색 속도가 중요한 경우에, 인접 행렬은 빠른 연결 여부 확인과 단순한 구현이 필요할 때 유용합니다.