TIl

그래프

아크몽 2024. 4. 1. 14:13

그래프

  • 노드와 간선으로 이루어진 자료구조
  • 데이터 간 관계를 표시하기 위해 사용
  • ⇒ 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계를 표현한다.
  • 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조
    • V : 정점의 개수, E : 그래프에 포함된 간선의 개수
    • V 개의 정점을 가지는 그래프는 최대 $V * (V-1) / 2$ 간선이 가능
      • 예) 5개의 정점의 최대 간선 수 10(=5*4/2)
  • 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기에 용이하다.

그래프 유형

  • 무향 그래프 (Undeirect)
  • 유향 그래프 ( directed)
  • 가중치 그래프 ( weighted )
  • 사이클 없는 방향 그래프 ( DAG, Directed Acyclic )
  • 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프
  • 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프

인접 정점

  • 인접 ( Adjacency)
    • 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.
    • 완전 그래프에 속한 임의의 두 정점들은 모두 인접해 있다.
  • 경로 : 간선들을 순서대로 나열한 것
    • 간선들: (0, 2, (2, 4) , (4, 6)
    • 정점들 : 0-2-4 -6
  • 경로 중 한 정점을 최대한 한번만 지나는 경로를 단순경로라 한다.
    • 0-2-4-6, 0-1-6
  • 시작한 정점에서 끝나는 경로를 사이클(Cycle) 이라고 한다. 1 - 3 - 5 - 1

그래프 표현

  • 간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결성
  • 인접 행렬 (Adjacent matrix)
    • MxM 크기의 2차원 배열을 이용해서 긴선 정보를 저장
    • 배열의 배열(포인터 배열)
  • 인접 리스트(Adjacent List)
    • 각 성점마다 해당 정점으로 나가는 건선의 정보를 저장
  • 간선의 배열
    • 간선(시작 정점, 끝 점점)을 배열에 연속적으로 저장

인접 행렬

  • 두 정점을 연결하는 간선의 유무를 행렬로 표현
  • IVI x IVI 장방형렬
  • 행 번호와 열 번호는 그래프의 정점에 대응
  • 두 정점이 인정되어 있으면 1. 그렇지 않으면 0으로 표현
  • 무향 그래프
    • i 번째 행의 합 = i 번째 열의 합 = V의 차수
  • 유향 그래프
    • 행 i의 합 = V의 진출 차수
    • 열 i의 합 = V의 진입 차수

인접 리스트

  • 각 정점에 대한 인접 정점들을 순차적으로 표현
  • 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장 ( 파이썬의 list가 이런식으로 작동함)
  • 무방향 그래프
    • 노드 수 = 간선의 수 * 2
    • 각 정점의 노드 수 = 정점의 차수
  • 방향 그래프
    • 노드 수 = 간선의 수
    • 각 정점의 노드 수 = 정점의 진출 차수

그래프 순회

친구 관계 문제

  1. A로 부터 시작해서 한 명의 친구에게만 소식을 전달, 전달 할 수 있다면 최대 몇 명의 친구가 소식을 전달 받을 수 있을까? ( 단 소식을 전달 받은 친구한테는 소식을 재 전달 할 수 없다.) ==DFS
  2. A로 부터 시작해서 친구들에게 동시에 소식을 전달할 수 있다고 할 때, 가장 늦게 전달 받는 사람은 누구일까? ( 단 친구에게 소식을 전달하는 속도는 동일하다) == BFS

Union-Find (Disjoint set)

서로소 집합(Disjoint-sets)

  • 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다.
    • 교집합이 없다는 말
  • 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다.
  • ⇒ 데이터가 같은 집합에 속해있다. =관계가 있다 = 그래프의 일종인 트리
  • 상호배타 집합을 표현하는 방법
    • 연결 리스트
    • 트리
  • 상호배타 집합 연산
    • Make-set ( x ) : 집합 만들기 ( 처음엔 자기 자신이 대표)
    • Find-Set( x ) : 너네 대표 누구야?
    • Union( x, y ) : 같은 집합으로 묶자

상호 배타 집합 표현 - 연결리스트

  • 같은 집합의 원소들은 하나의 연결리스트로 관리한다.
  • 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.
  • 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.

상호 배타 집합 표현 - 트리

  • 하나의 집합(a disjoint set)을 하나의 트리로 표현한다.
  • 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.

오프라인 강의

인접 행렬은 진출 차수, 진입 차수를 보기 편함 but 0이 너무 많아서 메모리 낭비

인접 리스트는 메모리 낭비 최소 but 진출 차수만 확인 가능

0이 많은 행렬 = 희소행렬