1. 📖 그래프

정점(node)의 모음과 이 정점을 잇는 간선의 모음의 결합으로
한 노드에서 출발하여 다시 자기 자신의 노드로 돌아오는 순환구조를 가집니다.

모든 정점이 간선으로 연결될 필요는 없으며 데이터 간의 다양한 연결관계를 표현할 수 있습니다.

간선의 방향성에 따라 단방향 그래프, 양방향 그래프로 나타낼 수 있고
간선의 가중치에 따라 연결 그래프, 가중치 그래프로 나타낼 수 있습니다.

그래프는 다른 선형 자료구조와 달리 비선형 자료구조로 사용 목적과 상황에 따라 달라서
프로그래머가 직접 구현해야 하는 번거로움이 있는 자료구조입니다.

이건 비선형 자료구조를 가진 모든 자료구조가 해당하는 단점이니 그래프만의 문제는 아닙니다.

1-1 🔖 인접행렬 그래프

그래프 내의 각 정점의 인접 관계를 나타내는 행렬입니다.

2차원 배열을 [출발 정점, 도착 정점] 으로 표현하는 방식으로
인접 여부 접근이 상당히 빠르지만 메모리 사용량이 많은 단점이 있습니다.

연결만 필요한 경우 bool로 표현해서 나타내면 되지만
가중치까지 표현할 경우 int로 표현하여 나타내면 됩니다.

bool[,] graph = new bool[8, 8];

graph[0, 3] = true;  // 0과 3 연결
graph[3, 0] = true;

bool[,] graph = new int[8, 8];

graph[0, 1] = 5;  // int를 사용하여 가중치를 표현할 수 있음
graph[1, 3] = 6;

1-2 🔖 인접리스트 그래프

그래프 내의 각 정점의 인접 관계를 표현하는 리스트 인접한 간선만을 리스트에 추가하여 관리하는 방식으로 메모리 사용량이 적은 장점이 있지만 인접여부를 확인하기 위해 리스트 탐색이 따로 필요하여 느린 것이 단점입니다.

List<int>[] listGraph1;                 // 연결 그래프
List<(int, int)>[] listGraph2;          // 가중치 그래프

인접리스트 그래프를 사용방법을 살펴본다면

List<int>[] listGraph = new List<int>[8];
listGraph[0] = new List<int>() { 2, 4 }; // 0은 2와 4와 연결
listGraph[1] = new List<int>() { 2, 3 }; // 1은 2와 3과 연결

listGraph[0].Add(5); // 0에 5를 연결 추가

listGraph[1].Remove(3); // 1에 3 연결 삭제

bool connect = listGraph[0].Contains (5); // 연결여부 확인

1-3 🔖 객체지향으로 그래프 표현

그래프의 경우 인접행렬과 인접리스트로 아주 간단하게 그래프를 만들 수 있지만
클래스를 만들어 객체지향으로 표현할 수도 있습니다.

복잡하지만 객체지향으로 그래프를 체계적으로 표현할 수 있다는 장점이 있습니다.

public class GraphNode<T>
{
    private T vertex;

    public T Vertex { get { return vertex; } set { vertex = value; } }

    private List<GraphNode<T>> edges = new List<GraphNode<T>>();

    public GraphNode(T vertex)
    {
       this.vertex = vertex;
    }

    public void AddEdge(GraphNode<T> node)     // 간선 연결
    {
        edges.Add(node);
    }

    public void RemoveEdge(GraphNode<T> node)  // 간선 끊기
    {
        edges.Remove(node);
    }

    public bool IsConnect(GraphNode<T> node)
    {
        return edges.Contains(node);
    }

static void Main(string[] args)
{
    GraphNode<int> node0 = new GraphNode<int>(0);
    GraphNode<int> node1 = new GraphNode<int>(1);
    GraphNode<int> node2 = new GraphNode<int>(2);
    GraphNode<int> node3 = new GraphNode<int>(3);
    GraphNode<int> node4 = new GraphNode<int>(4);

    node0.AddEdge (node3);
    node0.AddEdge (node0);
    node0.AddEdge (node4);
    node0.AddEdge (node0);
}