그래프

그래프란

정점과 간선으로 이루어진 자료구조

방향 그래프

간선에 방향이 있는 그래프로
A -> B로 향하는 간선과 B -> A로 향하는 간선이 서로 다를 수 있다.
진입차수(in-degree)와 진출차수(out-degree)로 나눠서 생각한다.

무방향 그래프

간선에 방향이 없는 그래프로
A - B를 연결하는 간선은 동일하다.

정점의 차수 (Degree)

• 정점에 연결된 간선의 수

• 무방향 그래프

  • 정점의 차수와 간선의 수가 같다.

• 방향 그래프

  • 진입차수(in-degree) 진출차수(out-degree)로 나눠진다.

• 경로

  • 정점을 연결된 간선을 따라 탐색하는 순서대로 나타내는 것
  • 최단 거리 (간선의 가중치의 합) vs 최단 경로 (탐색하는 순서대로 정점 나열)

• 사이클 (경로 종류 중 하나)

  • 간선의 경로 중 시작 정점과 끝 정점이 동일한 경로
  • 사이클이 없는 그래프
    • 예: 트리
    • (간선의 개수) = (노드의 개수) - 1 => 트리라면 바로 알 수 있다.

• 가중치 그래프

  • 간선에 가중치 혹은 비용이 할당된 그래프
  • 연결된 정점들 간 탐색에 드는 비용이나 연결 강도 등을 표현한다.
  • 구현 시 객체로 묶어서 표현하면 가독성이 좋은 코드를 작성할 수 있다.
  • [번호(정점) | 가중치]
    - ```
    class Node {
    int node;
    int cost;

    public Node(int node, int dist) {
    	this.node = node;
        this.dist = dist;
    }

    }

그래프 표현 방법

• 인접 행렬

  • 일반적으로 2차원 배열을 이용해서 표현한다.
  • adj[행][열] = 연결여부 (또는 가중치)
  • 공간 복잡도
    • V 개의 정점이 있으면 V*V 만큼의 공간을 사용한다.
  • 시간 복잡도
    • 연결관계(가중치) 조회/ 저장: O(1)
      • 정점에 연결된 모든 간선 조회: O(V)
  • 구현

    int[][] adj = new int[V+1][V+1]; 
    (무방향 그래프라면 역방향으로 만드는 행렬도 필요하다.)

• 인접 리스트

  	 - 간선 기반의 그래프의 일종으로 간선의 정보를 기반으로 저장한다.

  • 알고리즘 문제 풀이에서는 List<Node>[] graph형태로 선언한다.
    • 정점의 정보 : 베열
      • 간선의 정보 : 연결리스트 :: {간선의 가중치 + 정점번호}
  • graph[행] = new ArrayList()
    - 정점별로 간선의 정보{가중치 + 정점번호} 를 저장하는 리스트를 만든다.
  • 공간 복잡도
    - V개의 정점, E개의 간선 : V+E 만큼의 공간
    - ex) 모든 정점이 다른 정점과 모두 연결되어 있는 완전그래프
    - -> E 는 V(V-1)/2 에 수렴하므로 V^2 에 수렴한다.
    - 간선이 모든 정점과 연결되어 있으면 인접행렬과 유사함.
    - ex) 정점: 1만, 간선: 10만 -> 비완전그래프
    - 인접리스트로 구현해야 메모리초과에 대비할 수 있음.
    • 시간 복잡도
      - 연결관계(가중치) 조회/저장: O(outdegree(V))
      - A 정점과 B 정점이 연결되어 있는지 확인하려면 A 정점에 연결된 간선 리스트를 조회해야 하기때문에 진출차수만큼 탐색함.
      - 정점에 연결된 모든 간선 조회: O(outdegree(V))
    • 구현

List<Integer> graph[] = new List[V+1];
  for(int i=1; i<=v; i++){
      graph = new ArrayList<>();              
  }
  for(int i=0; i<e; i++){
      int src; int dst;
      graph[src].add(dst);
  }