![[자료구조] 그래프 (Graph) - 인접행렬 vs 인접리스트, DFS, BFS, Connected Component, Spanning Tree](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcoHi34%2FbtqSjAPXa41%2FDwji6MLkkGCfd09dsTxnzk%2Fimg.png)
1. 그래프
1.1 그래프란?
그래프(Graph)란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다.
그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다.
G = (V, E)
수학적으로 그래프를 표시하는 방법이다.
V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다.
그래프는 수학자 오일러(Euler)에 의해 창안되어 수학의 한 분야로서 수백 년 간 연구되어 왔지만, 컴퓨터 과학 분야에서 그래프 알고리즘을 다루기 시작한 것은 오래되지 않았다.
지하철 노선도, 도심의 도로 등 실생활의 다양한 예를 그래프로 표현하고 활용할 수 있으며, 특히 알고리즘에서 굉장히 많이 사용되므로 그래프에 대해 반드시 공부해야 한다.
※ 오일러 경로 (Eulerian Tour)
- 그래프에 존재하는 모든 간선을 한번만 통과하면서 처음 정점으로 되돌아오는 경로
- 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재 (오일러의 정리)
1.2 그래프 용어
-
정점 (vertex)
노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소이다.
-
간선 (edge)
링크(link)라고도 하며 정점 간의 관계를 나타낸다.
-
인접 정점 (adjacent vertex)
하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻한다.
위 그래프에서 정점C의 인접 정점은A,D이다. -
차수(degree)
정점에 연결된 간선의 수를 말한다.
위 그래프에서 정점A의 차수는 3이고, 모든 정점의 차수를 합하면 8이다.
무방향 그래프에서 하나의 간선은 두 개의 정점에 인접하기 때문에 간선 수에 2배를 해주면 된다.방향 그래프의 경우 외부에서 오는 간선의 수를 진입 차수(in-degree)라고 하며, 외부로 향하는 간선의 수를 진출 차수(out-degree)라고 한다.
-
경로 (path)
간선을 따라갈 수 있는 길을 말하며, 정점을 나열하여 표시한다.
정점s로부터 정점e까지의 경로는s, v₁, v₂ ... e로 표현하며, 반드시 정점들 간의 간선이 존재해야 한다.
너무나도 당연하게도 간선이 존재하지 않는 길은 경로가 될 수 없다. -
경로의 길이 (length)
경로를 구성하는 데 사용된 간선의 수를 뜻한다.
-
단순 경로 (simple path)
경로 중에서 반복되는 간선이 없는 경로이다.
-
사이클 (cycle)
시작 정점과 종료 정점이 같은 단순 경로를 뜻한다.
위 그래프에서A, C, D, A경로를 사이클이라고 한다.
추가로 그래프를 표현하는 방법에 대해서도 알아보자.
- V(G1) = {0, 1, 2, 3}, E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}
- V(G2) = {0, 1, 2, 3}, E(G2) = {(0, 1), (0, 2)}
- V(G3) = (0, 1, 3}, E(G3) = {<0, 1>, <1, 0>, <1, 2>}
1.3 그래프의 종류
그래프는 간선(edge)의 종류에 따라 구분된다.
무방향 그래프 (Undirected Graph)
두 정점을 연결하는 간선에 방향이 없는 그래프이며, 양 방향으로 이동이 가능하다.
위 그래프의 경우 (A, B)로 표현한다.
방향 그래프 (Directed Graph)
두 정점을 연결하는 간선에 방향이 존재하는 그래프이며, 간선의 방향으로만 이동할 수 있다.
위 그래프의 경우 <A, B>로 표현한다.
가중치 그래프 (Weighted Graph)
간선에 비용(cost) 또는 가중치(weight)가 할당된 그래프이다. 네트워크(network)라고 불리기도 한다.
완전 그래프 (Complete Graph)
모든 정점 간에 간선이 존재하는 그래프이다.
무방향 완전 그래프의 정점의 수가 n이라면, 전체 간선의 수는 n * (n-1) / 2 가 된다.
위 그래프의 경우 n=4이며 간선의 수는 (4*3)/2=6 이다.
1.4 그래프 ADT
객체
- 정점의 집합과 간선의 집합
연산
- create() : 그래프 생성
- insertVertex(v) : 그래프에 정점 v 삽입
- insertEdge(u, v) : 그래프에 u정점과 v정점을 연결하는 간선 삽입
- deleteVertex(v) : 그래프에서 정점 v 삭제 (v에 연결된 모든 간선도 함께 삭제)
- deleteEdge(u, v) : 그래프에서 u정점과 v정점을 연결하는 간선 삭제
- adjacent(v) : 정점 v에 인접한 모든 정점을 반환
1.5 그래프 구현 - 인접 행렬 (Adjacency Materix)
컴퓨터에서 그래프를 구현하는 방법에는 배열(Array)을 사용하는 방법과 연결리스트(Linked List)를 사용하는 방법이 있다.
인접 행렬을 이용한 그래프 구현
그래프의 정점을 2차원 배열로 만든 것이다.
정점의 개수가 n이라면 n*n 형태의 2차원 배열이 인접 행렬로 사용된다.
인접 행렬에서 행과 열은 정점을 의미하며, 각각의 원소들은 정점 간의 간선을 나타낸다.
무방향 그래프는 (a), (b)에서 볼 수 있듯이 인접 행렬이 대칭적 구조를 가진다.
(두 개의 정점에서 간선이 동시에 연결되어 있기 때문)
가중치 그래프의 경우 행렬에서 0과 1이 아니라 각 간선의 가중치 값이 저장된다.
(이 경우 가중치가 0인 것과 간선이 없는 것이 구별돼야 함)
장점
-
2차원 배열에 모든 정점들의 간선 정보가 있기 때문에, 두 정점을 연결하는 간선을 조회할 때
O(1)시간복잡도로 가능하다. -
정점(i)의 차수를 구할 때는 다음과 같이 인접행렬(M)의 i번째 행의 값을 모두 더하면 되므로
O(n)의 시간복잡도를 가진다.( $degree(i) = \sum_{k=0}^{n-1}{M[i][k]}$ )
-
구현이 비교적 간단하다.
단점
- 간선의 수와 무관하게 항상 n² 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
- 그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로
O(n²)의 시간이 소요된다.
C++ 구현
/*
* 9.1
* 인접 행렬(Adjacency Matrix)를 이용한 Graph 구현
*/
#include <iostream>
using namespace std;
#define MAX_VTXS 256 // 최대 정점 개수
class AdjMatGraph{
private:
int size; // 정점의 개수
char vertices[MAX_VTXS]; // 정점의 이름
int adjMat[MAX_VTXS][MAX_VTXS]; // 인접 행렬
public:
AdjMatGraph(){
reset();
}
~AdjMatGraph(){}
char getVertex(int i){
return vertices[i];
}
int getEdge(int i, int j){
return adjMat[i][j];
}
void setEdge(int i, int j, int val){
adjMat[i][j] = val;
}
// 그래프 초기화
void reset(){
for(int i=0; i<MAX_VTXS; i++){
for(int j=0; j<MAX_VTXS; j++){
setEdge(i, j, 0);
}
}
size = 0;
}
// 정점 삽입
void insertVertex(char name){
if(isFull()){
cout << "Graph vertex full error" << endl;
return;
}
vertices[size++] = name;
}
// 간선 삽입 (무방향 그래프)
void insertEdge(int u, int v){
setEdge(u, v, 1); // 가중치 그래프에서는 1이 아닌 가중치 삽입
setEdge(v, u, 1); // 방향 그래프에서는 삭제 (<u,v>만 존재)
}
// 그래프 정보 출력
void display(){
cout << "vertex size : " << size << endl;
cout << " ";
for(int i=0; i<size; i++){
cout << getVertex(i) << " ";
}
cout << endl;
for(int i=0; i<size; i++){
cout << getVertex(i) << " : ";
for(int j=0; j<size; j++){
cout << getEdge(i, j) << " ";
}
cout << endl;
}
}
bool isEmpty(){
return size == 0;
}
bool isFull(){
return size >= MAX_VTXS;
}
};
int main(){
AdjMatGraph graph;
// 정점 삽입 (A, B, C, D)
graph.insertVertex('A'); // 0
graph.insertVertex('B'); // 1
graph.insertVertex('C'); // 2
graph.insertVertex('D'); // 3
// 간선 삽입
graph.insertEdge(0, 1); // A->B
graph.insertEdge(0, 2); // A->C
graph.insertEdge(0, 3); // A->D
graph.insertEdge(2, 3); // C->D
graph.display();
return 0;
}
인접행렬을 이용하여 아래와 같은 그래프를 구현하였다.
1.6 그래프 구현 - 인접 리스트 (Adjacency List)
인접 리스트를 이용한 그래프 구현
그래프의 각 정점에 인접한 정점들을 연결리스트(Linked List)로 표현하는 방법이다.
즉 정점의 개수만큼 인접리스트가 존재하며, 각각의 인접리스트에는 인접한 정점 정보가 저장되는 것이다.
그래프는 각 인접리스트에 대한 헤드포인터를 배열로 갖는다.
무방향 그래프의 경우 간선이 추가되면 각각의 정점의 인접리스트에 반대편 정점의 노드를 추가해야 한다.
장점
- 존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 보다 효율적이다.
- 그래프의 모든 간선의 수를 알아내려면 각 정점의 헤더 노드부터 모든 인접리스트를 탐색해야 하므로 O(n+e)의 시간이 소요된다.
단점
- 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하므로 정점의 차수만큼의 시간이 필요하다.
O(degree(v)) - 구현이 비교적 어렵다.
C++ 구현
/*
* 9.2
* 인접 리스트(Adjacency List)를 이용한 Graph 구현 (무방향 그래프)
*/
#include <iostream>
using namespace std;
#define MAX_VTXS 256 // 최대 정점 개수
struct Node{
private:
int id; // vertex id
Node* link; // next node's pointer
public:
Node(int _id, Node* _link){
id = _id;
link = _link;
}
~Node(){};
// getter/setter
int getId(){
return id;
}
void setId(int _id){
id = _id;
}
Node* getLink(){
return link;
}
void setLink(Node* _link){
link = _link;
}
};
class AdjListGraph{
private:
int size; // 정점의 개수
char vertices[MAX_VTXS]; // 정점의 이름
Node* adjList[MAX_VTXS]; // 인접 리스트
public:
AdjListGraph(){
size = 0;
}
~AdjListGraph(){}
char getVertex(int i){
return vertices[i];
}
// 그래프 초기화
void reset(){
for(int i=0; i<size; i++){
if(adjList[i] != NULL){
delete adjList[i];
}
}
size = 0;
}
// 정점 삽입
void insertVertex(char name){
if(isFull()){
cout << "Graph vertex full error" << endl;
return;
}
vertices[size] = name;
adjList[size++] = NULL;
}
// 간선 삽입 (무방향 그래프)
void insertEdge(int u, int v){
// 인접리스트에 추가
adjList[u] = new Node(v, adjList[u]); // 새로운 노드로 head pointer가 바뀜 (새로운 node는 기존의 head pointer를 link로 함)
adjList[v] = new Node(u, adjList[v]); // 방향 그래프에서는 삭제 (<u,v>만 존재)
}
// 그래프 정보 출력
void display(){
cout << "vertex size : " << size << endl;
for(int i=0; i<size; i++){
cout << getVertex(i) << " : ";
Node* head = adjList[i];
while(head != NULL){
cout << getVertex(head->getId()) << " ";
head = head->getLink();
}
cout << endl;
}
}
// 'v'번째 정점의 인접 정점 리스트 반환
Node* adjacent(int v){
return adjList[v];
}
bool isEmpty(){
return size == 0;
}
bool isFull(){
return size >= MAX_VTXS;
}
};
int main(){
AdjListGraph graph;
// 정점 삽입 (A, B, C, D)
graph.insertVertex('A'); // 0
graph.insertVertex('B'); // 1
graph.insertVertex('C'); // 2
graph.insertVertex('D'); // 3
// 간선 삽입
graph.insertEdge(0, 1); // A->B
graph.insertEdge(0, 2); // A->C
graph.insertEdge(0, 3); // A->D
graph.insertEdge(2, 3); // C->D
graph.display();
return 0;
}
동일하게 아래의 그래프를 인접 리스트로 구현한 것이다.
1.7 인접 행렬 vs 인접 리스트
마치 어떻게 활용될지에 따라 ArrayList와 LinkedList를 고민하는 것처럼, 이 또한 상황에 따라 알맞은 방법을 선택해야 한다.
만약 10억 개의 노드가 있고 각 노드가 2개씩의 간선만 있는 상황이다. 인접행렬로 구현한 그래프에서는 한 정점의 차수를 구할 때 10억번의 연산을 수행할 것이다. 반면, 인접리스트로 구현한 그래프에서는 2번의 연산만 수행하면 된다.
정점의 개수에 비해 간선의 개수가 매우 적은 희소 그래프(sparse graph)에서는 인접리스트가 유리할 수 있고, 모든 정점간에 간선이 존재하는 완전 그래프(Complete Graph)에서는 인접행렬이 유리할 수 있다.
그래프에서 주로 어떤 연산이 수행되는지도 매우 중요하게 고려되어야 할 것이다.
답은 없다. 상황에 따라 최선의 방법을 선택하는 것이 프로그래머의 덕목이다.
2. 그래프 활용
2.1 깊이우선 탐색 (DFS)
깊이우선 탐색(DFS: Depth First Search)이란 특정 노드에서 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게(끝까지) 탐색하는 방법을 뜻한다.
아래 그래프를 깊이우선 탐색해보자
인접행렬을 이용한 DFS 구현 (C++)
// DFS 탐색 기능이 추가된 그래프
class SearchAdjMatGraph : public AdjMatGraph{
private:
bool visited[MAX_VTXS]; // 방문 기록
public:
// 모든 정점의 방문기록을 false로 초기화
void resetVisited(){
for(int i=0; i<size; i++){
visited[i] = false;
}
}
// 깊이우선탐색 (순환)
void dfs(int v){
resetVisited();
dfsRecur(v);
}
void dfsRecur(int v){
visited[v] = true; // 현재 vertex 방문처리
cout << getVertex(v) << " ";
for(int n=0; n<size; n++){
if(isLinked(v, n) && visited[n]==false){
dfsRecur(n);
}
}
}
};
int main(){
SearchAdjMatGraph graph;
// 정점 삽입 (A, B, C, D)
graph.insertVertex('A'); // 0
graph.insertVertex('B'); // 1
graph.insertVertex('C'); // 2
graph.insertVertex('D'); // 3
graph.insertVertex('E'); // 4
graph.insertVertex('F'); // 5
graph.insertVertex('G'); // 6
graph.insertVertex('H'); // 7
// 간선 삽입
graph.insertEdge(0, 1); // A->B
graph.insertEdge(0, 2); // A->C
graph.insertEdge(1, 3); // B->D
graph.insertEdge(2, 3); // C->D
graph.insertEdge(2, 4); // C->E
graph.insertEdge(3, 5); // D->F
graph.insertEdge(4, 6); // E->G
graph.insertEdge(4, 7); // E->H
graph.insertEdge(6, 7); // G->H
cout << "== Display Graph == " << endl;
graph.display();
cout << "-DFS => ";
graph.dfs(0);
return 0;
}
인접리스트를 이용한 DFS 구현 (C++)
// DFS 탐색 기능이 추가된 그래프
class SearchAdjListGraph : public AdjListGraph{
private:
bool visited[MAX_VTXS]; // 방문 기록
public:
// 모든 정점의 방문기록을 false로 초기화
void resetVisited(){
for(int i=0; i<size; i++){
visited[i] = false;
}
}
// 깊이우선탐색 (순환)
void dfs(int v){
resetVisited();
dfsRecur(v);
}
void dfsRecur(int v){
visited[v] = true; // 현재 vertex 방문처리
cout << getVertex(v) << " ";
// v 정점의 인접리스트를 모두 방문하며 탐색
for(Node *p=adjList[v]; p!=NULL; p=p->getLink()){
if(visited[p->getId()] == false){
dfsRecur(p->getId());
}
}
}
};
int main(){
SearchAdjListGraph graph;
// 정점 삽입 (A, B, C, D)
graph.insertVertex('A'); // 0
graph.insertVertex('B'); // 1
graph.insertVertex('C'); // 2
graph.insertVertex('D'); // 3
graph.insertVertex('E'); // 4
graph.insertVertex('F'); // 5
graph.insertVertex('G'); // 6
graph.insertVertex('H'); // 7
// 간선 삽입
graph.insertEdge(0, 1); // A->B
graph.insertEdge(0, 2); // A->C
graph.insertEdge(1, 3); // B->D
graph.insertEdge(2, 3); // C->D
graph.insertEdge(2, 4); // C->E
graph.insertEdge(3, 5); // D->F
graph.insertEdge(4, 6); // E->G
graph.insertEdge(4, 7); // E->H
graph.insertEdge(6, 7); // G->H
cout << "== Display Graph == " << endl;
graph.display();
cout << "-DFS => ";
graph.dfs(0);
return 0;
}
DFS 결과 순서가 다른 이유는 인접 리스트의 노드 순서가 역순으로 들어있기 때문이다.
※ 시간복잡도
정점의 수가 n이고 간선의 수가 e인 그래프를 인접 행렬로 구현하는 경우 DFS 시간복잡도는 O(n²) 이며, 인접 리스트로 구현하는 경우 DFS 시간복잡도는 O(n+e) 이다.
2.2 너비우선 탐색
너비우선 탐색(BFS: Breadth First Search)이란 특정 노드에서 시작하여 인접한 노드를 먼저 탐색해나가는 방법을 뜻한다.
이번에는 아래 그래프를 너비우선 탐색해보자
인접행렬을 이용한 BFS 구현 (C++)
// BFS 탐색 기능이 추가된 그래프
class SearchAdjMatGraph : public AdjMatGraph{
private:
bool visited[MAX_VTXS]; // 방문 기록
public:
// 모든 정점의 방문기록을 false로 초기화
void resetVisited(){
for(int i=0; i<size; i++){
visited[i] = false;
}
}
// 너비우선탐색 (큐 이용)
void bfs(int v){
resetVisited();
visited[v] = true; // 현재 vertex 방문처리
cout << getVertex(v) << " ";
queue<int> queue;
queue.push(v); // 시작 vertex enqueue
while(!queue.empty()){
v = queue.front();
queue.pop(); // v = queue.dequeue()
// 인접 정점 탐색
for(int n=0; n<size; n++){
if(isLinked(v, n) && visited[n]==false){
cout << getVertex(n) << " ";
visited[n] = true; // 방문 처리
queue.push(n);
}
}
}
}
};
int main(){
SearchAdjMatGraph graph;
// 정점 삽입 (A, B, C, D)
graph.insertVertex('A'); // 0
graph.insertVertex('B'); // 1
graph.insertVertex('C'); // 2
graph.insertVertex('D'); // 3
graph.insertVertex('E'); // 4
graph.insertVertex('F'); // 5
graph.insertVertex('G'); // 6
graph.insertVertex('H'); // 7
// 간선 삽입
graph.insertEdge(0, 1); // A->B
graph.insertEdge(0, 2); // A->C
graph.insertEdge(1, 3); // B->D
graph.insertEdge(2, 3); // C->D
graph.insertEdge(2, 4); // C->E
graph.insertEdge(3, 5); // D->F
graph.insertEdge(4, 6); // E->G
graph.insertEdge(4, 7); // E->H
graph.insertEdge(6, 7); // G->H
cout << "== Display Graph == " << endl;
graph.display();
cout << "-BFS => ";
graph.bfs(0);
return 0;
}
인접리스트를 이용한 BFS 구현 (C++)
// BFS 탐색 기능이 추가된 그래프
class SearchAdjListGraph : public AdjListGraph{
private:
bool visited[MAX_VTXS]; // 방문 기록
public:
// 모든 정점의 방문기록을 false로 초기화
void resetVisited(){
for(int i=0; i<size; i++){
visited[i] = false;
}
}
// 너비우선탐색 (큐 사용)
void bfs(int v){
resetVisited();
visited[v] = true; // 현재 vertex 방문처리
cout << getVertex(v) << " ";
queue<int> queue;
queue.push(v); // 시작 vertex enqueue
while(!queue.empty()){
v = queue.front();
queue.pop(); // v = queue.dequeue()
// 인접 정점 탐색
for(Node *n=adjList[v]; n!=NULL; n=n->getLink()){
int nId = n->getId(); // 인접 노드의 정점 id
if(!visited[nId]){
cout << getVertex(nId) << " ";
visited[nId] = true; // 방문 처리
queue.push(nId);
}
}
}
}
};
int main(){
SearchAdjListGraph graph;
// 정점 삽입 (A, B, C, D)
graph.insertVertex('A'); // 0
graph.insertVertex('B'); // 1
graph.insertVertex('C'); // 2
graph.insertVertex('D'); // 3
graph.insertVertex('E'); // 4
graph.insertVertex('F'); // 5
graph.insertVertex('G'); // 6
graph.insertVertex('H'); // 7
// 간선 삽입
graph.insertEdge(0, 1); // A->B
graph.insertEdge(0, 2); // A->C
graph.insertEdge(1, 3); // B->D
graph.insertEdge(2, 3); // C->D
graph.insertEdge(2, 4); // C->E
graph.insertEdge(3, 5); // D->F
graph.insertEdge(4, 6); // E->G
graph.insertEdge(4, 7); // E->H
graph.insertEdge(6, 7); // G->H
cout << "== Display Graph == " << endl;
graph.display();
cout << "-BFS => ";
graph.bfs(0);
return 0;
}
※ 시간복잡도
정점의 수가 n이고 간선의 수가 e인 그래프를 인접 행렬로 구현하는 경우 BFS 시간복잡도는 O(n²) 이며, 인접 리스트로 구현하는 경우 BFS 시간복잡도는 O(n+e) 이다.
2.3 Connected Component
Connected Component(연결 성분)이란 여러 개의 노드의 집합에서 간선으로 연결된 각각의 그래프를 의미한다.
연결 성분을 찾는 방법
- 그래프 상의 임의의 노드를 선택해 DFS 또는 BFS 탐색을 수행한다.
(방문한 노드는 같은 성분으로 labeling 한다.) - 남은 노드 중 방문하지 않은 노드를 선택하여 다시 1번을 수행한다.
- 그래프의 모든 노드가 방문처리될 때까지 1, 2번을 반복한다.
C++ 구현
/*
* 9.9
* 인접 행렬(Adjacency Matrix)과 DFS를 이용한 Connected Component (연결 성분) 탐색 프로그램 구현해보기
*/
#include <iostream>
using namespace std;
#define MAX_VTXS 256 // 최대 정점 개수
class AdjMatGraph{
protected:
int size; // 정점의 개수
char vertices[MAX_VTXS]; // 정점의 이름
int adjMat[MAX_VTXS][MAX_VTXS]; // 인접 행렬
public:
AdjMatGraph(){
reset();
}
~AdjMatGraph(){}
char getVertex(int i){
return vertices[i];
}
int getEdge(int i, int j){
return adjMat[i][j];
}
void setEdge(int i, int j, int val){
adjMat[i][j] = val;
}
// 그래프 초기화
void reset(){
for(int i=0; i<MAX_VTXS; i++){
for(int j=0; j<MAX_VTXS; j++){
setEdge(i, j, 0);
}
}
size = 0;
}
// 정점 삽입
void insertVertex(char name){
if(isFull()){
cout << "Graph vertex full error" << endl;
return;
}
vertices[size++] = name;
}
// 간선 삽입 (무방향 그래프)
void insertEdge(int u, int v){
setEdge(u, v, 1); // 가중치 그래프에서는 1이 아닌 가중치 삽입
setEdge(v, u, 1); // 방향 그래프에서는 삭제 (<u,v>만 존재)
}
// 그래프 정보 출력
void display(){
cout << "vertex size : " << size << endl;
cout << " ";
for(int i=0; i<size; i++){
cout << getVertex(i) << " ";
}
cout << endl;
for(int i=0; i<size; i++){
cout << getVertex(i) << " : ";
for(int j=0; j<size; j++){
cout << getEdge(i, j) << " ";
}
cout << endl;
}
}
// 두개의 정점이 연결되어 있는지 검사
bool isLinked(int u, int v){
return getEdge(u, v) != 0;
}
bool isEmpty(){
return size == 0;
}
bool isFull(){
return size >= MAX_VTXS;
}
};
// DFS를 이용하여 그래프의 연결성분 탐색
class ConnectedComponentGraph : public AdjMatGraph{
private:
int labelValue = 0;
int label[MAX_VTXS]; // component label;
public:
// 모든 node의 label을 0으로 초기화
void resetVisited(){
for(int i=0; i<size; i++){
label[i] = 0;
}
}
// 깊이우선탐색 (순환)
void labelDfsRecur(int v){
label[v] = labelValue;
for(int n=0; n<size; n++){
if(isLinked(v, n) && label[n]==0){
labelDfsRecur(n);
}
}
}
void findConnectedComponent(){
cout << "== Connected Component ==" << endl;
int cnt = 0; // component 개수
labelValue = 0; // labelValue 초기화
resetVisited(); // label array 초기화
for(int i=0; i<size; i++){
if(label[i]==0){ // 방문하지 않은 node의 경우
labelValue++; // label 값 증가
labelDfsRecur(i);
cnt++;
}
}
cout << "- component 개수 : " << cnt << endl;
for(int i=1; i<=labelValue; i++){
cout << " " << i << " : ";
for(int j=0; j<size; j++){
if(label[j]==i){
cout << "[" << getVertex(j) << "]";
}
}
cout << endl;
}
}
};
int main(){
// 그래프 모양
cout << "== Graph Shape ==" << endl;
cout << "A - C E - G" << endl;
cout << " \\ " << endl;
cout << "B - D - F H" << endl;
cout << endl;
// 인접 행렬 그래프
ConnectedComponentGraph graph;
cout << "== Adjacency Matrix Graph == " << endl;
// 정점 삽입 (A, B, C, D)
graph.insertVertex('A'); // 0
graph.insertVertex('B'); // 1
graph.insertVertex('C'); // 2
graph.insertVertex('D'); // 3
graph.insertVertex('E'); // 4
graph.insertVertex('F'); // 5
graph.insertVertex('G'); // 6
graph.insertVertex('H'); // 7
// 간선 삽입
graph.insertEdge(0, 2); // A->C
graph.insertEdge(1, 3); // B->D
graph.insertEdge(3, 5); // D->F
graph.insertEdge(4, 6); // E->G
graph.insertEdge(4, 7); // E->H
graph.display();
graph.findConnectedComponent();
return 0;
}
2.4 신장 트리 (Spanning Tree)
신장 트리(spanning tree)란 그래프 내의 모든 정점이 연결되어 있으면서 사이클이 없는 트리를 의미한다.
신장 트리는 그래프의 n개의 정점을 정확하게 n-1개의 간선으로 연결하게 된다.
신장 트리를 구현하기 위해서는 DFS 또는 BFS 도중에 사용된 간선들만 남겨두면 된다.
즉, 이를 그림으로 표현하면 아래와 같다.
