[TIL] 123 [C#] Graph 인접행렬, 인접리스트

---

Graph 인접행렬 인접리스트

---

Graph

노드(Node, Vertex)와 간선(Edge)으로 이루어진 구조
노드(Node): 그래프의 기본 단위이며, 각 노드는 다른 노드와 연결될 수 있습니다.
간선(Edge): 두 노드를 연결하는 선입니다. 간선은 방향성이 있을 수도, 없을 수도 있습니다.

그래프 종류 방향 그래프: 간선에 방향이 있는 그래프로, A -> B와 같이 한 방향으로만 연결됩니다.
무방향 그래프: 간선에 방향이 없는 그래프로, A - B와 같이 양방향으로 연결된 형태입니다.
가중치 그래프: 각 간선에 가중치(비용, 거리 등)가 있는 그래프입니다.
비가중치 그래프: 모든 간선의 가중치가 없는 그래프입니다.
사이클 그래프: 하나 이상의 닫힌 루프(사이클)가 존재하는 그래프입니다.
비순환 그래프: 닫힌 루프가 없는 그래프입니다.
완전 그래프: 모든 노드가 서로 연결된 그래프입니다.

인접행렬

노드 간의 연결 관계를 2차원 배열로 표현
노드 간의 연결 여부와 가중치를 간단히 확인할 수 있다

예제 두 노드가 연결되어 있으면 해당 위치에 1(또는 가중치)을, 연결되지 않았으면 0을 저장합니다.

예제	노드1	노드2	노드3
노드1	0	1	1
노드2	1	0	0
노드3	1	0	0

1-2 1-3 이 연결되어있습니다.

static void Main()
{
    int sum = 0;
    int input = Convert.ToInt32( Console.ReadLine());

    bool[] visited = new bool[input+1];
    int[,] graph = new int[input+1,input+1];

    int con = Convert.ToInt32(Console.ReadLine());
    for (int i = 0; i < con; i++)
    {
        int[] a = Array.ConvertAll( Console.ReadLine().Split(' '),Convert.ToInt32);
        graph[a[0],a[1]] = 1;
        graph[a[1],a[0]] = 1;
    }

    dfs(1);

    void dfs(int a) 
    {
        visited[a] = true;
        sum++;
        for (int i = 1; i <= input; i++)
        {
            if (graph[a, i] == 1 && !visited[i])
            {
                dfs(i);
            }
        }
    }

    Console.WriteLine(sum-1);
    Console.ReadLine();
}

인접행렬의 장점
빠른 확인: 두 노드의 연결 여부를 0, 1로 확인할 수 있습니다.
구현이 간단: 단순히 이차원 배열을 사용하여 그래프를 표현하므로 구현하기가 비교적 간단합니다.

인접행렬의 단점
메모리 비효율성: 노드가 많고 연결이 적은 희소 그래프에서는 불필요한 0값이 많이 생기며, 메모리를 낭비할 수 있습니다.
탐색 성능: 노드가 많아지면 이차원 배열을 사용하는 만큼 공간 복잡도가 커질 수 있습니다.

적합한 상황 :작은 크기의 밀집 그래프에서 두 노드 간 연결 여부를 빠르게 확인해야 하는 경우에 유리합니다.

인접리스트

List 타입을 요소로 갖는 배열 배열의 각 요소에 새로운 리스트를 할당해야합니다.(초기값 null)

static void Main()
{
    int sum = 0;
    int input = Convert.ToInt32( Console.ReadLine());

    bool[] visited = new bool[input+1];
    List<int>[] list = new List<int>[input+1];
    for (int i = 0; i <= input; i++)
    {
        list[i] = new List<int>();
    }

    
    int con = Convert.ToInt32(Console.ReadLine());
    for (int i = 0; i < con; i++)
    {
        int[] a = Array.ConvertAll( Console.ReadLine().Split(' '),Convert.ToInt32);
        list[a[0]].Add(a[1]);
        list[a[1]].Add(a[0]);
    }

    dfs(1);

    void dfs(int a) 
    {
        visited[a] = true;
        sum++;
        foreach (int b in list[a]) 
        {
            if (!visited[b])
            {
                dfs(b);
            }
        }
    }

    Console.WriteLine(sum-1);
    Console.ReadLine();
}

• List[]를 선언하면 List 타입을 담을 수 있는 배열만 만들어질 뿐 개별 리스트 인스턴스는 자동으로 생성되지 않습니다.
• 각 요소에 새로운 List를 할당하지 않으면 null 상태로 남아있기 때문에 추가적인 할당이 필요합니다.

인접리스트의 장점
메모리 효율성: 연결된 노드만 저장하므로 메모리를 절약, 특히 희소 그래프에 유리합니다.
노드 탐색 효율성: 특정 노드에 연결된 노드들을 순회하기가 빠르며, 연결된 노드들만 저장되어 있어 순회가 간단합니다.
동적 그래프 표현 용이성: 노드 추가, 삭제가 유연하고 간선 추가/삭제가 효율적입니다.

인접행렬의 단점
직접 연결 여부 확인이 느림: 두 노드의 직접 연결 여부를 확인하려면, 리스트를 탐색해야 하므로 시간이 걸릴 수 있습니다.
간선 가중치 비효율: 가중치를 포함하려면 노드와 가중치 쌍으로 구성된 복잡한 자료구조가 필요해 구현이 더 복잡해질 수 있습니다.

적합한 상황 : 노드가 많고 간선이 적은 희소 그래프에 적합하며, 그래프가 크더라도 효율적으로 사용할 수 있습니다.

---

잡담, 일기?

Graph
코드 예제문제
인접행렬 - 적합한 상황 :노드 연결 여부 확인이 빈번히 필요한 경우
인접리스트 - 적합한 상황 : 희소 그래프 - 메모리와 탐색 효율이 뛰어납니다.

---