[C# 기초] #19.Graph - Graph의 정의, 종류, 구현 방법

---

1. Graph란?

정점(vertex(V))과 그 정점을 연결하는 간선(edge(E)을 하나로 모아 놓은 자료구조.

연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조입니다. 

• G = (V, E)

(ex) 지도, 지하철 노선도, 전기 회로의 소자들, 도로 등.

 

---

2. Graph의 종류

1. 무방향 그래프 (Undirected graph)

 : 두 정점을 연결하는 간선에 방향이 없는 그래프. 두 정점의 양 방향으로 이동 가능.

 

 

2. 방향 그래프 (Directed graph)

 : 두 정점을 연결하는 간선에 방향이 있는 그래프. 특정 방향으로만 이동 가능.

 

 

3. 가중 그래프 (Weighted graph)

 : 정점을 연결하는 간선에 가중치(Weight)가 있는 그래프. 네트워크(Network) 라고도 함. 

4. 완전 그래프 (Complete graph)

 : 그래프의 모든 정점이 1:1 간선으로 연결된 그래프. 

• 최대 간선 수 - 무방향 그래프의 경우 n(n-1) / 2, 방향그래프의 경우 n(n-1). (정점의 개수 = n) 

5. 다중 그래프 (Multi graph)

 : 두 정점이 2개 이상의 간선으로 연결.

 

6. 연결 그래프 (Connected graph) vs 비연결 그래프 (Unconnected graph)

 : 모든 정점 사이에 간선이 존재하는 그래프를 연결 그래프, 간선이 하나라도 존재하지 않는 그래프를 비연결 그래프라 함. 

연결 그래프

비연결 그래프

---

3. Graph 구현 방법(인접 행렬, 인접 리스트)

1)인접 행렬 (Adjacency matrix)

 : 2차 배열(행렬)을 이용.

  인접 행렬은 상대적으로 정점의 개수가 적고, 간선의 수가 많을 때 사용하는 것이 좋음.

  정점 i와 j를 잇는 간선이 존재한다면 [i][j] = 1, 간선이 존재하지 않는다면 [i][j] = 0.

• 장점 

- 두 정점 사이의 간선 정보를 확인하는 것이 빠르고, 새로운 간선을 추가하고 제거하는 것이 빠름.

 

• 단점 

- 간선의 개수와 관계없이 배열의 크키가 항상 n*n개(n은 정점의 개수)이므로 메모리를 많이 사용함. 

- 노드를 추가, 제거하는데 오래 걸림.

- 특정한 노드에 인접한 노드를 찾기 위해 모든 노드를 순회해야 함.

- 그래프의 모든 간선의 수를 찾기 위해 모든 노드를 순회해야 함. 

 

2) 인접 리스트 (Adjacency List)

: 1차원 배열(시작 정점을 기준으로 정점의 개수만큼 연결 리스트가 1차원 배열에 저장)

  배열의 크기는 정점의 개수와 같음. 

  인접 리스트는 정점의 개수가 많고 간선의 개수가 상대적으로 적을때 사용하는것이 좋다.

 

• 장점 

- 노드의 수가 아닌 간선의 수에 따라 메모리 사용량이 달라지기 때문에 메모리 효율이 좋음

- 특정 노드에 직접 접근할 수 있어 인접한 노드를 찾기 쉬움.

- 노드의 추가 삭제가 빠름. 

- 새로운 간선을 빠르게 추가할 수 있음. 

- 그래프의 모든 간선의 수를 찾는 것이 빠름.

 

• 단점 

- 두 노드의 간선 정보를 확인하는데 오래 걸림. 

 

• 코드 구현

struct myGraph
{
    public int numV; // 정점의 수
    public int numE; // 간선의 수
    public List<Vertex>[] vArray;
}
static myGraph graph = new myGraph();

public enum Vertex
{
    A,B,C,D,E,F = 5
    ,G,H,I,J
}

static public void GraphInit(int numV)
{
    graph = new myGraph();
    graph.numV = numV;
    graph.vArray = new List<Vertex>[numV];
    for (int i = 0; i < numV; i++)
    {
        graph.vArray[i] = new List<Vertex>();
    }
}

static public void AddEdge(Vertex fromV, Vertex toV)
{
    if (!graph.vArray[(int)fromV].Contains(toV))
    {
        graph.numE++;
        graph.vArray[(int)fromV].Add(toV);
        graph.vArray[(int)toV].Add(fromV);
    }
}

static public void ShowGraphEdgeInfo()
{
    for (int i = 0; i < graph.numV; i++)
    {
        Console.Write((Vertex)i+" : ");
        foreach (var VARIABLE in graph.vArray[i])
        {
            Console.Write(VARIABLE+", ");
        }
        Console.Write("\n");
    }
}