그래프 개관

• 객체들의 상호 관계를 표현하기 위해 고안된 자료 구조
• 계층 관계만을 표현하는 트리에 비해 훨씬 다양한 현실 세계의 문제 표현

개요

그래프 표현

• 인접 행렬 표현 - 모든 정점의 관계를 표현. 밀집 그래프에서 유리
• 인접 리스트 표현 - 그래프 간 간선의 관계만 표현. 희소 그래프에서 유리
• 암시적 그래프 표현
  •  ex) 좌표 표현 - 연결관계가 암시적(바로 옆의 좌표)으로 표현됨
  • 문제가 비교적 단순한 경우 . 그래프 표현이 번거로워 사용
  • 그래프가 아주 큰데, 일부만 사용(정점을 모두 그리지 않음)
  • 단점. 그래프를 사용하는 알고리즘과 변환과정이 합쳐짐 → 코드가 복잡해짐

깊이 우선 탐색(DFS)

• 대표적 그래프 알고리즘. 재귀 사용
• 내부적으로 스택이 됨.

너비 우선 탐색(BFS)

• 가중치가 없는 그래프에서 두 점 사이의 최단 경로 찾기
• 큐 사용
• 만능은 아님
• 너비 우선 탐색을 사용 할 수 없는 특수한 경우(너무 넓은 경우) 사용하는 방법
  • 양방향 탐색 - 끝에서도 거꾸로 올라와 중간에서 만남
  • 점점 깊어지는 탐색 - 깊이 제한을 정한 후, 제한보다 짧은 경로가 있는지 깊이 우선 탐색.

가중치가 있는 그래프 상의 최단 경로 찾기

• 상황에 따라
  • 음수 가중치
  • 경로의 출발점이 하나로 고정(p to p)인지, 전체에 대한 것인지(all to all)

종류 

• 다익스트라 - p to p . 우선순위 큐 이용. 양수에만 추천
• 벨만-포드 - p to p. 음수도 됨. 음수 사이클 체크 가능. 각 정점까지 상한을 예측 후 갱신(완화)
• 플로이드 - all to all 특화 .
  • 각 정점쌍의 최단거리를 2차원 배열에 저장 후 점화식 활용
  • 가중치 없는 그래프의 각 정점간 도달 가능성 여부 계산 가능

최소 스패닝 트리

• 가중치가 있는 그래프에서 가중치의 합이 최소가 되도록 간선의 부분 집합을 선택해 정점을 모두 연결

종류 - 둘다 그리디를 이용한다.

• 크루스칼 - 전체 간선 중 가중치 작은 것부터 더함. 상호 배타적 집합구조 쓰면 좋음
• 프림 - 점점 늘려가면서 가장 작은 간선을 추가함 (이것을 정점에 대해 반복해 최적화)

그래프의 최대 유량 문제

• 간선에 길이 뿐만 아니라 용량을 정의함
• 그래프와 상관 없어 보이는 문제를 풀 때 유용
• 포드-풀커슨 알고리즘

정의

• G(V,E) 형식으로 표현
  • G - Graph
  • V - Vertex;정점
  • E - Edge; 간선
  • 정점의 위치 정보, 간선의 순서는 포함되지 않음

종류

• 방향 그래프(;유향 그래프) - 간선이 방향이라는 속성을 가짐
• 무향 그래프 - 간선에 방향이 없음
• 가중치 그래프 - 각 간선에 가중치라는 속성 부여
  • 도시 사이의 거리, 물건 사이의 교환 비율, 두 사람 사이의 호감도 등
• 다중 그래프 - 두 정점 사이에 두개 이상의 간선이 있을 수 있음
• 단순 그래프 - 두 정점 사이에 최대 한 개의 간선만 있음
• 트리, 루트 없는 트리 - 부모, 자식 관계만 성립하지 않는 트리 형태
• 이분 그래프 - 정점을 두개의 그룹으로 나누고 다른 그룹에 속한 정점들 끼리만 간선 존재 (남, 여 연결 관계)
• 중복 속성
  • 사이클 없는 방향 그래프(DAG;Directec Acyclic Graph) - 작업들 간의 상호 의존 관계를 나타낼 수 있음
    • 방향을 무시한다면 사이클이 존재할 수도 있다.

경로

• 단순 경로 - 경로 중 한 점을 최대 한 번만 지나는 경로; 그래프에서 경로라고 하면 대부분 단순경로임
• 사이클(cycle;회로) - 시작한 점에서 끝나는 경로

그래프 사용 예

• 철도의 안정성 분석 - 절단점 찾기 알고리즘
• 소셜 네트워크 분석 - (너비 우선 탐색) 한다리 건너 알고 있는 사람 몇명? 몇다리 건너야 다른 사람 만나는지?
• 인터넷 전송 속도 계산 - 최소 스패닝 트리
• 한 붓 그리기 - 오일러 경로(깊이 우선 탐색)
• 외환 거래 - 아비트리지.
  • 간선의 가중치를 전부 곱했을 때 1을 초과하는 값
  • 간선 가중치의 합이 음수임

암시적 그래프 구조

• 그래프 형태를 갖는 구조가 아닌데 그래프로 표현하면 쉬운 문제
• 할일 목록 정리 → 의존관계 (위상정렬;topological Sorting)
• 15-퍼즐 → 상태공간(게임판의 상태 전체를를 정점으로 생성)
• 게임판 덮기 → 이분 그래프. 이분 매칭 알고리즘
• 회의실 배정 → 2-SAT 문제 → 그래프에서의 강 결합성 문제로 변환