<x,y> // 간선의 방향 x에서 y로 향함 x는 꼬리(tail) y는 머리(head)라 표현
방향 그래프
V(G) = {A,B,C,D}
E(G) = {<A,B>,<B,A>,<B,D>,<A,C>,<C,D>}
3) 연결 그래프(Connected Graph)
그래프에서 어떤 정점에서 다른 정점까지 갈 수 있는 경로가 존재하면 두 정점은 연결되었다고 한다. 모든 정점들에 대해서 어느 두 정점을 잡아도 갈 수 있는 경로가 존재하는 그래프가 연결 그래프(Connected Graph)이다. 그 반대는 단절 그래프(비 연결 그래프,Disconnected Graph)이다. 방향 그래프에서 임의의 두 정점 x,y에 대하여 x에서 y로 갈 수 있는 경로가 존재하고 아울러 y에서 x로 갈 수 있는 경로가 존재하면 이것을 강력 연결 그래프(Strongly Connected Graph)라 한다.
단절 그래프(비연결 그래프)
4) 다중 그래프(Multi Graph)
보통 그래프라고 하면 두 정점 사이의 간선은 무방향 그래프일 때는 한 개가 존재하고, 방향 그래프일 때는 두 개까지 존재할 수 있다. 그러나 두 정점 사이에 두 개 이상의 간선이 존재하는 그래프를 다중 그래프(multigraph)라고 한다. 일반적으로 그래프라고 하면 다중 그래프는 포함하지 않는다.
다중 그래프
정점 A와 C 사이에 간선 2개
정점 B와 C 사이에 간선 3개
5) 부분 그래프(Sub Graph)
그래프 G=(V,E)에 대해 그래프 G1=(V1,E1)가 V(G1)이 V(G)의 부분 집합이고, E(G1)가 E(G)의 부분집합이라면 그래프G1을 그래프G의 부분 그래프(subgraph)라고 한다.
6) 완전 그래프(Completed Graph)
n개의 정점을 갖는 무방향 그래프에서 간선의 최대 수는 n(n-1)/2이다. n개의 정점을 갖는 방향 그래프에서 간선의 최대 수는 n(n-1)이다. 어떤 그래프의 간선수가 최대 간선수를 가졌다면 이를 완전 그래프(completed graph) 라고 한다.
완전 그래프
정점이 5인 무방향 그래프의
최대 간선수는 5(5-1)/2 =10개이다.
7) 가중 그래프(Weighted Graph)
정점을 연결하는 간선에 가중치를 부여한 그래프로, 네트워크(Network)라고도 한다.
예를 들어 정점을 도시, 간선을 도로라고 하면, 간선에 부여된 가중치는 통행료, 이동 시간 등이 될 수 있다.
// 가중 그래프에서 최단 거리(가중치의 최소)를 구하기 위한 다익스트라(Dijkstra) 알고리즘이 있다.
**다익스트라는 추후 업로드 예정이다.
가중 그래프
3. 그래프 관련 용어
경로(Path) : 그래프의 두 정점 사이에 갈 수 있는 길을 순서대로 나열한 것이다.
단순 경로(Simple Path) : 한 경로 상에 있는 모든 정점들이 서로 다른 것을 단순 경로라 한다.// 단 처음과 끝의 정점은 같아도 된다
경로 길이(Length Of Path) : 경로를 구성하는 간선들의 수를 말한다.
사이클(Cycle): 처음과 끝의 경로가 같은 단순 경로를 말한다.
인접(Adjacency) : 정점 x와 정점 y가 간선에 의해 연결되어져 있다면, 이들 두 정점 x와 y를 인접(Adjacent)되어있다고 한다.
부속(Incident) : 정점 사이에 연결된 간선을 두 정점 X와 Y에 부속(Incident)되어있다고 한다.
차수(Degree) : 정점에 부속한(연결된) 간선의 수를 차수(Degree)라 한다. //방향 그래프인 경우는 진입 차수와 //진출 차수를 합한 것을 차수라고 말한다.
진입 차수(In-Degree) : 방향 그래프에서 어떤 정점으로 들어오는 간선의 수를 말한다. 즉 어떤 정점이 머리가 되는 간선의 수이다.
진출 차수(Out-Degree) : 방향 그래프에서 어떤 정점에서 다른 정점으로 나가는 간선의 수를 말한다. 즉. 어떤 정점이 꼬리가 되는 간선의 수이다.
// A B D는 단순 경로이다.// A B D의 경로 길이는 2이다.// A B C A는 사이클이다.// A C E는 C에서 E로 가는 간선이 없으므로 경로가 아니다.// A와 B는 인접해있다.// 간선(A,B)는 두 정점 A와 B에 부속되어 있다.// A의 차수는 2이고, E의 차수는 1이다.// H의 진입 차수는 2이고, 진출 차수는 4로서 H의 차수는 6이다.//방향 그래프의 모든 간선의 수는 모든 진입,진출 차수의 합을 2로 나눈 것과 같다. -> 방향 그래프의 모든 간선수 : (3 + 3 + 6 + 2 + 2)/2 ==8
연결 요소(Connected Component) : 그래프에서 어떤 정점으로부터 다른 정점으로 갈 수 있는 경로들의 집합을 연결 요소(connected component)라 한다. 이 연결 요소는 그래프의 최대로 연결된 부분 그래프가 된다.
운행(traverse) : 그래프에서 한 번에 하나의 노드를 찾아가면서(방문(visit)), 그래프의 모든 노드를 빠뜨리지 않고, 한 노드를 한 번씩 방문하는 것이다.
4. 그래프의 표현
1) 인접 행렬(Adjacency Matrix)
2차원 배열로 표현하고, 행렬 상의 원소들을 쉽게 접근할 수 있다. n개의 정점을 가지는 그래프는 n*n 정방 행렬이 되고, 두 정점이 인접되어 있으면 1로 인접되어 있지 않으면 0으로 표현한다.
인접 리스트는 각 정점에 인접한 간선들을 연결 리스트로 표현하는 방법이다. 그래프의 각 정점마다 1개의 리스트가 존재하므로 n개의 정점을 갖는 그래프는 n개의 연결 리스트로 표현된다. 인접 행렬에서는 그래프에 속하지 않는 간선들은 0으로 표현하는 반면, 인접 리스트에서는 표현되지 않는다. 연결 리스트의 각 노드는 정점 부분과 연결 부분으로 구성되고, 정점 부분에는 인접한 정점들을 표현하며 연결 부분은 다음 노드를 가리킨다. 따라서 어떤 정점의 연결 리스트를 모두 조사하면 그 정점에 인접한 정점들을 알 수 있다.
무방향 그래프방향 그래프
위의 그래프 들에서 A의 헤드를 예로 들면 B와 C노드를 가리키고 있는데, 순서는 의미 없다.
따라서 리스트가 아닌 vector를 이용해 쉽게 구현할 수 있다.
c++/visual studio 2017
#include <iostream>
#include <vector>
using namespace std;
//무방향 그래프
vector<int> graph1[4];
//방향 그래프
vector<int> graph2[4];
int main() {
//0 =='A' 1=='B' 2=='C' 3=='D'
cout << "무방향 그래프" << '\n';
graph1[0].push_back(1);
graph1[0].push_back(2);
graph1[1].push_back(0);
graph1[1].push_back(3);
graph1[2].push_back(0);
graph1[2].push_back(3);
graph1[3].push_back(1);
graph1[3].push_back(2);
for (int i = 0; i < 4; i++) {
cout << i << "이 가리키는 노드 : ";
for (int j = 0; j < graph1[i].size(); j++) {
cout << graph1[i][j]<<' ';
}
cout << '\n';
}
cout << '\n' << "방향 그래프" << '\n';
graph2[0].push_back(1);
graph2[0].push_back(2);
graph2[1].push_back(2);
graph2[2].push_back(0);
graph2[2].push_back(3);
graph2[3].push_back(0);
for (int i = 0; i < 4; i++) {
cout << i << "가 가리키는 노드 : ";
for (int j = 0; j < graph2[i].size(); j++) {
cout << graph2[i][j]<<' ';
}
cout << '\n';
}
return 0;
}
3) 인접 다중 리스트(Adjacenc MultiList)
5.그래프의 탐색
그래프에서 간선에 연결된 모든 정점을 방문하는 것이다.
1) DFS(Depth First Search) : 깊이 우선 탐색
DFS는 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색하여, 더 이상 탐색 가능한 노드가 없으면
다시 가장 마지막에 만났던 갈림길 간선으로 돌아가 다른 방향의 간선으로 탐색을 계속하여 모든 정점을 방문하는
순회 방법이다.
//DFS 알고리즘은 추후 업로드 예정이다.
2) BFS(Breadth First Search) 너비 우선 탐색
BFS는 시작 정점에서 인접한 정점들을 모두 차례로 방문하고, 방문했던 정점에 대해 다시 인접한 정점들을
차례로 방문하는 방식으로, 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회 방법이다.
댓글