.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
그래프 관련 용어
•
정점(vertex): 위치라는 개념. (node 라고도 부름)
•
간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
•
인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
•
정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
•
무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
•
진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
•
진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
•
방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
•
경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
•
단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
•
사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우
그래프(Graph)의 개념
•
단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조
•
연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조
오일러 경로(Eulerian tour)
- 그래프에 존재하는 모든 간선(edge)을 한 번만 통과하면서 처음 정점(vertex)으로 되돌아오는 경로
- 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재
그래프의 특징
•
각 노드들은 계층 구조를 갖지 않고 서로가 서로에게 갈 수 있는 ‘간선’으로 이루어진 구조이다.
•
트리와 그래프의 차이
1.
트리는 비순환 방식, 그래프는 순환/비순환 선택이 가능하다.
2.
트리는 무조건 방향이 있다. 그러나 그래프는 선택이 가능하다.
3.
트리는 계층 모델이나, 그래프는 네트워크 모델이다.
방향/무방향/가중 그래프
•
무방향 그래프(Undirected Graph)
◦
무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
◦
정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
▪
(A, B)는 (B, A) 동일
◦
Ex) 양방향 통행 도로
•
방향 그래프(Directed Graph)
◦
간선에 방향성이 존재하는 그래프
◦
A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다.
▪
<A, B>는 <B, A>는 다름
◦
Ex) 일방 통행
방향 그래프(Directed Graph)
•
모든 간선이 방향 간선인 그래프
•
진입간선들(in-edges)과 진출간선들(out-edges)을 각각 별도의 인접리스트로 보관한다면, 진입간선들의 집합과진출간선들의 집합을 각각의 크기에 비례한 시간에 조사 가능하다.
무방향 그래프(Undirected Graph)
가중치 그래프(Weighted Graph)
•
간선에 비용이나 가중치가 할당된 그래프
•
== ‘네트워크(Network)’
◦
Ex) 도시-도시의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등
•
무방향 그래프에서 가중치가 달린 그래프
•
방향 그래프에서 가중치가 달린 그래프
연결/비연결 그래프
연결 그래프(Connected Graph)
•
무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
Ex) 트리(Tree): 사이클을 가지지 않는 연결 그래프
비연결 그래프(Disconnected Graph)
•
무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
순환/비순환 그래프
순환(Cycle)
•
단순 경로 시작 정점과 종료 정점이 동일한 경우
단순 경로 : 경로 중에서 반복되는 정점이 없는 경우
비순환(Acyclic Graph)
•
사이클이 없는 그래프
완전 그래프(Complete Graph)
•
그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
◦
무방향 완전 그래프
◦
정점 수: n이면 간선의 수: n * (n-1) / 2
그래프 구현 방법
인접 리스트
•
일반적인 방법
•
모든 정점(노드)을 인접 리스트에 저장
◦
각각의 정점에 인접한 정점들을 리스트로 표시한 것
◦
배열(혹은 해시테이블)과 배열의 각 인덱스마다 존재하는 또 다른 리스트(배열, 동적 가변 크기 배열(ArrayList), 연결리스트(LinkedList) 등)를 이용해서 인접 리스트를 표현
0: 1
1: 2
2: 0, 3
3: 2
4: 6
5: 4
6: 5
Python
복사
◦
정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 리스트에 쉽게 접근 가능
•
무방향 그래프(Undirected Graph)에서 (a, b) 간선은 두 번 저장
•
트리에선 특정 노드 하나(루트 노드)에서 다른 모든 노드로 접근이 가능 -> Tree 클래스 불필요
•
그래프에선 특정 노드에서 다른 모든 노드로 접근이 가능하지는 않음 -> Graph 클래스 필요
인접 행렬
•
인접 행렬은 NxN 불린 행렬(Boolean Matrix)로써 matrix[i][j]가 true라면 i -> j로의 간선이 있다는 뜻
if(간선 (i, j)가 그래프에 존재)
matrix[i][j] = 1;
else
matrix[i][j] = 0;
Python
복사
•
정점(노드)의 개수가 N인 그래프를 인접 행렬로 표현
◦
간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요하다.
•
무방향 그래프를 인접 행렬로 표현한다면 이 행렬은 대칭 행렬(Symmetric Matrix)이 된다.
◦
물론 방향 그래프는 대칭 행렬이 안 될 수도 있다.
•
인접 리스트를 사용한 그래프 알고리즘들(Ex. 너비 우선 탐색) 또한 인접 행렬에서도 사용이 가능하다.
◦
하지만 인접 행렬은 조금 효율성이 떨어진다.
◦
인접 리스트는 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있지만 인접 행렬에서는 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다.
인접 리스트와 인접 행렬 중 선택 방법
•
인접 리스트
◦
그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우
◦
장점
▪
어떤 노드에 인접한 노드들 을 쉽게 찾을 수 있다.
▪
그래프에 존재하는 모든 간선의 수 는 O(N+E) 안에 알 수 있다. : 인접 리스트 전체를 조사한다.
◦
단점
▪
간선의 존재 여부와 정점의 차수: 정점 i의 리스트에 있는 노드의 수 즉, 정점 차수만큼의 시간이 필요
•
인접 행렬
◦
그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph) 의 경우
◦
장점
▪
두 정점을 연결하는 간선의 존재 여부 (M[i][j])를 O(1) 안에 즉시 알 수 있다.
정점의 차수 는 O(N) 안에 알 수 있다. : 인접 배열의 i번 째 행 또는 열을 모두 더한다.
◦
단점
▪
어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야 한다.
그래프에 존재하는 모든 간선의 수는 O(N^2) 안에 알 수 있다. : 인접 행렬 전체를 조사한다.
