C# Graph 구현

Description

이번에 구현해볼 것은 Graph 이다, Graph의 종류는 많이 있다.
그 중 방향이 존재하는 방향 Graph, 가중치로 최단 거리를 알 수있는 가중 그래프를 이용해 만들고자 한다.
DFS와 BFS가 이러한 Graph구조에서 비롯된 탐색 방법이다.

방향 그래프 (Directed Graph)

가중 그래프 (Weighted Graph)

---

Cord

Class

public class GraphNode<T>
{
    private List<GraphNode<T>> neighbor;    // 이웃 Node
    private List<int> weights;  // 가중치

    public T Data { get; set; } // Node의 값

    // 생성자를 통해 Data 초기화
    public GraphNode(T _data)
    {
        Data = _data;
    }

    // 이웃들을 List에 담아 관리
    public List<GraphNode<T>> Neighbor
    {
        get 
        {
            if (neighbor == null)
            {
                neighbor = new List<GraphNode<T>>();
            }
            return neighbor; 
        }
    }

    // 각각의 이웃에 대한 가중치를 담은 List
    public List<int> Weights
    {
        get 
        {
            if (weights == null)
            {
                weights = new List<int>();
            }
            return weights; 
        }
    }
}

public class Graph <T>
{
    // 현재 그래프가 가지고 있는 모든 Node
    private List<GraphNode<T>> nodeList;

    public Graph()
    {
        nodeList = new List<GraphNode<T>>();
    }

    // 방문한 Node의 공간
    private Stack<GraphNode<T>> truePath = new Stack<GraphNode<T>>();   // 방문한 Node 저장
    private string result = " ";    // 목적지까지의 방문한 Node 출력

    // 최단 Node 탐색 List
    private List<Tuple<string, int>> minPath = new List<Tuple<string, int>>();    // (result, weight)를 저장
    int sumWeight = 0;  // 가충치의 합
}

Graph에 대한 Node class를 따로 만들었다.
현재 Node가 가진 이웃 Node와 weight를 List로 관리한다
이제 이 Node를 이어줄 AddLine()을 만들어 보자.

---

AddLine()

// 가중치를 제외한 Line
public void AddLine(GraphNode<T> _start, GraphNode<T> _end)
{
    _start.Neighbor.Add(_end);
}

// 가중치를 포함한 Line
public void AddLine(GraphNode<T> _start, GraphNode<T> _end, int _weight)
{
    _start.Neighbor.Add(_end);
    _start.Weights.Add(_weight);
}

다음에는 Node 탐색을 할 것 인데 모든 Node를 출력하는 것과 가장 짧은 Node를 출력하는 매소드
이 두가지를 따로 만들고자 이렇게 두개를 만들었다.
잘 이어져있는지 확인 하고 바로 다음으로 넘어가보자.

현재 이어진 라인 상태이다.
1 <-> 2 <- 3 <- 4
1 <- 4
이와 같이 이어졌는지 확인해보자

1 -> 2 로 가고 2 -> 1로 가는 것을 각각 볼 수 있다.

3 -> 2 로 가는 것이 확인이 된다.

4 -> 3, 4 -> 1 로 가는 두 가지가 확인 되었다.

---

FindNode()

public void FindNode(GraphNode<T> _start, GraphNode<T> _end)
{
    truePath.Push(_start); // 현재 방문한 Node를 Stack에 저장

    // 도착지를 찾았을 경우 출력
    if (_start == _end)
    {
        // Stack에 쌓인 index를 끝에서부터 꺼내 출력한다.
        GraphNode<T>[] arr = truePath.ToArray();
        for (int pathIdx = arr.Length - 1; pathIdx >= 0; pathIdx--)
        {
            if (pathIdx == 0)
            {
                result += arr[pathIdx].Data;
            }
            else
            {
                result += arr[pathIdx].Data + " -> ";
            }
        }
        Debug.Log(result);
        result = " ";   // 출력한 뒤 초기화
        return;
    }

    // 다음 Node로 방문
    for (int idx = 0; idx < _start.Neighbor.Count; idx++)
    { 
        // 이미 방문했다면 다음으로 넘어가기
        if (truePath.Contains(_start.Neighbor[idx])) { continue; }
    
        FindNode(_start.Neighbor[idx], _end);
        truePath.Pop();     
    }
}

우선 FindNode로 node4에서 node1로 가는 모든 경로를 출력하는 것을 볼 수 있다.
즉, 모든 Node를 탐색하는 DFS 알고리즘을 사용하였다.
다음은 최단 경로에 대해 알아보자

---

FindMinNode()

public void Search(GraphNode<T> _start, GraphNode<T> _end)
{
    truePath.Push(_start); // 현재 방문한 Node를 Stack에 저장
    
    // 도착지를 찾았을 경우 출력
    if (_start == _end)
    {
        // Stack에 쌓인 index를 끝에서부터 꺼내 출력한다.
        GraphNode<T>[] arr = truePath.ToArray();
        for (int pathIdx = arr.Length - 1; pathIdx >= 0; pathIdx--)
        {
            if (pathIdx == 0)
            {
                result += arr[pathIdx].Data;
            }
            else
            {
                result += arr[pathIdx].Data + " -> ";
            }
        }
        minPath.Add(new Tuple<string, int>(result, sumWeight)); // 출력값과 가중치 저장
        result = " ";   // 출력한 뒤 초기화
        sumWeight = 0;  // 가중치 초기화
        return;
    }

    // 다음 Node로 방문
    for (int idx = 0; idx < _start.Neighbor.Count; idx++)
    {
        if (truePath.Contains(_start.Neighbor[idx])) { continue; }

        sumWeight += _start.Weights[idx];
        Search(_start.Neighbor[idx], _end);
        truePath.Pop();
    }
}

public void FindMinNode(GraphNode<T> _start, GraphNode<T> _end)
{
    Search(_start, _end);

    int min = int.MaxValue;        
    // 최단 Node 출력
    for (int idx = 0; idx < minPath.Count; idx++)
    {     
        if (min > minPath[idx].Item2)
        {
            min = minPath[idx].Item2;
            result = minPath[idx].Item1;
        }
    }
    Debug.Log("최단 루트 : " + result);
    Debug.Log("최소 비용 : " + min);
}

FindNode()와 마찬가지로 DFS방식을 사용하여 모든 노드를 방문하고
목적지까지의 경로와 가중치의 합 Tuple로 묶어 List에 저장하였다

List에는 “4 -> 3 -> 2 -> 1”, 4 와 “4 -> 1”, 5 가 저장되고
가중치가 5보다 작은 4로 0번 index가 선택되어 출력이 된 것을 볼 수 있다.

이로써 Graph도 완성 ~!