자료구조 - 그래프(Graph)

 

 

 

그래프란 ? 

 

 

 

 

 

• 그래프는 '정점의 모음' 과 '간선의 모음' 이 결합한 것이다.
• 정점들이 간선을 통해 연결되면 '관계'가 형성되고 이로 인해 그래프가 만들어진다.
• 간선으로 연결된 두 정점은 서로 '인접' 관계에 있다고 표현한다.
• 어떤 경로가 하나의 정점을 두번 이상 거친다면 그 경로는 '사이클' 이라고 표현한다.
• 간선에 방향성이 있다면 방향성 그래프, 없다면 무방향성 그래프가 된다.

 

방향성 그래프

 

 

 

 

 

그래프의 표현 방법

 

 

 

• 정점의 집합은 배열, 리스트 등 여러 자료구조로 표현이 가능하다.

 

• 간선의 집합은 정점 사이의 인접 관계를 나타내는 방식이다.
  즉 정점과 정점의 인접 관계를 어떻게 나타내는가를 잘 고민해야 한다.
• 간선의 집합은 크게 두 가지로 표현 한다. (인접 행렬, 인접 리스트)

 

 

인접 행렬

 

 

• 인접 행렬은 정점끼리의 인접 관계를 나타내는 행렬이다.
• 그래프의 정점 수를 N이라고 할때 N * N 크기의 행렬을 만든다.
• 정점 사이의 간선이 존재 할 경우 1로 표기하고 없을 경우 0으로 표기한다.

 

 

 

• 위의 예제에서 정점 1은 정점 2,3,4,5와 모두 인접한다.
• 따라서 (1, 2), (1, 3), (1, 4), (1, 5) 는 모두 1에 속한다.
• 정점 2는 (2, 1), (2, 3), (2, 5) 로 표기한다.

 

해당 정점에 대해 인접 표시가 완료된 행렬은 다음과 같다.

 

 

인접 리스트

 

 

• 인접 리스트는 그래프의 각 정점의 인접 관계를 표현하는 리스트다.
• 각각의 정점이 자신과 인접한 모든 정점의 목록을 리스트로 관리한다.
• 인접 리스트를 만드는 방식은 모든 정점을 나열하고 각 정점의 인접 정점을 옆에 나열하는 방식이다.

 

 

 

다음은 위 예시 그래프를 인접 리스트로 구현하는 방법이다.

 

정점	인접 정점
1	2,3,4,5
2	1,3,5
3	1,2
4	1,5
5	1,2,4

 

 

인접 정점을 정리한 후 이를 링크드 리스트로 각 정점에 연결한다.

 

 

 

 

 

인접 행렬과 인접 리스트의 선택 기준

 

 

• 인접 행렬을 이용하면 정점 간 인접 여부는 빠르게 파악이 가능하지만 행렬 형태로 저장해야 하는
  메모리의 양이 N * N, 즉 공간 복잡도가 O(N²) 만큼 발생한다.

 

• 인접 리스트를 이용하면 정점 간의 인접 여부를 알아내기 위해 인접 리스트를 타고 순차 탐색을 꼭 해야한다.
  하지만 정점과 간선 삽입이 인접 행렬보다 빠르고 인접 관계를 표시하는 리스트에 사용되는 메모리의 양이 적다.

 

 

따라서 메모리의 효율성이 우선시 되는지, 정점의 수가 많고 정점과 간선의 입력이 빈번하게 이루어 지는지 고려한 후
프로그램의 목적에 따라 결정하는 것이 바람직하다.

 

 

노드의 수가 많지 않고 간선의 밀도가 높은 경우에는 인접 행렬이 유리하고

 

 

노드의 수가 많고 간선의 밀도가 낮거나 메모리 효율성이 우선시 되는 경우에는 인접 리스트를 사용하는 것이 유리하다.

 

 

 

 

 

코드 예제

 

 

 public class Node
 {
     // 노드의 값 저장
     public int Value { get; set; }

     // 인접 노드들을 저장하는 링크드 리스트
     public LinkedList<Node> linkedListNodes { get; set; }

     // 생성자: 노드의 값을 초기화하고 인접 리스트를 초기화
     public Node(int value)
     {
         Value = value;
         linkedListNodes = new LinkedList<Node>();
     }

     // 인접 노드를 추가하는 메소드
     public void AddLinkedListNodes(Node node)
     {
         linkedListNodes.AddLast(node);
     }
 }

 

 

우선 노드의 값을 저장할 Value와 LinkedList를 생성 한다.

 

인접 노드가 발생할 경우 AddLinkedListNodes를 호출 한다.

 

 

 

public class Graph
{
    // 그래프의 노드들을 저장하는 딕셔너리
    private Dictionary<int, Node> nodes;

    // 생성자: 노드 딕셔너리를 초기화
    public Graph()
    {
        nodes = new Dictionary<int, Node>();
    }

    // 새로운 노드를 추가하는 메소드
    public void AddNode(int value)
    {
        if (!nodes.ContainsKey(value))
        {
            nodes[value] = new Node(value);
        }
    }

    // 간선을 추가하는 메소드
    public void AddEdge(int from, int to)
    {
        // 시작 노드가 없으면 추가
        if (!nodes.ContainsKey(from))
        {
            AddNode(from);
        }
        // 끝 노드가 없으면 추가
        if (!nodes.ContainsKey(to))
        {
            AddNode(to);
        }

        // 시작 노드와 끝 노드를 연결
        Node fromNode = nodes[from];
        Node toNode = nodes[to];
        fromNode.AddLinkedListNodes(toNode);
    }
}

 

 

그래프 클래스를 만들어주고 각 그래프의 노드들을 저장할 딕셔너리를 선언한다.

 

이후 새로운 노드를 추가하는 경우에는 AddNode 메소드를 불러오고

 

간선을 추가하는 경우에는 LinkedList를 연결하는 메소드인 AddEdge 메소드를 호출한다.

 

 

 // 그래프를 출력하는 메소드
 public void ShowGraph()
 {
     // Dictionary의 Values를 확인
     foreach (var node in nodes.Values)
     {
         Console.Write(node.Value + " -> ");

         // LinkedList를 foreach로 확인 후 출력
         foreach (var adjacentNode in node.linkedListNodes)
         {
             Console.Write(adjacentNode.Value + " ");
         }
         Console.WriteLine();
     }
 }

 

 

 public static void Main()
 {
     // 그래프 객체 생성
     Graph graph = new Graph();

     // 노드 추가
     graph.AddNode(1);
     graph.AddNode(2);
     graph.AddNode(3);
     graph.AddNode(4);
     graph.AddNode(5);

     // 간선 추가
     graph.AddEdge(1, 2);
     graph.AddEdge(1, 3);
     graph.AddEdge(1, 4);
     graph.AddEdge(1, 5);

     graph.AddEdge(2, 1);
     graph.AddEdge(2, 3);
     graph.AddEdge(2, 5);

     graph.AddEdge(3, 1);
     graph.AddEdge(3, 2);

     graph.AddEdge(4, 1);
     graph.AddEdge(4, 5);

     graph.AddEdge(5, 1);
     graph.AddEdge(5, 2);
     graph.AddEdge(5, 4);

     // 그래프 출력
     graph.ShowGraph();
 }

 

위의 예제 그래프를 출력해보도록 하자.

 

 

 

노드를 추가하고 간선을 추가한 대로 잘 표기된다.