📊인접 행렬 & 인접 리스트

🧠 그래프(Graph)란?

• 정점(Vertex)의 모음과 이 정점들을 잇는 간선(Edge)의 모음으로 구성된 자료구조
• 한 노드에서 출발해 자기 자신으로 돌아올 수 있는 순환 구조를 가질 수 있음

• 방향성에 따라

  • 단방향 그래프 (Directed Graph)
    

  • 양방향 그래프 (Undirected Graph)
    

알고리즘 시각화 사이트 :

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

---

📐 인접 행렬(Adjacency Matrix)

그래프 내의 각 정점의 인접 관계를 나타내는 2차원 배열 구조

• 배열 형태: bool[,] matrix = new bool[V, V]
• matrix[i, j] == true → 정점 i에서 정점 j로 연결된 간선이 존재

✅ 장점

• 인접 여부 확인이 O(1)로 빠름

❌ 단점

• 간선이 적은 희소 그래프에서는 메모리 낭비가 큼
• 정점 개수가 많을수록 메모리 부담 증가

🔧 예시 코드

public class AdjacencyMatrixGraph
{
    public bool[,] graph = new bool[8, 8];

    public void TwoWayGraph(int a, int b)
    {
        graph[a, b] = true;
        graph[b, a] = true;
    }

    public void OneWayGraph(int a, int b)
    {
        graph[a, b] = true;
    }

    public void PrintGraph()
    {
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                Console.Write($"{(graph[i, j] ? "1" : "")}\t");
            }
            Console.WriteLine();
        }
    }
}

📐 인접 리스트(Adjacency List)

그래프의 각 정점에 연결된 이웃 정점들을 리스트로 저장하는 방식

배열 형태:List<int>[] graph = new List<int>[V]

graph[i]에 연결된 노드들의 리스트를 저장

✅ 장점

• 메모리 효율이 뛰어남 (간선 수만큼만 저장)
• 연결된 노드 순회가 빠름

❌ 단점

• 특정 노드와의 연결 여부를 확인할 때 선형 탐색이 필요 (O(n))

🔧 예시 코드

public class AdjacencyList
{
    public List<int>[] graph;

    public AdjacencyList()
    {
        graph = new List<int>[8];
        for (int i = 0; i < 8; i++)
        {
            graph[i] = new List<int>();
        }
    }

    public void TwoWayGraph(int a, int b)
    {
        if (!graph[a].Contains(b)) graph[a].Add(b);
        if (!graph[b].Contains(a)) graph[b].Add(a);
    }

    public void PrintGraph()
    {
        for (int i = 0; i < graph.Length; i++)
        {
            Console.Write($"{i}노드 : ");
            foreach (var neighbor in graph[i])
            {
                Console.Write($"- {neighbor} ");
            }
            Console.WriteLine();
        }
    }
}