그래프

• 다대다 관계로 표현할 수 있다

• 트리는 그래프의 특별한 형태 (1:N 관계)

• 그래프는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조
  • 정점: 그래프의 구성요소로 하나의 연결점

  • 간선: 두 정점에 연결된 간선의 수

  • v개의 정점을 가지는 그래프는 최대 v*(v-1)/2 간선 가능 (무향그래프인경우) v*(v-1) 간선 가능 (유향그래프 가능)

• 인접 (Adjacency) : 두 개의 정점에 간선이 존재하면 서로 인접해 있다

  • 연결되어 있다, 관계가 있다 ( = 다 같은 말)

• 경로 : 어떤 정점(A)에서 시작하며 다른 정점(B)로 끝나는 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열한 것

  • 단순 경로 : 경로 중 한 정점을 최대 한 번만 지나는 경로
  • 순환 경로 : 단순 경로가 아닌 경우
    • 경로의 시작점과 끝점이 같음
    • 경로에서 어떤 정점을 2번이상 거치는 경우

그래프의 종류

• 무향그래프(양방향관계) vs 유향그래프(단방향관계)
• 가중치그래프 : 관계의 정도를 수치로 표현한 그래프
• 사이클 없는 방향 그래프 (DAG, Directed Acyclic Graph)
• 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프 ( v*v-1)
• 트리는 싸이클이 없는 무향 연결 그래프이다
  • 두 노드 사이에는 유일한 경로가 존재한다
  • 각 노드는 최대 하나의 부모 노드가 존재할 수 있다
  • 각 노드는 자식 노드가 없거나 하나 이상이 존재할 수 있다.

그래프 표현의 방법

• 인접 행렬 (정점중심) : v*v 크기의 2차원 배열을 이용해서 간선 정보 저장

  • 단점

    • 희소 그래프 : 그래프 정점은 상대적으로 많고 정점은 그에 비해 적다 ; 공간낭비가 발생한다 ; 탐색을 할 때도 비효율적이다 ;
    • 밀집 그래프 : 정점과 그에 따른 간선의 개수가 비례해서 많다 (= 완전그래프) ; 자기 자신만 빼고 다 채워져있다 ; 어쩔 수 없이 다 탐색을 해야 하므로 공간적인 측면에서 크기상 배열을 만들 수 있는지만 검사한다

• 인접 리스트 (정점중심) : 각 정점마다 다른 정점으로 나가는 간선의 정보를 목록으로 저장

  • 희소 그래프의 단점을 해결 => 공간, 시간 복잡도가 인접행렬보다 훨씬 효율적
  • 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장 (연결 리스트도 가능)
    • ⭐**포인터의 역할일 뿐이지 이어져있다고 연결된게 아니다 **⭐
    • 노드들의 순서는 상관이 없다
    • 정점개수 만큼 연결리스트를 가지고 있고 , 연결리스트 안에 head만 갖고 있다
    • ArrayList로 할 경우 안에 ArrayList안에 ArrayList[] 가 있다
    • 하지만 LinkedList는 head노드만 있으면 되므로 ArrayList보다 성능 더 좋다

• 간선 리스트 (간선중심) : 간선(시작 정점, 끝 정점)의 정보를 객체로 표현하여 리스트에 저장

  • N개의 간선 / [from , to] / 가중치
  • class Edge{}를 만들어서 구현

그래프 탐색

• BFS
  • 트리는 싸이클을 갖고 있지 않는 무향 그래프이기 때문에 visited[] 를 쓰지 않았다
  • 그래프는 다대다 관계이기 때문에 한 번만 탐색해야하므로 visited[] 가 필요하다
  • while( isEmpty() ){ size = que.size(); while ( size>0 ) { } }
  • 위 방법을 써서 같은 level에 있는 값만 빼오는 BFS코드를 짤 수 있다
• DFS

서로소 집합

• 서로소 또는 상호 배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다 => 교집합이 없다
• 대표자 : 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다
• 서로소 집합을 표현하는 방법
  • 연결 리스트
  • 트리
• 서로소 집합 연산
  • Make-Set() :: 단위집합 (크기가 1인집합) 을 만든다; 최초로 한번만 실행한다
  • Find-Set(x) :: x가 속한 집합을 찾는다
  • Union(x,y) :: x와 y의 집합을 합친다
• 문제점
  • 계속 아래로 합쳐질 수가 있다 , Depth가 깊어진다
• 해결방법
  • Rank를 이용한 Union
    • 대표자의 rank를 비교해서 높은 대표자 집합에 낮은 대표자의 집합을 추가하여 depth를 깊어지지 않게 한다
  • Path compression (패스압축)
    • return parents[a]=findSet(parents[a])
    • 대표자들끼리 그룹을 합치면 pass compression이 안이루어진다
    • 구성원이 대표자를 찾으러 가는 과정에서는 pass compression이 이뤄진다
    • 그래서 rank 관리를 하면서 Depth가 깊어지는 문제를 방지한다

최소신장트리 (MST)

• 그래프에서 최소 비용 문제

  1. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
  2. 두 정점 사이의 최소 비용의 경로 찾기

• 최소 신장 트리 (Minimum Spanning Tree)

  • 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리
• 크루스칼 알고리즘 ( 간선중심 )
  • 간선을 하나씩 선택해서 MST를 찾는 알고리즘
  1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
  2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다
     • 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
  3. 의미 있는 n-1개의 간선이 선택될 때까지 2를 반복
  • unoin-find 알고리즘으로 간선을 쓸지 말지(사이클)을 검사한다
• 프림 알고리즘 ( 정점중심 )
  • 이미 그룹이 된 친구들은 안보기 때문에 사이클이 발생하지 않는다
  • N개의 정점을 모두 고립되지 않도록 연결, 가중치의 합 “최소”

최단경로 알고리즘

• 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 가선의 가중치의 합이 최소인 경로
• 하나의 시작 정점에서 끝 정점까지의 최단 경로 (인접정렬, 인접리스트 사용)
  • 다익스트라 알고리즘 => 음의 가중치를 허용하지 않음
    • MST의 프림 알고리즘과 유사하다
  • 벨만 포드 알고리즘 => 음의 가중치 허용
• 모든 정점들에 대한 최단 경로
  • 플로이드-워샬 알고리즘 (DP)