[자료구조] 그래프

그래프

• “관계” 를 그래프로 추상화 하여 다룰 수 있음 (자료구조의 정의)
• 전기회로의 분석, 최단 거리 탐색, 프로젝트 계획, 스케줄링, 운송, 컴퓨터 네트워크 시뮬레이션 등등

그래프의 정의

• 그래프 G는 하나 이상의 정점(혹은 노드) 을 포함하는 집합 V 와 두 정점의 쌍으로 구성되는 간선을 포함하는 집합 E의 순서 쌍으로 정의함
• 그래프 G = (V ,E)

그래프의 정의 - 정점과 간선

V = {a,b,c,d} (정점의 집합)

E = {1,2,3,4,5,6,7} (간선의 집합)

G = (V,E) = ({a,b,c,d} , {1,2,3,4,5,6,7}) (정점과 간선의 합)

그래프 용어의 정의

• 간선은 두 정점을 연결하는 선
• 그래프는 연결(간선)에 방향성이 없는 무방향 그래프와 방향성을 갖는 방향 그래프가 있음
• 무방향 그래프는 간선의 방향성이 없음
• 방향 그래프는 간선의 방향성이 있음
• 무방향 그래프의 간선은 실선으로 나타내고
• 방향 그래프의 간선은 화살표로 나타냄
• 간선은 두 정점 쌍으로 나타냄
• 무방향 그래프일 때는 정점 쌍이 순서를 나타낼 필요가 없으므로 어떤 간선이 두 정점 v1,v2를 잇는 것이라면 {v1,v2} 로 나타냄
• 방향 그래프의 간선은 순서 쌍 (v1,v2) 로 표시함

그래프 연결 - 방향 무방향 혼합 그래프

출처) 방송통신대학교 자료구조 강의

• 방향 그래프

G(b) = (V,E) , V = {v1,v2} , E = {(v1 , v2)}

G(e) = (V,E)

V = {v1,v2,v3,v4},

E = {(v1,v2) , (v,2,v4) , (v2,v3) , (v4,v3) , (v3,v1)}

• 무방향 그래프

G(f) = (V,E),

V = {v1,v2,v3,v4,v5} ,

E = {{v1,v2} , {v1,v3} , {v2,v3} , {v2,v4} , {v3,v4}}

• 혼합 그래프

G(d) = (V,E),

V = {v1,v2,v3,v4} ,

E = {(v2 ,v1) , (v2,v3) , {v2,v4} , {v1,v3} , (v4,v3)}

다중 그래프

• 다중 그래프 : 두 정점을 잇는 간선이 여러 개인 그래프
• 방향 다중 그래프 : 방향성을 갖는 간선으로 이루어진 다중 그래프
• 무방향 다중 그래프 : 방향성이 없는 간선으로 이루어진 다중 그래프

가중 그래프

• 가중 그래프 : 간선이 가중치를 갖는 그래프

그래프의 성질

• n개의 정점을 갖는 무방향 그래프에서 v1 != vj 인 서로 다른 무순서 쌍 {vi , vj} 의 최대 개수

→ nC2 = 2/n(n-1)

• n개의 정점을 갖는 방향 그래프에서 v1 != vj 인 서로 다른 순서 쌍 (vi , vj) 의 최대 개수

→ nP2 = n(n-1)

• 완전 그래프 : 모든 정점들이 간선으로 서로 연결된 그래프
• 완전 그래프인 (만일 정점의 수를 n이라고 하면) 무방향 그래프의 간선 개수

→ 2/n(n-1)

• 두 정점 vi 와 vj 가 서로 인접한다.
• 독립 정점 : 다른 어떤 정점과도 인접하지 않은 정점
• 널(null) 그래프 : 독립 정점만으로 구성한 그래프이며, 간선 집합E는 공집합임
• 경로(path) : 임의의 두 정점을 연결하는 어떤 간선의 끝 정점(해당 간선의 머리) 에서 그 간선의 시작 정점(해당 간선의 꼬리) 으로 이어지는 간선의 연속(열)
• 무방향 그래프 G에 대해 E(G) 에 속하는 순서 없는 간선 {vp,v1},{v1,v2} … {vn-1 , vn} , {vn,vq} 가 있을때, 그래프 G의 정점 vp에서 vq 까지의 경로는 정점 vp…vq 들의 연속을 말함
• 만일 G가 방향 그래프인 경우 정점 vp에 대해서 정점 vq 까지의 경로는 E(G)에 속하는 순서 있는 간선들 (vp,v1), (v1,v2) … (vn-1,vn),(vn,vq) 로 구성
• 특별한 언급이 없는 경우 정점 vp 에서 정점 vq 까지 경로는 vp,v1,…,vn,vq 와 같은 경로상의 간선을 구성하는 정점 순서열로 표시
• 경로 길이 : 경로에 있는 간선의 수
• 단순 경로 : 경로 상에 있는 모든 정점이 서로 다른 경로
• 기본 경로 경로 상에 있는 모든 간선이 서로 다른 경로

방향 그래프

• 그래프의 정점 v2 에서 출발하여 정점 v4 에서 끝나는 경로 중에서 단순 경로
• 사이클 : 출발점과 도착점이 동일한 단순 경로
• 사이클 그래프 : 사이클이 있는 그래프

그래프 이론에서 사용하는 용어 정리

• 방향 그래프에서

→ 진입 차수 : 주어진 정점으로 향한 간선의 개수

→ 진출 차수 : 주어진 정점에서 시작하는 간선의 개수

→ 정점의 차수 : 진출 차수와 진입 차수의 합

• 무방향 그래프에서

→ 차수 : 정점에 연결된 간선들의 개수

• 루프 : 간선의 시작점과 끝점이 같은 정점인 길이가 1인 경로
• 무사이클 그래프 : 사이클이 없는 그래프 혹은 트리

추상자료형

그래프의 추상 자료형

• 객체의 정의 : 정점과 간선의 유한 집합

연산	내용
Graph Creat()	그래프 생성
Destroy(Graph)	그래프 기억 장소 반납
Graph Copy_Tree(Graph)	그래프 복사
InsertVertex()	그래프에 정점 삽입
InsertEdge()	그래프에 간선 추가
DeleteVertex()	정점 삭제
DeleteEdge()	간선 삭제
Search()	정점 탐색
IsAdjacent()	인접 정점 여부 확인
ExistPath()	경로가 존재하는지 확인
PathLength()	경로 길이 계산
BFS()	너비 우선 탐색
DFS()	깊이 우선 탐색

그래프의 표현 방법

그래프의 두 가지 표현 방법

• 인접 행렬
• 인접 리스트

 

그래프 탐색

그래프 탐색이란 ?

• 그래프에서 특정 정점을 찾는 연산
• 그래프 G = (V,E) 와 V(G) 에 있는 정점이 v 가 주어졌을 때, 정점 v 에 도달할 때 까지 G의 정점을 방문하는 연산

→ 만일 그래프 내에 정점이 v가 없다면, 그래프 의 모든 정점을 방문한 후 종료

• 그래프 탐색 (순회) :

→ 깊은 우선탐색 (DFS) 과 너비 우선 탐색(BFS) 두 가지 방법이 있음

깊이 우선 탐색

1. 시작 : 출발점 v 를 방문
2. 다음으로 v에 인접하고 아직 방문하지 않은 정점 w를 선택하여 w를 출발점으로 다시 깊이 우선 탐색 ( 인접하고 아직 방문하지 않은 정점을 선택 )
3. 위 두 과정을 모든 정점을 한 번씩 방문할 때 까지 반복

• 만약 인접한 모든 정점들이 이미 방문한 정점인 경우 가장 최근 방문했던 정점 중, 방문하지 않은 정점w를 가진 정점을 선택하여 정점w로 부터 다시 깊이 우선 탐색 시작

→ 스택을 사용하여 가장 최근에 선택의 지점에 있던 정점을 찾아냄

• 방문하지 않은 정점이 없으면 탐색을 종료