그래프 알고리즘 연습(노드를 배열로 만들기)

By on November 22, 2023

그래프 알고리즘 기초 - 노드 변환

그래프 알고리즘을 배우기 전에 필수로 연습해야할 그래프를 배열로 만드는 방법에 대해서 정리 해보겠습니다.

  • 그래프 알고리즘 종류
    • 유니온 파인드 알고리즘(Union-Find)
      • 문제 유형 : 그래프에 사이클이 생성되는지 판별 하는 알고리즘
    • 위상 정렬(topological sorting)
      • 문제 유형 : 사이클이 없고. 방향이 있는 그래프에서만 사용할 수 있으며 전후 관계가 필요한 알고리즘(수강 신청 등등)
    • 다익스트라 알고리즘(Dijkstra)
      • 문제 유형 : 최단 거리 알고리즘. 시작 노드(S) 에서 목적지(E)로 가는 최단거리 탐색에 이용됨. (음수 간선 불가)
    • 벨만포드 알고리즘(Bellman-Ford)
      • 문제 유형 : 다익스트라 알고리즘과 동일하게 최단거리를 구할 수 있는 알고리즘 이지만 음수 간선도 사용이 가능함.
    • 플로이드 워셜 알고리즘(Floyd-Warshall)
      • 문제 유형 : 벨만포드 알고리즘과 동일한 음수간선을 포함한 최단거리에 활용되는 알고리즘이지만 동적 계획법(DP-Memorise) 을 활용함.
    • 최소 신장 트리(MST : Minimum Spanning Tree)
      • 문제 유형 : 모든 노드를 연결 할때 최소의 비용을 구할 수 잇는 알고리즘. 유니온파인드를 활용해서 사이클을 없엠.

위 그래프 문제를 해결 하기 위해서는 그래프를 배열로 변경 하는 방법을 숙지 하고 있어야 합니다.

에지 리스트 중심으로 표현하는 방법

  • 그래프 제시 유형

    노드의 시작(S) 과 종료(E) 가 주어지며 가중치(V) 가 있는경우 2차원 배열로 변환

  • 입력 값 
    6
1 2 5
1 3 4
3 4 3
2 4 2
2 5 1
4 5 9
  • 변환 하기 
      @Test
  void 그래프변환(){
      int[][] graph = new int[6][2];  // 가중치가 있는 경우 new int[6][3]
      //  시작노드(S)       종료노드(E)           가중치(V)
      graph[0][0] = 1; graph[0][1] = 2;    graph[0][2] = 5;
      graph[1][0] = 1; graph[1][1] = 3;    graph[1][2] = 4;
      graph[2][0] = 3; graph[2][1] = 4;    graph[2][2] = 3;
      graph[3][0] = 2; graph[3][1] = 4;    graph[3][2] = 2;
      graph[4][0] = 2; graph[4][1] = 5;    graph[4][2] = 1;
      graph[5][0] = 4; graph[5][1] = 5;    graph[5][2] = 9;

      for(int[] g : graph){
          System.out.println(Arrays.toString(g));
      }
  }

인접 행렬로 그래프 표현 하는 방법

  • 그래프 제시 유형

    2차원 배열을 이용해서 표현하며 노드 중심으로 표현 하며 X 가 출발(S) 노드 Y 가 도착(E) 노드를 표현 한다.

인접 행렬 그래프 표현 방법

  • 입력 값 
    6
1 2
1 3
3 4
2 4
2 5
4 5

  • 변환 하기

    @Test
void 그래프변환(){
int[][] graph = new int[6][6];  // N x N 배열을 만든다.
  
        //   [S][E]  [간선 표기] - 가중치가 있는경우 가중치를 간선 표기에 값으로 넣는다.
        graph[1][2] = 1;
        graph[1][3] = 1;
        graph[3][4] = 1;
        graph[2][4] = 1;
        graph[2][5] = 1;
        graph[4][5] = 1;
  
        for(int[] g : graph){
            System.out.println(Arrays.toString(g));
        }
    }

인접 리스트(ArrayList)로 그래프 표현 방법

  • 그래프 제시 유형

    ArrayList 를 사용하여 그래프 관계를 표현하는 방법으로 가장 많이 활용하는 방법. 시작(S) 노드를 List의 Index 로 사용 하고 연결된 노드를 List.add(E) 하는 방법. 구현은 어렵지만 인덱스를 시작 노드로 이용하여 탐색이 매우 빠르다. 인접행렬과 다르게 빈공간이 없기 때문에 메모리에 이점이 있다.

인접 리스트형 그래프 표현 방법
  • 입력 값 
    6
1 2
1 3
3 4
2 4
2 5
4 5
  • 변환 하기(가중치가 없는 경우) 
    @Test
void 그래프변환(){

    List<Integer>[] graph = new ArrayList[6+1];  // 6개의 인덱스를 가진 리스트를 만든다.(인덱스는 0 부터 시작하기 때문에 N + 1)
    for(int i = 0; i <= 6; i++){
        graph[i] = new ArrayList<>(); // 초기화
    }

    graph[1].add(2); graph[1].add(3);
    graph[2].add(4); graph[2].add(5);
    graph[3].add(4);
    graph[4].add(5);

    for(List<Integer> g : graph){
        System.out.println(g);
    }
}
  • 변환 하기(가중치가 있는 경우) 
    @Test
void 그래프변환(){
    List<Node>[] graph = new ArrayList[6+1];  // 6개의 인덱스를 가진 리스트를 만든다.(인덱스는 0 부터 시작하기 때문에 N + 1)
    for(int i = 0; i <= 6; i++){
        graph[i] = new ArrayList<>(); // 초기화
    }

    //   [S]                  [E]      [V]
    graph[1].add(new Node(2, 5));
    graph[1].add(new Node(3, 4));
    graph[2].add(new Node(4, 2));
    graph[2].add(new Node(5, 1));
    graph[3].add(new Node(4, 3));
    graph[4].add(new Node(5, 9));

    for(List<Node> n : graph){
        System.out.println(n.toString());
    }
}
  
// Node 클래스를 이용하여 List 에 가중치와 함께 저장한다.
public class Node{
    private int end;
    private int value;

    public Node(int end, int value){
        this.end = end;
        this.value = value;
    }

    @Override
    public String toString(){
        return "end : " + end + " " + "value : " + value;
    }
}

Back to blog