스패닝 트리 Spanning Tree

• 스패닝 트리 : 원개 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프
  • 단, 사이클을 이루지 않는다 [ 트리형식이라고 많이들 이야기하지만, 트리의 사이클이 없는 특징을 의미하는 것으로 혼돈하지 말자 ]
  • 스패닝 트리는 유일하지 않다.

---

최소 스패닝 트리 Mininum Spanning Tree

Kruskal Algorithm

방법
1 ) 그래프의 모든 간선을 가중치의 오름차순으로 정렬
2 ) 스패닝 트리에 하나씩 추가

구현법
1 ) 간선 추가 후, DFS[깊이 우선 탐색] 탐색 후, 역방향 간선이 있는 지 확인
- 각 간선마다 깊이 우선 탐색을 하기 때문에 시간 복잡도는 O(|V|+|E|) *O(|E|) = O(|E|lg|E|)
2 ) 두 정점이 동일한 컴포넌트에 속하는지 확인하
- 유니온 파인드 (Union Find)

구현코드

typedef struct edge {
	int i;
	int j;
	int c;
};
typedef struct compare {
	bool operator()(edge a , edge b) {
		return a.c > b.c;
	}
};
vector<int> visited;
int find(int a) {
	if (visited[a] == a)
		return a;
	return find(visited[a]);
}
void uni(int a, int b) {
	a = find(a);
	b = find(b);
	visited[b] = visited[a];
}
int kruskal(int v,vector<edge> list) {
	for (int i = 0; i <= v; i++) {
		visited.push_back(i);
	}
	int answer = 0;
	priority_queue<edge, vector<edge>, compare> qu;
	for (int i = 0; i < list.size(); i++) {
		qu.push(list[i]);
	}
	while (!qu.empty()) {
		int s = qu.top().i;
		int e = qu.top().j;
		int c = qu.top().c;
		qu.pop();
		if (find(e) != find(s)) {
			uni(s, e);
			answer += c;
		}  
	}
	return answer;
}

Prim Algorithm

이미 만들어진 트리에 인접한 간선만을 고려한다는 점을 제외하면 프림 알고리즘과 크루스칼 알고리즘과 동일하다
방법_
1 ) 각 정점의 트리에 포함되었는지 여부를 나타내는 불린 값 배열 ADDED[]을 만든다
2 ) 각 차례마다 모든 간선을 순회하면서 다음으로 트리에 추가할 간선을 찾으면 됩니다. 단, 사이클이 생기지 않게

시간복잡도

• O(|V||E|)
• 우선순위 큐 사용 : O(|E|lg|V|)
  구현코드

typedef struct edge {
	int i;
	int j;
	int c;
};
typedef struct compare {
	bool operator()(edge a , edge b) {
		return a.c > b.c;
	}
};
int prim(int v, vector<edge> list) {
	int answer = 0;
	vector<int> visited;
	vector<vector<edge>> connect_list;
	for(int i=0;i<=v;i++){
		visited.push_back(0);
		vector<edge> a;
		connect_list.push_back(a);
	}
	for (int i = 0; i < list.size(); i++) {
		connect_list[list[i].i].push_back({ list[i].i,list[i].j,list[i].c });
		connect_list[list[i].j].push_back({ list[i].j,list[i].i,list[i].c });
	}
	priority_queue<edge,vector<edge>,compare> qu;
	qu.push({ 1,1,0 });
	while (!qu.empty()) {
		int s = qu.top().i;
		int e = qu.top().j;
		int c = qu.top().c;
		qu.pop();
		if (visited[e] ==1)
			continue;
		visited[e] = 1;
		answer += c;
		for (int i = 0; i < connect_list[e].size(); i++) { 
			qu.push({ e,connect_list[e][i].j,connect_list[e][i].c });
		}
	}
	return answer;
}