그래프 생성

전체 코드

1. 그래프란?

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다.
정점(Vertex): 데이터를 표현하는 노드
간선(Edge): 정점들을 연결하는 선
그래프는 방향성이 있는 경우와 없는 경우로 나뉘며, 간선에 가중치(Weight) 가 포함될 수도 있습니다.

2. 그래프의 유형

그래프는 여러 유형으로 분류될 수 있습니다.

1. 방향 그래프(Directed Graph)

   • 간선이 한쪽 방향으로만 연결됨
   • 예: 도시 간의 일방통행 도로

2. 무방향 그래프(Undirected Graph)

   • 간선이 양방향으로 연결됨
   • 예: 친구 관계(페이스북 친구, 네트워크 연결)

3. 가중치 그래프(Weighted Graph)

   • 간선에 가중치(비용)가 포함됨
   • 예: 도로망(거리, 시간, 비용 포함)

---

3. 그래프 표현 방법

그래프를 코드로 표현하는 방법에는 다음 세 가지가 있습니다.

1. 정점을 객체로 생성하여 표현
2. 인접 리스트(Adjacency List) 사용
3. 인접 행렬(Adjacency Matrix) 사용

각 방법마다 장점과 단점이 존재합니다.

표현 방법	메모리 효율성	탐색 속도	사용 예
정점 객체	정점 추가가 쉬움	탐색 시 성능 저하	객체 지향적인 접근
인접 리스트	메모리 절약	탐색 성능 다소 떨어짐	정점이 많고 간선이 적은 경우
인접 행렬	빠른 탐색	메모리 사용 증가	간선이 많은 경우

---

4. 그래프 코드 구현 (C#)

4.1 정점을 객체로 생성하여 그래프 표현

각 정점을 클래스로 생성하여 간선 정보를 관리하는 방식입니다.

using System;
using System.Collections.Generic;

class Vertex
{
    public List<Vertex> edges = new List<Vertex>();  // 연결된 정점 목록
}

class Program
{
    static void CreateGraph()
    {
        List<Vertex> v = new List<Vertex>(6)
        {
            new Vertex(),
            new Vertex(),
            new Vertex(),
            new Vertex(),
            new Vertex(),
            new Vertex(),
        };

        v[0].edges.Add(v[1]); // v[0] → v[1], v[3] 연결
        v[0].edges.Add(v[3]);

        v[1].edges.Add(v[0]); // v[1] → v[0], v[2], v[3] 연결
        v[1].edges.Add(v[2]);
        v[1].edges.Add(v[3]);

        v[3].edges.Add(v[4]); // v[3] → v[4] 연결
        v[5].edges.Add(v[4]); // v[5] → v[4] 연결
    }

    static void Main(string[] args)
    {
        CreateGraph();
    }
}

✅ 장점

• 객체 지향적인 표현이 가능
• 정점별로 데이터 관리가 용이

❌ 단점

• 정점이 많을 경우 메모리 낭비 발생
• 정점 추가 시 객체를 직접 생성해야 함

---

4.2 인접 리스트를 사용한 그래프 표현

정점을 객체로 만들지 않고 리스트 배열을 사용하여 관리하는 방법입니다.

using System;
using System.Collections.Generic;

class Program
{
    static void CreateGraph()
    {
        List<int>[] adjacent = new List<int>[6]
        {
            new List<int> {1, 3},      // v[0] → v[1], v[3]
            new List<int> {0, 2, 3},   // v[1] → v[0], v[2], v[3]
            new List<int> { },         // v[2] → 없음
            new List<int> {4},         // v[3] → v[4]
            new List<int> { },         // v[4] → 없음
            new List<int> {4},         // v[5] → v[4]
        };
    }

    static void Main(string[] args)
    {
        CreateGraph();
    }
}

✅ 장점

• 메모리 절약 (객체 생성 필요 없음)
• 정점 수가 많고 간선이 적을 경우 효율적

❌ 단점

• 탐색 시 리스트를 순회해야 하므로 접근 속도가 떨어짐
• 특정 정점이 존재하는지 확인하는 연산이 O(n)

---

4.3 인접 행렬(2차원 배열)

정점 간 연결을 2차원 배열로 관리하는 방식입니다.

using System;

class Program
{
    static void CreateGraph()
    {
        int[,] adjacent = new int[6, 6]
        {
            { 0, 1, 0, 1, 0, 0 }, // v[0] → v[1], v[3]
            { 1, 0, 1, 1, 0, 0 }, // v[1] → v[0], v[2], v[3]
            { 0, 1, 0, 0, 0, 0 }, // v[2] → v[1]
            { 1, 1, 0, 0, 1, 0 }, // v[3] → v[0], v[1], v[4]
            { 0, 0, 0, 1, 0, 1 }, // v[4] → v[3], v[5]
            { 0, 0, 0, 0, 1, 0 }, // v[5] → v[4]
        };
    }

    static void Main(string[] args)
    {
        CreateGraph();
    }
}

✅ 장점

• 탐색 속도 O(1)
• 정점 간 연결 여부를 빠르게 확인 가능

❌ 단점

• 메모리 낭비 (연결되지 않은 정점도 저장해야 함)
• 정점 수가 많으면 비효율적

---

5. 가중치 그래프 표현

그래프의 간선에 가중치(weight) 를 부여할 수도 있습니다.

using System;
using System.Collections.Generic;

class Edge
{
    public int Vertex;
    public int Weight;

    public Edge(int v, int w)
    {
        Vertex = v;
        Weight = w;
    }
}

class Program
{
    static void CreateGraph()
    {
        List<Edge>[] adjacent = new List<Edge>[6]
        {
            new List<Edge> { new Edge(1, 15), new Edge(3, 35) },  
            new List<Edge> { new Edge(0, 15), new Edge(2, 5), new Edge(3, 10) },
            new List<Edge> { },
            new List<Edge> { new Edge(4, 5) },  
            new List<Edge> { },
            new List<Edge> { new Edge(4, 5) },  
        };
    }

    static void Main(string[] args)
    {
        CreateGraph();
    }
}

---

6. 그래프 표현 방식 비교

표현 방식	메모리 효율성	접근 속도	사용 예
정점 객체	O(n)	O(n)	객체 지향적인 접근
인접 리스트	O(n + m)	O(n)	간선이 적고 정점이 많은 경우
인접 행렬	O(n²)	O(1)	간선이 많은 경우

---