개요
- 차수(degree) : 정점에 연결된 간선의 수
- 정점(vertex)
- 간선(edge)
정의
- 그래프 G : 2개의 집합 V와 E로 구성
- V : 공집합이 아닌 정점(vertex)의 유한집합
- E : 간선(edge)이라고 하는 정점 쌍들의 집합
- 무방향 그래프
- 방향 그래프
- 방향을 가지는 정점의 쌍<u, v>로 표시
(u는 꼬리(tail), v는 머리(head))
- <u,v>와 <v,u>는 서로 다른 간선
제한 사항
-
자기 간선(self edge) 또는 자기 루프(self loop)가 없음
-
동일 간선의 중복 없음 / 다중 그래프는 예외
-
완전 그래프 : n개의 정점과 n(n-1)/2개의 간선을 가진 그래프
용어
- 정점 u로부터 정점 v까지의 경로(path)
- 그래프 G에서 (u,i1), (i1,i2), (i2,i3),... (ik,v)를 E(G)에 속한 간선들이라 할 때, 정점열 u, i1, i2, i3 .... v를 말함
- 경로의 길이(length)
- 단순 경로(simple length)
- 경로상에서 처음과 마지막을 제외한 모든 정점들이 서로 다름
- 단순 방향 경로(simple directed path)
- 사이클(cycle)
인접 리스트(Adjaceny Lists)
- 인접행렬의 n행들을 n개의 체인으로 표현
- n개의 정점, e개의 간선의 무방향 그래프
- n개의 헤드노드, 2e개의 리스트 노드가 필요
- 방향 그래프 : e개의 리스트 노드
- 연결 리스트 노드의 순차적 저장 : 배열 node[]
- node[i] = 정점 i에 대한 리스트 시작 지점
- node[n] = n + 2e + 1
- 정점 i와 인접한 정점
- node[i], .... node[i+1]-1에 저장
- 역인접리스트
- 리스트가 표현하는 정점에 인접한 각 정점에 대해 하나의 노드
Ex)
인접다중리스트(Adjacency Multilists)
- 간선(u,v)는 두 개의 엔트리로 표현
: u를 위한 리스트, v를 위한 리스트에 나타남
- 새로운 노드 구조
가중치 간선(Weighted Edges)
- 그래프의 간선에 가중치 부여
- 인접행렬 : 행렬 엔트리에 a[i][j]의 가중치 정보 저장
- 인접리스트 : 노드 구조에 weight 필드를 추가
- 네트워크 : 가중치 간선을 가진 그래프
그래프 기본 연산
깊이 우선 탐색 (DFS: Depth-First Search)
- 출발 정점 v를 방문
- v에 인접하고 방문하지 않은 한 정점 w를 선택
- w를 시작점으로 다시 깊이 우선 탐색 시작
- 모든 인접 정점을 방문한 정점 u에 도달하면, 최근에 방문한 정점 중 아직 방문을 안한 정점 w와 인접하고 있는 정점으로 되돌아감
- 정점 w로부터 다시 깊이 우선 탐색 시작
- 방문을 한 정점들로부터 방문하지 않은 정점으로 더 이상 갈 수 없을 때 종료
Ex)
DFS 분석
- 탐색을 끝내는 시간 O(e)
- v에 인접한 모든 정점을 찾는데 O(n)의 시간
- 총 시간 O(n2)
너비 우선 탐색 (BFS: Breadth-First Search)
- 시작 정점 v를 방문
- v에 인접한 모든 정점들을 방문
- 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문
Ex)
BFS 분석
- 전체 시간 O(n2)
- 인접 리스트 표현 : 전체 비용 O(e)
연결요소
방문하지 않은 정점 v에 대해 DFS 또는 BFS를 반복 호출로 구함
- 인접리스트로 표현 : 모든 연결요소들 생성 시간은 O(n+e)
- 인접행렬로 표현 : O(n2)
최단경로와 이행적 폐쇄
단일 시발점/모든 종점 : 음이 아닌 간선 비용
참조