[자료구조]#6_그래프

 

#0. 개념

 

1. 그래프?

• [정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와 간선의 개수, 간선의 방향 유무 등에 따라서 다양한 형태로 나타납니다. 예를 들면, 간선의 방향성 유무에 따라서 비 방향성 그래프와 방향성 그래프가 존재합니다. 더불어, 간선의 연결 강도에 따라서 가중치 그래프/네트워크가 있고, 노드와 간선의 연결 유무에 따라서 부분 그래프와 완전 그래프가 존재합니다.
• [특징] : (1) 계층 구조의 부재 : 그래프는 계층 구조를 갖지 않습니다. (2) 간선의 방향성 : 그래프의 간선은 비 방향성 혹은 방향성을 갖습니다. (3) 간선의 가중치 : 그래프의 간선은 가중치를 가질 수 있습니다. (4) 순환 구조 : 그래프는 순환 구조일수도, 비 순환 구조일수도 있습니다.  
• [활용] : 그래프는 많은 분야에서 활용되는 자료구조이며, 경로 탐색, 최단 경로 탐색, 그리디 알고리즘 등에서 활용됩니다.

 

2. 비 방향성/방향성 그래프

출저: C언어를 이용한 체험 자료구조

 

Details

 

• 간선이 방향성을 갖지 않는 그래프는 비 방향성 그래프라고 하며, 반대로 간선이 방향성을 가지면 방향성 그래프라고 합니다.
• 비 방향성 그래프는 간선의 시작점과 끝점이 구분되지 않으며, 그래프를 표현할 때 간선으로 실선 혹은 점선을 사용합니다.
• 방향성 그래프는 간선의 시작점과 끝점이 구분되어 있으며, 그래프를 표현할 때 간선으로 화살표를 사용합니다.
• 각 그래프의 특징에 따라서 사용처가 저마다 다릅니다. 비 방향성 그래프는 네트워크 플로우 문제 등을 해결하기 위해 사용되며, 방향성 그래프는 최단 경로 문제 등에서 활용됩니다.

 

3. 가중치 그래프

출저: C언어를 이용한 체험 자료구조

 

Details

 

• 가중치 그래프는 간선에 연결 강도 혹은 가중치가 할당됩니다. 가중치 그래프의 간선의 가중치는 일반적으로 실수 값이며, 두 정점 사이의 거리, 비용, 시간 등의 개념을 나타내는 데 사용됩니다.
• 가중치 그래프는 크루스칼(Kruskal) 알고리즘, 벨만-포드(Bellman-Ford) 알고리즘, 그리고 다익스트라(Dijkstra) 알고리즘 등에 활용됩니다. 

 

3. 부분/완전 그래프

출저: C언어를 이용한 체험 자료구조

출저: C언어를 이용한 체험 자료구조

 

Details

 

• 부분 그래프는 노드 집합의 부분 집합과 간선 집합의 부분 집합으로 이루어진 그래프입니다. 즉, 기존의 그래프에서 일부 노드와 간선을 선택하여 만든 작은 그래프입니다.
• 완전 그래프는 그래프 내의 모든 정점이 서로 연결된 그래프입니다. 즉, 모든 정점 쌍 사이에 간선이 존재하는 그래프입니다.
• 두 그래프 종류의 차이점은 간선의 수와 연결성입니다. 부분 그래프는 기존의 그래프에서 일부 정점과 간선을 선택하여 만든 작은 그래프이기 때문에, 간선의 수와 연결성이 기존의 그래프보다 작습니다. 반면에, 완전 그래프는 모든 정점 쌍 사이에 간선이 존재하기 때문에, 간선의 수와 연결성이 최대입니다.
• 부분 그래프는 기존의 문제의 일부분만 고려하여 해결할 때 유용하게 사용됩니다. 반면에, 완전 그래프는 정점 쌍 사이의 거리, 경로, 연결성 등을 계산하는데 활용됩니다. 

 

4. 관련 용어

1. 인접 노드 : 하나의 간선에 의해 직접 연결된 노드.
2. 진입 차수 : 외부로부터 들어오는 간선의 수.
3. 진출 차수 : 외부로 향하는 간선의 수.
4. 경로 : 그래프에서 간선을 따라서 갈 수 있는 길을 노드 순서대로 나타낸 것.
5. 연결 그래프 : 경로로 연결된 노드들의 집합.

 

---

 

#1. 구현

 

1. 인접 행렬(Adjacent Matrix)

#include <iostream>
#include <vector>

using namespace std;

class Graph {
private:
    vector<vector<int>> adj; // 인접 행렬
    int n; // 노드의 개수
public:
    // 생성자
    Graph(int n) {
        this->n = n;
        adj.resize(n, vector<int>(n, 0));
    }
    
    // 간선 추가 함수
    void addEdge(int u, int v, int weight) {
        adj[u][v] = weight;
        adj[v][u] = weight;
    }
    
    // 간선 제거 함수
    void removeEdge(int u, int v) {
        adj[u][v] = 0;
        adj[v][u] = 0;
    }
    
    // 노드 추가 함수
    void addNode() {
        n++;
        adj.resize(n, vector<int>(n, 0));
    }
    
    // 노드 제거 함수
    void removeNode(int u) {
        // 해당 노드와 연결된 모든 간선을 제거
        for (int i = 0; i < n; i++) {
            adj[u][i] = 0;
            adj[i][u] = 0;
        }
        
        // 해당 노드를 삭제
        adj.erase(adj.begin() + u);
        n--;
        for (int i = 0; i < n; i++) {
            adj[i].erase(adj[i].begin() + u);
        }
    }
};

int main() {
    // 노드의 개수가 4인 그래프 생성
    Graph g(4);
    
    // 간선 추가
    g.addEdge(0, 1, 2);
    g.addEdge(1, 2, 5);
    g.addEdge(2, 3, 1);
    g.addEdge(3, 0, 4);
    
    // 노드 추가
    g.addNode();
    
    // 간선 추가
    g.addEdge(4, 2, 3);
    
    // 노드 제거
    g.removeNode(1);
    
    return 0;
}

 

출저: C언어를 이용한 체험 자료구조

 

Adjacent_Matix[From][To]

 

Details

 

• [정의] : 인접 행렬은 그래프를 표현하는 다양한 방법 중 하나입니다. 인접 행렬은 기본적으로 2차원 배열을 활용하며, row 값은 노드가 갖는 값을 의미하며, column 값은 해당 노드가  column 값을 갖는 노드와 연결되어 있는지 여부를 의미합니다. 즉, 배열에 저장된 원소는 두 노드의 연결 관계를 0과 1로 나타냅니다. 가중치 그래프를 인접 행렬을 이용해 구현할 경우 2차원 배열의 원소는 가중치를 의미하겠죠.
• [특징] : 그래프를 인접 행렬을 통해 구현하는 방법은 간단하며, 노드 간의 연결 관계를 빠르게 파악할 수 있습니다. 더불어, 가중치 그래프의 가중치를 표현하기에 적합합니다. 다만, 희소 그래프를 인접행렬을 통해 구현할 경우 메모리를 많이 사용합니다.

 

2. 인접 리스트(Adjacent List)

#include <iostream>
#include <vector>
using namespace std;

// #1. 그래프 자료구조의 총괄 구조체
typedef struct Graph {
	HeadNodes* List;
	int NodeSize;
}Graph;

// #2. 헤드 노드 구조체
typedef struct HeadNodes {
	Node* Head;
}HeadNodes;

// #3. 노드 구조체
typedef struct Node {
	int Val;
	Node* Next;
}Node;

// #4. 그래프 생성 함수
Graph* CreateGraph(int nodeSize)
{
	Graph* G = new Graph;
	G->NodeSize = nodeSize;
	G->List = new HeadNodes[nodeSize];

	for (int i = 0; i < nodeSize; i++)
	{
		G->List[i].Head = NULL;
	}

	return G;
}

void AddEdge(Graph* G, int from, int to) {
	Node* newNode = new Node;
	newNode->Val = to;
	newNode->Next = NULL;

	if (G->List[from].Head == NULL) {  // Head의 Next가 Null일 때
		G->List[from].Head = newNode;
	}
	else {  // Head의 Next가 이미 존재할 때
		Node* cur = G->List[from].Head;
		while (cur->Next != NULL) {
			cur = cur->Next;
		}
		cur->Next = newNode;
	}
}

void RemoveEdge(Graph* G, int from, int to) {
	Node* cur = G->List[from].Head;
	Node* prev = NULL;

	// 삭제할 간선을 찾는 과정
	while (cur != NULL) {
		if (cur->Val == to) {
			break;
		}
		prev = cur;
		cur = cur->Next;
	}

	// 삭제할 간선이 없는 경우
	if (cur == NULL) {
		cout << "Cannot remove edge (" << from << ", " << to << "). Edge does not exist." << endl;
		return;
	}

	// 삭제할 간선이 Head일 경우
	if (prev == NULL) {
		G->List[from].Head = cur->Next;
	}
	else { // 삭제할 간선이 Head가 아닐 경우
		prev->Next = cur->Next;
	}

	delete cur;
}

 

Details

 

1. Graph : 인접 리스트를 총괄하는 구조체, 인접 리스트를 데이터 필드로 갖습니다. 
2. HeadNodes : 인접 리스트의 첫 번째 항목을 가리키는 포인터를 데이터 필드로 갖습니다.
3. Node : 인접 리스트를 구성하는 노드
4. Create 함수 : Head Nodes를 노드 사이즈만큼 생성하고, HeadNodes 구조체가 담고 있는 데이터 필드 Node를 Null 값으로 초기화합니다.
5. AddEdge 함수 : 간선 추가 함수는 From(출발 노드)를 To(도착 노드)로 연결하는 함수입니다. 따라서, HeadNodes 중 From 노드를 찾고, 리스트의 마지막에 To(도착 노드)를 연결해 줍니다.
6. RemoveEdge 함수 : 간선 제거 함수는 From(출발 노드)를 HeadNodes에서 찾고, 다시, 도착 노드를 Next멤버로 갖는 노드를 탐색해 해당 노드를 제거하고 간선 또한 제거합니다.

 

---

 

#2. 탐색

 

1. 깊이 우선 탐색(DFS)

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

struct Graph
{
	vector<vector<int>> adjMatrix;
	int NodeSize;
};

// #1. 재귀 호출을 활용한 깊이 우선 탐색 알고리즘
void DFS(Graph& graph)
{
	vector<bool> visited(graph.NodeSize, false);
	
	for (int i = 0; i < graph.NodeSize; i++) {
		if (!visited[i])
			DFSRecur(i, visited, graph);
	}

}

void DFSRecur(int node, vector<bool>& visited, const Graph& graph)
{
	visited[node] = true;

	for (int i = 0; i < graph.NodeSize; i++)
	{
		if (graph.adjMatrix[node][i] != 0 && !visited[i])
		{
			DFSRecur(i, visited, graph);
		}
	}
}

// #2. 스택을 활용한 깊이 우선 탐색
void DFS(Graph& graph, int start)
{
	stack<int> s;
	vector<bool> visited(graph.NodeSize; false);

	s.push(start);

	while (!s.empty())
	{
		int cur = s.top();
		s.pop();
		
            if(!visited[cur])
            {
                visited[cur] = true;
           	 cout << "Current Node : " << cur << '\n';
            }

            for (int next = 0; next < graph.NodeSize; next++)
            {
                if (graph.adjMatrix[cur][next] != 0 && !visited[next])
                {
                    s.push(next);
                }
            }
	}

}

 

Details

 

• [정의] : 깊이 우선 탐색은 그래프의 모든 노드를 탐색하는 방법 중 하나입니다.
• [동작 방식] : 깊이 우선 탐색은 시작 노드부터 출발해 노드를 추가해 더 이상 확장 할 수 없는 단말 노드까지 탐색을 수행하는 방법입니다. 이때, 탐색 과정에서 단말 노드에 다다르면 백트래킹하여 다음 노드에서 같은 작업을 수행합니다.
• [특징] : 깊이 우선 탐색은 재귀 함수 혹은 스택을 사용해 구현할 수 있습니다.
• [활용] : 깊이 우선 탐색은 경로 찾기, 연결 여부, 위상 정렬, 그리고 사이클 검사에 활용됩니다.

 

[BOJ알고리즘, C++]#15649_N과 M(1), 깊이 우선 탐색

 

[BOJ알고리즘, C++]#15649 N과 M(1), 깊이 정렬, DFS

 

[BOJ알고리즘, C++]#9663_N-Queen 문제, 백 트래킹

 

[BOJ알고리즘, C++]#14889_스타트와 링크, DFS, 깊이 우선 탐색

 

2. 너비 우선 탐색(BFS)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Graph
{
	vector<vector<int>> adjMatrix;
	int NodeSize;
};

void BFS(Graph& graph, int start)
{

	queue<int> q;
	vector<bool> visited(graph.NodeSize, false);

	q.push(start);
	visited[start] = true;

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		cout << cur << " ";

		for (int neighbor = 0; neighbor < graph.nodeSize; neighbor++)
		{
			if (graph.adjMatrix[cur][neighbor] != 0 && !visited[neighbor])
			{
				q.push(neighbor);
				visited[neighbor] = true;
			}
		}
	}

}

 

Details

 

• [정의] : 너비 우선 탐색(BFS)은 그래프의 모든 노드를 탐색하는 방법 중 하나입니다.
• [동작 방식] : 너비 우선 탐색은 현재 상태에서 가장 인접한 정점들을 순차적으로 탐색하는 방법입니다. 너비 우선 탐색은 큐를 활용해 구현할 수 있습니다.
• [활용] : 너비 우선 탐색은 최단 경로 탐색을 위해 사용됩니다.

 

---

 

#3. 정렬

 

1. 위상 정렬(DAG 정렬)

• [정의] : 위상 정렬은 비순환 유향 그래프(DAG)에서 각 정점들의 선행 관계를 유지하며 정점을 나열하는 방법입니다.
• [특징] : 그래프에 사이클이 존재하면 두 정점 u, v 모두 먼저 오거나 뒤에 올 수 있기 때문에 순서를 정할 수 없기 때문에 순환 그래프는 위상 정렬을 적용할 수 없습니다. 일반적으로, 위상 정렬은 DFS(깊이 우선 정렬)을 기반으로 합니다. 따라서, 스택을 활용합니다.

 

2. DFS(재귀 호출)를 활용한 위상 정렬

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

struct Graph
{
	int NodeSize;
	vector<vector<int>> adjMatrix;
};


void TopologicalSort(Graph& graph)
{
	
	vector<bool> visited(graph.NodeSize, false);
	stack<int> res;

	for (int i = 0; i < graph.NodeSize; i++)
	{
		if (!visited[i])
			DFS(graph, i, visited, res);
	}

	while (!res.empty())
	{
		int cur = res.top();
		cout << cur << '\n';
		res.pop();
	}

}

void DFS(Graph& graph, int node, vector<bool>& visited, stack<int>& s)
{
	visited[node] = true;

	for (const auto& neighbor : graph.adjMatrix[node])
	{
		if (!visited[neighbor])
		{
			DFS(graph, neighbor, visited, s);
		}
	}

	s.push(node);

}

int main()
{
	Graph graph;
	int numNodes, numEdges;

	cout << "노드의 개수를 입력하세요: ";
	cin >> numNodes;
	graph.NodeSize = numNodes;

	cout << "간선의 개수를 입력하세요: ";
	cin >> numEdges;

	graph.adjMatrix.resize(numNodes);
	cout << "간선 정보를 입력하세요.\n";
	for (int i = 0; i < numEdges; i++)
	{
		int from, to;
		cout << "출발 노드와 도착 노드를 입력하세요: ";
		cin >> from >> to;
		graph.adjMatrix[from].push_back(to);
	}

	cout << "위상 정렬 결과:\n";
	TopologicalSort(graph);

	return 0;
}

 

Details

 

1. CreateGraph 함수 : 먼저, 총 6개의 정점을 갖는 인접 리스트를 구현합니다.
2. AddEdge 함수 : 두 정점 사이에 간선을 추가합니다.
3. TopologicalSortDFS 함수 : DFS(깊이 우선 정렬) 알고리즘은 방문 여부 확인과 재귀호출 혹은 스택을 활용해 구현합니다. TopologicalSortDFS() 함수는 DFS를 활용하여 위상 정렬을  구현하는 함수입니다. DFS는 재귀 호출 혹은 스택 중 한 가지 방법으로 구현 가능하지만, 정점들의 선행 관계를 출력하기 위해 스택 자료구조를 활용했습니다. 

 

3. 진입 차수 위상 정렬

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Graph
{
	int NodeSize;
	vector<int> InDegree;
	vector<vector<int>> adjMatrix;
};

void TopologicalSort(Graph& graph)
{
	queue<int> q;
	// #1. 그래프 내 정점들 중 진입 차수가 이미 0인 정점들을 큐에 삽입합니다.
	for (int i = 0; i < graph.NodeSize; i++)
	{
		if (graph.InDegree[i] == 0)
			q.push(i);
	}

	// #2. 큐를 순회하며, 방문한 정점의 진입 차수를 1 감소하고, 0이 되면 큐에 삽입합니다.
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		cout << cur << '\n';
		
		for (const auto& neighbor : graph.adjMatrix[cur])
		{
			graph.InDegree[neighbor]--;
			if (graph.InDegree[neighbor] == 0)
				q.push(neighbor);
		}
	}

}

int main()
{

	Graph graph;
	graph.NodeSize = 6;
	graph.adjMatrix.resize(graph.NodeSize);
	graph.InDegree.resize(graph.NodeSize, 0);

	// 그래프 초기화
	graph.adjMatrix[0].push_back(1);
	graph.adjMatrix[0].push_back(2);
	graph.adjMatrix[1].push_back(3);
	graph.adjMatrix[2].push_back(3);
	graph.adjMatrix[2].push_back(4);
	graph.adjMatrix[3].push_back(5);
	graph.adjMatrix[4].push_back(5);
	graph.InDegree[1]++;
	graph.InDegree[2]++;
	graph.InDegree[3]++;
	graph.InDegree[4]++;
	graph.InDegree[5]++;

	TopologicalSort(graph);

	return 0;

}

 

Details

 

• [동작 방식]
  1. "진입 차수(In-Degree)"는 해당 정점으로 들어오는 간선의 개수를 의미합니다. 진입 차수를 활용하는 BFS는 진입 차수를 기반으로 작업의 선후 관계를 유지합니다. 진입 차수가 0인 정점을 선행 작업이 완료된 정점으로 처리합니다.
  2. 진입 차수를 활용한 위상 정렬은 먼저 진입 차수가 0인 정점들을 탐색해 큐에 Push 하는 작업이 필요합니다.
  3. 진입 차수를 활용한 위상 정렬은 해당 큐에 가장 먼저 들어온 정점을 꺼내 인접한 정점들을 큐에 다시 Push 하는 작업들을 반복합니다. 

 

4. DFS를 통한 그래프의 사이클 검사(유향 그래프, 양수 가중치만 있을 경우)

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct Graph
{
	int NodeSize;
	vector<int> InDegree;
	vector<vector<int>> adjMatrix;
};

bool DFS(Graph& graph, vector<bool>& visited, vector<bool>& recStack, int cur)
{
	if (!visited[cur])
	{
		visited[cur] = true;
		recStack[cur] = true;

		for (int i = 0; i < graph.NodeSize; i++)
		{
			if (graph.adjMatrix[cur][i] != 0)
			{
        	 	// #1. 현재 탐색 경로에서 해당 정점을 방문하지 않았다면, DFS를 계속 진행
				if (!visited[i] && DFS(graph, visited, recStack, i))
				{
					return true;
				}
  		        // #2. 현재 탐색 경로에서 이미 해당 정점을 방문한 적이 있다면, 순환 구조가 형성되어 있습니다.
				else if (recStack[i])
					return true;
			}
		}
	}
     // #3. DFS를 모두 수행하고, 현재 탐색 경로에 존재하는 정점 목록에서 현재 정점을 제외해줍니다.
	recStack[cur] = false;

	return false;
}

void CheckCycle(Graph& graph)
{
	vector<bool> visited(graph.NodeSize, false);
	vector<bool> recStack(graph.NodeSize, false);

    for (int i = 0; i < graph.NodeSize; i++)
    {
        if(!visited[i] && DFS(graph, visited, recStack, i)) {
            cout << "Yes" << endl;
            return;
        }
    }

	cout << "No" << endl;

}

 

Details

 

• [개념] : 위상 정렬 알고리즘은 사이클이 없는 오직 비순환 유향 그래프에 적용 가능한 알고리즘입니다. 그렇다면, 어떤 그래프가 순환 그래프이고, 혹은 비 순환 그래프일까? 그래프의 순환 여부를 확인할 수 있는 대표적인 방법으로 DFS가 있습니다. 현재 정점을 기준으로 DFS를 재귀적으로 수행하고, 탐색 경로에서 이미 방문한 정점을 한번 더 방문하게 되면 해당 그래프는 '순환' 구조를 형성하고 있다는 뜻입니다. 
• [동작 방식]
  
  1. 먼저, 순환 여부를 체크하는 DFS는 두 가지 목록을 체크합니다. - 방문 여부 + 현재 탐색 경로에서 방문 여부
  2. 첫 번째, 방문 여부는 현재 정점에 대해서 DFS를 수행할 것인지 결정합니다.
  3. 두 번째, 현재 탐색 경로에서 현재 정점을 이미 방문했는지 체크합니다.
  4. 결과적으로, 방문 여부 목록을 통해 DFS 수행 여부를 결정하고, 방문하지 않았다면 DFS를 재귀적으로 수행하며 탐색 경로에서 방문한 정점들을 체크하고, 이 과정에서 이미 탐색 경로에 존재했던 정점을 다시 만난다면 그래프 내 순환 구조가 확인되어 탐색을 종료합니다. 

 

---

 

#4. 신장 트리

 

1. 신장 트리(Spanning Tree)

• [정의] : '신장 트리'는 그래프 내 모든 정점을 최소한의 간선으로 순환 구조 없이 연결하는 부분 그래프를 의미합니다.
• [특징] : 신장 트리는 결과적으로 최소한의 간선을 활용해 그래프의 모든 정점을 연결하는 그래프를 의미합니다. 이러한 신장 트리는 그래프의 깊이 우선 탐색 혹은 너비 우선 탐색을 통해 구할 수 있습니다.
• [방법] : 신장 트리를 구하는 방법은 크게 두 가지로 하나는 "DFS" 그리고 다른 하나는 역시나 "BFS"입니다. DFS를 통해 생성된 신장 트리를 깊이 우선 신장 트리, BFS를 통해 생성된 신장 트리를 너비 우선 신장트리라고 합니다. DFS와 BFS는 한번 방문한 노드는 방문 여부를 기억해 다시 방문하지 않기 때문에, 사이클을 형성하지 않습니다!

 

2. 깊이 우선 신장 트리

#include <iostream>
#include <vector>

using namespace std;

// #0. 인접 리스트
struct Graph {
    struct HeadNodes* List;
    int NodeSize;
};

struct HeadNodes {
    struct Node* Head;
};

struct Node {
    int Val;
    int InDegree;
    struct Node* Next;
};

// #1. DFS 함수
void dfs(struct Node* node, bool* visited, struct Graph* graph) {
    visited[node->Val] = true;
    cout << node->Val << endl;

    for (struct Node* neighbor = node->Next; neighbor != NULL; neighbor = neighbor->Next) {
        if (!visited[neighbor->Val]) {
            dfs(neighbor, visited, graph);
        }
    }
}

// #2. 신장 트리 생성 함수
void spanningTree(struct Graph* graph) {
    bool* visited = new bool[graph->NodeSize];
    for (int i = 0; i < graph->NodeSize; i++) {
        visited[i] = false;
    }

    for (int i = 0; i < graph->NodeSize; i++) {
        if (!visited[i]) {
            dfs(graph->List[i].Head, visited, graph);
        }
    }
}

 

3. 너비 우선 신장 트리

#include <queue>
#include <iostream>

// #0. 인접 리스트
struct Graph {
    struct HeadNodes* List;
    int NodeSize;
};

struct HeadNodes {
    struct Node* Head;
};

struct Node {
    int Val;
    int InDegree;
    struct Node* Next;
};

void bfs(struct Node* node, bool* visited, struct Graph* graph) {
    std::queue<struct Node*> q;
    q.push(node);
    visited[node->Val] = true;

    while (!q.empty()) {
        struct Node* currNode = q.front();
        q.pop();
        std::cout << currNode->Val << endl;

        for (struct Node* neighbor = currNode->Next; neighbor != NULL; neighbor = neighbor->Next) {
            if (!visited[neighbor->Val]) {
                visited[neighbor->Val] = true;
                q.push(neighbor);
            }
        }
    }
}

void spanningTree(struct Graph* graph) {
    bool* visited = new bool[graph->NodeSize];
    for (int i = 0; i < graph->NodeSize; i++) {
        visited[i] = false;
    }

    for (int i = 0; i < graph->NodeSize; i++) {
        if (!visited[i]) {
            bfs(graph->List[i].Head, visited, graph);
        }
    }
}

 

Details

 

• 기존의 DFS와 BFS 알고리즘의 형식과 거의 동일합니다. 현재 노드가 갖는 값이 무엇인지 출력하는 코드만 추가됩니다.

 

---

 

#5. 최소 신장 트리

 

1. 최소 신장 트리

최소 신장 트리는 가중치 그래프에서 간선들이 갖는 가중치의 합이 최소가 되는 신장 트리를 의미합니다. 대표적인 최소 신장 트리 알고리즘으로 Kruskal 알고리즘, Prim 알고리즘, 그리고 Sollin 알고리즘이 있습니다.

 

2. Union-Find 알고리즘

 

2-1. 개념

Union-Find 알고리즘은 서로소 관계의 집합(Disjoint Set) 들을 찾거나, 두 집합들을 하나의 합집합으로 구성하는 알고리즘입니다. 이때, 서로소 집합들이란, 서로 상호 배타적이며 중복 값이 존재하지 않는 서로 다른 집합을 의미합니다. 정리하면, Union-Find 알고리즘을 통해 우리는 두 집합 혹은 트리 간 서로소(상호 배타적) 여부를 체크하거나, 두 집합의 대표 원소 혹은 루트 노드를 찾아 하나로 합치는 작업을 수행할 때 활용할 수 있습니다.

 

2-2. 특징

1. Union(x, y) 연산은 x와 y가 속한 두 집합의 합집합을 반환합니다.
2. Find(x) 연산은 x가 속한 집합의 대표 원소, 즉 x가 속한 트리의 루트 노드를 반환합니다.

일반적인 트리 자료구조는 자신의 자식을 가리키지만, Union-Find 알고리즘에서 활용하는 트리 자료구조는 자신의 부모 노드를 가리킵니다.

 

2-3. Union-Find의 최적화 기법

Union-Find 알고리즘을 최적화하는 두 가지 추가적인 기법들이 존재합니다- Union-by-rank, Path-Compression

// #1. Find 알고리즘, Path-Compression 최적화 기법 적용
int Find(int x, vector<int>& parent)
{
	if (parent[x] != x)
	{
		parent[x] = Find(parent[x], parent);
	}

	return parent[x];
}

// #2. Union 알고리즘, Union-by-Rank 최적화 기법 적용
void Union(int rootX, int rootY, vector<int>& parent, vector<int>& rank)
{

	if (rank[rootX] > rank[rootY])
	{
		parent[rootY] = rootX;
	}
	else if (rank[rootX] < rank[rootY])
	{
		parent[rootX] = rootY;
	}
	else
	{
		parent[rootX] = rootY;
		rank[rootY]++;
	}

}

 

Details

 

1. Union-by-rank 기법 : Union-Find 알고리즘에서 활용하는 Union-by-rank 기법은 각 노드/원소가 속한 트리의 높이 정보를 기억하는 것이 핵심입니다. 특히, Union-Find 알고리즘에서 Union 연산에 활용되는 Union-by-rank 최적화 기법은 Find 연산을 통해 구한 서로 다른 트리의 루트 노드 중 높이가 더 낮은 노드를 높이가 더 높은 노드의 자식 노드로 설정합니다. Union 연산은 많이 수행할수록 트리의 깊이가 증가해 Find() 연산의 속도를 저하시킵니다. 따라서, Union() 연산 내 Union-by-rank 최적화 기법을 차용해 트리의 높이를 최대한 작게 유지함으로써 연산 시간을 효과적으로 줄일 수 있습니다!

2. Path Compression 기법 : Union-Find 알고리즘에서 활용되는 Path Compression 기법은 트리(집합)에 속한 전체 노드의 부모 노드를 해당 트리의 루트 노드로 갱신하는 것이 핵심입니다. 특히, Union-Find 알고리즘에서 Find 연산에 활용되는 Path Compression 최적화 기법은 재귀 호출의 백트래킹 과정에서 경로상의 모든 노드의 부모 노드를 최초 부모 노드(루트 노드)로 갱신하고 있습니다. 결과적으로, Path Compression 최적화 기법을 Union-Find 알고리즘의 Find 연산에 적용해 어느 한 노드에 대한 Find 연산의 최초 호출 시 방문하는 모든 노드의 부모 노드를 루트 노드로 갱신하여 다음 호출 시 재귀 호출 횟수가 한 번으로 단축되어 트리 높이를 단축시키는 효과를 보여줍니다.

 

 

4. 크루스칼 알고리즘(Kruskal)

 

4-1. 개념

Kruskal 알고리즘은 최소 신장 트리(MST)를 구현하는 알고리즘 중 하나로, 우리가 잘 알고 있는 그리디 알고리즘(Greedy Algorithm)을 활용합니다. Kruskal 알고리즘은 무방향 가중치 그래프의 간선들을 가중치를 기준으로 오름차순 정렬하여 가장 작은 가중치를 갖는 간선부터 선택하며 트리를 구성하는 알고리즘입니다. Kruskal 알고리즘의 성능은 간선의 수가 e일 때, O(e long e)입니다. 반면, 정점의 개수가 n이고, 간선의 수가 정점의 수보다 많을 때 Kruskal 알고리즘의 성능이 최악의 경우가 되어, O(e log n)입니다.

 

4-2. 동작 방식

1. 간선 목록의 가중치 기준 오름차순 정렬
2. 간선 목록 순회, 시작 정점과 도착 정점에 대한 Find 연산 수행.
3. 시작 정점과 도착 정점이 속해 있는 집합이 서로소 관계일 경우, Union 연산 수행.
4. 해당 간선을 최소 신장 트리에 추가해줍니다.

 

4-3. 코드

#include <iostream
#include <vector>
#include <algorithm>
using namespace std;

// Graph 구조체
struct Graph
{
	int NodeSize;
	vector<int> InDegree;
	vector<vector<int>> adjMatrix;
};

// Edge 구조체
struct Edge
{
	int from, weight, to;
	Edge(int from, int to, int weight)
	{
		this->from = from;
		this->to = to;
		this->weight = weight;
	}

	bool operator<(const Edge& RightEdge)
	{
		return weight < RightEdge.weight;
	}
};

int Find(int x, vector<int>& parent)
{
	if (parent[x] != x)
	{
		parent[x] = Find(parent[x], parent);
	}

	return parent[x];
}

void Union(int rootX, int rootY, vector<int>& parent, vector<int>& rank)
{

	if (rank[rootX] > rank[rootY])
	{
		parent[rootY] = rootX;
	}
	else if (rank[rootX] < rank[rootY])
	{
		parent[rootX] = rootY;
	}
	else
	{
		parent[rootX] = rootY;
		rank[rootY]++;
	}

}

vector<Edge> Kruskal(Graph& graph)
{
	
	vector<int> parent(graph.NodeSize);
	for (int i = 0; i < graph.NodeSize; i++)
	{
		parent[i] = i;
	}

	vector<int> rank(graph.NodeSize, 0);

	vector<Edge> edges;
	for (int i = 0; i < graph.NodeSize; i++)
	{
		for (const auto neighbor : graph.adjMatrix[i])
		{
			edges.push_back(Edge(i, neighbor, graph.adjMatrix[i][neighbor]));
		}
	}

	sort(begin(edges), end(edges));

	vector<Edge> MST;

	for (const auto edge : edges)
	{
		int rootX = Find(edge.from, parent);
		int rootY = Find(edge.to, parent);

		if (rootX != rootY)
		{
			MST.push_back(edge);
			Union(rootX, rootY, parent, rank);
		}
	}

	return MST;

}

 

5. 프림 알고리즘(Prim Algorithm)

 

5-1. 개념

Prim 알고리즘은 임의의 정점에서 시작해 인접 노드들 중 최소 가중치를 갖는 간선으로 연결된 정점을 선택하며 트리를 확장하고, 최종적으로 최소 신장 트리를 완성합니다. Prim 알고리즘의 가장 큰 특징은 "우선순위 큐"와 "인접 정점 순회"입니다.

 

5-2. 성능

Prim 알고리즘의 평균 시간 복잡도는 간선의 개수를 E, 그리고 노드 개수가 n일 때 O(E log n)
입니다. Prim 알고리즘은 우선 순위 큐를 활용해 각 정점을 방문하는 시간은 O(log n)이며, 해당 정점과 연결된 모든 간선 E을 검사합니다. 최종적으로, Prim 알고리즘의 평균 시간 복잡도는 O(E log n)이 됩니다. Prim 알고리즘은 해당 그래프가 완전 그래프(모든 정점들이 서로 연결되어 있는 그래프) 일 경우 O(n²)의 최악 시간 복잡도
를 갖습니다. 예를 들면, 10개의 정점들이 서로 연결되어 있는 완전 그래프는 정점 당 9개의 간선을 갖고, 총 90개의 간선을 갖습니다. 각 정점 당 검사해야 할 간선의 개수가 크게 늘어나 알고리즘의 수행 속도가 느려집니다.

 

5-3. 크루스칼 vs 프림

간선 관점에서 운용되는 Kruskal 알고리즘과 반대로, Prim 알고리즘은 노드 관점으로 이루어집니다. 따라서, 그래프의 간선의 개수가 비교적 많을 경우 Kruskal 알고리즘을 활용하는 것이 더 효율적입니다! 반대로, 시작 정점을 정해 최소 신장 트리를 구성할 경우 프림 알고리즘이 더 효율적입니다. 크루스칼 - 간선 / 프림 - 정점

 

5-4. 동작 방식

1. pair< 가중치, 정점 > 형식을 가중치 기준 최소 힙을 구성하는 우선순위 큐
2. 우선순위 큐의 루트 노드를 꺼내어 정점의 인접 정점을 탐색
3. 아직 방문하지 않은 인접 정점을 가중치와 함께 pair 형식으로 묶어 우선순위 큐에 삽입
4. 최소 신장 트리 목록에 모든 정점이 추가될 때 까지 위 과정을 반복합니다.

 

5-5. 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// #0. 그래프
struct Graph
{
	int NodeSize;
	vector<int> InDegree;
	vector<vector<int>> adjMatrix;
};

// #1. 간선
struct Edge
{
	int from, to, weight;
	Edge(int from, int to, int weight)
	{
		this->from = from;
		this->to = to;
		this->weight = weight;
	}

	bool operator<(const Edge& RightEdge)
	{
		return weight < RightEdge.weight;
	}
};

// #2. Prim 알고리즘
vector<Edge> Prim(Graph& graph, int start)
{
	vector<bool> visited(graph.NodeSize, false);
    // #3. 우선 순위 큐
	priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
	vector<Edge> MST;

	visited[start] = true;
	
	for (const auto& next : graph.adjMatrix[start])
	{
		pq.push(Edge(start, next, graph.adjMatrix[start][next]));
	}

	while (!pq.empty())
	{
		Edge CurEdge = pq.top();
		pq.pop();

		int to = CurEdge.to;
		int weight = CurEdge.weight;

		if (visited[to] == true)
			continue;

		MST.push_back(CurEdge);
		visited[to] = true;

		for (const auto& neighbor : graph.adjMatrix[to])
		{
			pq.push(Edge(to, neighbor, graph.adjMatrix[to][neighbor]));
		}
	}

	return MST;

}


int main()
{

	int numVertices = 5; // 정점의 개수
	Graph graph;
	graph.NodeSize = 5;

	// 그래프의 간선 정보를 추가
	graph.adjMatrix[0][1] = 2; // 0과 1 사이의 간선 (가중치 2)
	graph.adjMatrix[0][3] = 6; // 0과 3 사이의 간선 (가중치 6)
	graph.adjMatrix[1][0] = 2;
	graph.adjMatrix[1][2] = 3; // 1과 2 사이의 간선 (가중치 3)
	graph.adjMatrix[1][3] = 8; // 1과 3 사이의 간선 (가중치 8)
	graph.adjMatrix[1][4] = 5; // 1과 4 사이의 간선 (가중치 5)
	graph.adjMatrix[2][1] = 3;
	graph.adjMatrix[2][4] = 7; // 2와 4 사이의 간선 (가중치 7)
	graph.adjMatrix[3][0] = 6;
	graph.adjMatrix[3][1] = 8;
	graph.adjMatrix[3][4] = 9; // 3과 4 사이의 간선 (가중치 9)
	graph.adjMatrix[4][1] = 5;
	graph.adjMatrix[4][2] = 7;
	graph.adjMatrix[4][3] = 9;

	vector<Edge> MST = Prim(graph, 0); // 시작 정점을 0으로 설정하여 최소 신장 트리 구함

	// 최소 신장 트리 출력
	for (const auto& edge : MST) {
		cout << edge.to << " ";
	}

	return 0;

}

 

6. Sollin 알고리즘

 

6-1. 개념

Sollin 알고리즘은 최소 신장 트리(MST)를 구하는 알고리즘 중 하나로, 컴포넌트(집합) 중심의 그리디 알고리즘입니다. Sollin 알고리즘은 '간선 목록'을 순회하며 각각 시작 노드와 도착 노드가 속한 집합의 최소 가중치 간선을 찾습니다. 그리고, 각 집합의 최소 가중치 간선들의 시작 노드와 도착 노드의 집합을 하나로 합치고, 최소 신장 트리 목록에 해당 간선을 추가해주고, 총 집합의 수를 -1 차감합니다.

 

6-2. 성능

Sollin 알고리즘의 평균 시간 복잡도는 간선의 개수를 E, 그리고 정점의 개수를 V일 때, O(ElogV) 입니다. 그래프의 간선을 가중치 순으로 정렬할 때 O(ElogE)의 시간이 소요되고, Union-Find 알고리즘을 통해 간선을 추가하고 컴포넌트들 관리하는 작업에 O(ElogV)의 시간이 소요되기 때문입니다. 반면에, Sollin 알고리즘의 최악 시간 복잡도는 O(E² log V)입니다. 최소 가중치를 갖는 간선을 찾는 과정에서 모든 간선을 검사해야 하는 알고리즘의 특성상 간선의 수에 비례하여 알고리즘의 수행 시간이 증가합니다.

 

6-3. Kruskal vs Sollin 

[병렬 처리] : Sollin 알고리즘은 Kruskal 알고리즘과 같이 Union-Find 알고리즘을 활용합니다. 하지만, Sollin 알고리즘은 병렬 처리를 통해 알고리즘의 성능을 향상할 수 있어 병렬 처리가 가능한 환경에서 효과적으로 사용할 수 있습니다.

[간선 중심 vs 집합 중심] : Kruskal 알고리즘은 간선을 중심의 알고리즘입니다. 그래프의 간선들을 가중치 기준 오름차순으로 정렬하여, 이들의 사이클 여부를 체크하고 최소 신장 트리에 추가합니다. 하지만, Sollin 알고리즘은 컴포넌트/집합 중심 알고리즘입니다. Sollin 알고리즘은 그래프의 컴포넌트들을 순회하며 최소 가중치를 갖는 간선들을 찾아 목록을 작성합니다. 그리고, 이들의 사이클 여부를 판단해 최소 신장 트리에 추가합니다.

 

6-4. 동작 방식

1. 각 정점을 하나의 컴포넌트로 초기화
2. 간선 목록 순회하며 시작 정점과 도착 정점의 집합의 최소 가중치 간선 찾기
3. 각 집합의 최소 가중치 간선에서 두 집합의 서로소 관계 확인 및 하나로 합치기
4. 해당 간선을 최소 신장 트리 목록에 추가하고, 총 집합 수 -1 차감
5. 2~4번 작업을 하나의 집합이 남을 때까지 반복, 최종적으로 최소 신장 트리 구성

 

6-5. 코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// #1. 간선 구조체
struct Edge {
	int src, dest, weight;
};

// #2. Find 연산
int find(vector<int>& parent, int i) {
	if (parent[i] == i)
		return i;
	return parent[i] = find(parent, parent[i]);
}
// #3. Union 연산 
void Union(vector<int>& parent, vector<int>& rank, int x, int y) {
	int rootX = find(parent, x);
	int rootY = find(parent, y);

	if (rank[rootX] < rank[rootY])
		parent[rootX] = rootY;
	else if (rank[rootX] > rank[rootY])
		parent[rootY] = rootX;
	else {
		parent[rootY] = rootX;
		rank[rootX]++;
	}
}

void sollin(vector<Edge>& edges, int N, int M) {
	// #1.parent 목록, rank 목록 : Union-Find의 최적화,
	vector<int> parent(N + 1), cheapest(N + 1), rank(N + 1, 0);

	// #2. 총 컴포넌트 수, MST의 가중치 합
	int numComponents = N, MSTweight = 0;

	// #3. 부모 목록 초기화
	for (int i = 1; i <= N; i++)
		parent[i] = i;

	// #4. 총 컴포넌트가 1개가 될 때까지 진행되는 솔린 알고리즘
	while (numComponents > 1) {
		fill(cheapest.begin(), cheapest.end(), -1);

		// 1.	간선 목록 순회하며, 각 간선의 시작 노드와 도착 노드가 속해 있는 트리/집합의 루트/대표 노드
		//		를 인덱스로, 해당 트리/집합의 간선들 중 최소 가중치를 갖는 간선을 찾는다.
		for (int i = 0; i < M; i++) {
			int set1 = find(parent, edges[i].src);
			int set2 = find(parent, edges[i].dest);

			if (set1 == set2)
				continue;
			else {
				if (cheapest[set1] == -1 || edges[cheapest[set1]].weight > edges[i].weight)
					cheapest[set1] = i;
				if (cheapest[set2] == -1 || edges[cheapest[set2]].weight > edges[i].weight)
					cheapest[set2] = i;
			}
		}

		// 2.	각 집합의 최소 가중치 목록을 순회하며, 각 최소 가중치 간선의 시작 노드와 도착노드가
		//		속한 트리/집합의 루트/대표 노드들을 구해 Union 연산하여, 두 집합을 합친다.
		for (int i = 1; i <= N; i++) {
			if (cheapest[i] != -1) {
				int set1 = find(parent, edges[cheapest[i]].src);
				int set2 = find(parent, edges[cheapest[i]].dest);

				if (set1 == set2)
					continue;
				MSTweight += edges[cheapest[i]].weight;
				Union(parent, rank, set1, set2);
				numComponents--;
			}
		}
	}

	cout << MSTweight;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, M;
	cin >> N >> M;

	vector<Edge> edges(M);

	for (int i = 0; i < M; i++)
		cin >> edges[i].src >> edges[i].dest >> edges[i].weight;

	sollin(edges, N, M);

	return 0;
}

 

---