图 最小支撑树

图(Graph)由顶点(Node)和边(Edge)构成，可分为有向图和无向图，带权图和无权图储存方式主要有两种，邻接矩阵或邻接链表。下面的代码是我用邻接矩阵法储存的图。

#pragma once
#ifndef _GRAPH_H_
#define _GRAPH_H_
#include <iostream>
#include <queue>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::queue;
using std::vector;

class Graph {
public:
	Graph();													//构造函数1
	Graph(const vector<int> &, const vector<vector<int> > &);	//构造函数2，参数分别为顶点数组和邻接矩阵
	Graph(const Graph &, const vector<int> &);					//构造函数3，根据已经存在的图的邻接矩阵，使用新的顶点数组构造图
	Graph(const Graph &, const vector<vector<int> > &);			//构造函数4，根据已经存在的图的顶点数组，使用新的邻接矩阵构造图
	void init();												//初始化图
	int firstadj(int);			//求某边的第一个邻接点
	int nextadj(int, int);		//求某边在某临界点之后的邻接点
	void Traverse_DFS();		//深度优先遍历
	void Traverse_BFS();		//广度优先遍历
	inline int EdgesWeight(int i, int j) const { return edges[i][j]; }	//返回某边的权重（带权图）
	inline unsigned size() const { return _size; }						//返回图的顶点数
protected:
	unsigned _size;					//顶点数
	vector<int> vectors;			//顶点数组
	vector<vector<int> > edges;		//邻接矩阵
	void dfs(int, vector<bool> &);	//深度优先遍历（单连通域）
	void bfs(int, vector<bool> &);	//广度优先遍历（单连通域）
};

Graph::Graph() {
	init();
}

void Graph::init() {
	cout << "请输入顶点的个数：";
	cin >> _size;
	vectors.resize(_size);
	edges.resize(_size);
	for (unsigned i = 0; i < _size; ++i)
		edges[i].resize(_size);
	cout << "请输入数据：";
	for (unsigned i = 0; i < _size; ++i)
		cin >> vectors[i];
	cout << "请输入邻接矩阵：";
	for (unsigned i = 0; i < _size; ++i)
		for (unsigned j = 0; j < _size; ++j)
			cin >> edges[i][j];
}

Graph::Graph(const Graph &g, const vector<int> &_vectors) {
	// assert : g.size() == _vectors.size()
	_size = _vectors.size();
	vectors = g.vectors;
	edges = g.edges;
	cout << this;
}

Graph::Graph(const vector<int> &_vectors, const vector<vector<int>> &_edges) {
	// assert : _vectors.size() == _edges.size()
	_size = _vectors.size();
	vectors = _vectors;
	edges = _edges;
}

int Graph::firstadj(int v) {
	for (unsigned i = 0; i < _size; ++i)
		if (edges[v][i]) return i;
	return -1;
}

int Graph::nextadj(int v, int w) {
	for (unsigned i = w+1; i < _size; ++i)
		if (edges[v][i]) return i;
	return -1;
}

void Graph::Traverse_DFS() {
	vector<bool> visited(_size, false);
	for (unsigned i = 0; i < _size; ++i)
		if (!visited[i])
			dfs(i, visited);
}

void Graph::Traverse_BFS() {
	vector<bool> visited(_size, false);
	for (unsigned i = 0; i < _size; ++i)
		if (!visited[i])
			bfs(i, visited);
}

void Graph::dfs(int v, vector<bool> &visited) {
	cout << vectors[v] << ' ';
	visited[v] = true;
	int w = firstadj(v);
	while (w != -1) {
		if (!visited[w])
			dfs(w, visited);
		w = nextadj(v, w);
	}
}

void Graph::bfs(int v, vector<bool> &visited) {
	cout << vectors[v] << ' ';
	visited[v] = true;
	queue<int> Q;
	Q.push(v);
	while (!Q.empty()) {
		v = Q.front();
		Q.pop();
		int w = firstadj(v);
		while (w != -1) {
			if (!visited[w]) {
				cout << vectors[w] << ' ';
				visited[w] = true;
				Q.push(w);
			}
			w = nextadj(v, w);
		}
	}
}


#endif // _GRAPH_H_

最小支撑树（最小生成树），是指带权图中可以覆盖图中全部顶点且各边权重和最小的无环连同子图。构造最小支撑树的算法，有Prime算法和Kruskal算法。

Prime算法的核心是：
指定一个起点，将起点标记为已选顶点。然后反复在一段已选，一段未选的边中选择一条权重最小的边，直到所有顶点全部成为已选顶点（选择n-1条边）。
1）设置一个标记数组，标记是否为已选顶点。
2）设置一个结构体用来储存备选边（一段已选，一段未选的边）。比如，设计为

struct MinEdgeType {
	int _the_seleted_node;  //备选边的另一个顶点，备选边数组的下标作为另一个顶点
	int _weight;                    //该边的权重
};
typedef vector<MinEdgeType> MinEdgeVecType;    //备选边的顶点数组

3）因为只需要所有边中最小的边，所以不需要求出所有的边，只需要开顶点个数大小的数组就可以了。
4）在有了一个新增的选中顶点之后，需要更新备选边数组。

Prime算法的代码（部分）如下：

struct MinEdgeType {
		int _the_seleted_node;
		int _weight;
	};
	typedef vector<MinEdgeType> MinEdgeVecType;
	void Init_MinEdges(const Graph &g, MinEdgeVecType &MinEdges, int v0) {
		for (unsigned i = 0; i < g.size(); ++i) {
			int weight = g.EdgesWeight(v0, i);
			if (weight) {
				MinEdges[i]._the_seleted_node = v0;
				MinEdges[i]._weight = weight;
			}
			else MinEdges[i]._weight = INT_MAX;
		}
	}
	int Get_MinEdge(const Graph &g, MinEdgeVecType &MinEgdes, vector<bool> &selected) {
		int min = INT_MAX, ans;
		for (unsigned i = 0; i < g.size(); ++i)
			if (!selected[i] && MinEgdes[i]._weight < min) {
				ans = i;
				min = MinEgdes[i]._weight;
			}
		return ans;
	}
	void change_MinEdges_with(const Graph &g, MinEdgeVecType &MinEdges, int k, vector<bool> &selected) {
		for (unsigned i = 0; i < g.size(); ++i)
			if (!selected[i])
				if (g.EdgesWeight(k, i) && g.EdgesWeight(k, i) < MinEdges[i]._weight) {
					MinEdges[i]._weight = g.EdgesWeight(k, i);
					MinEdges[i]._the_seleted_node = k;
				}
	}
	vector<int> Prime(const Graph &_Origin_Graph, int _Start) {
		unsigned _size = _Origin_Graph.size();
		vector<bool> selected(_size, false);
		MinEdgeVecType MinEdges(_size);
		vector<int> Ans_Set;
		Ans_Set.push_back(_Start);
		selected[_Start] = true;
		Init_MinEdges(_Origin_Graph, MinEdges, _Start);
		while (--_size) {
			int _selected_node = Get_MinEdge(_Origin_Graph, MinEdges, selected);
			Ans_Set.push_back(_selected_node);
			selected[_selected_node] = true;
			change_MinEdges_with(_Origin_Graph, MinEdges, _selected_node, selected);
		}
		return Ans_Set;
	}

以上代码只返回了选定顶点的数组，暂未完成之后的操作…

Kruskal算法的核心是：
在与已选的边不构成回路的边里选择出权重最小的边。
1）可以将图中的所有边都过一遍，把边和边的权重打包起来进行排序，这样可以避免每一次都从图中找边。
2）打包的方法有很多种，这里采用的std::pair
3）下面为了操作方便，从Graph类中派生出一个新的类。
4）判断是否构成回路可采用电位法，即连通的顶点具有相同的电位值。
完整的Kruskal算法的代码如下：

class Kruskal_Graph :public Graph {
	public:
		Kruskal_Graph(const Graph &g) :Graph(g) { init_keys(); }
		friend Graph Kruskal(Kruskal_Graph);
	protected:
		void init_keys();
		vector<int> keys;
	};
	void Kruskal_Graph::init_keys() {
		keys.resize(_size);
		for (unsigned i = 0; i < _size; ++i)
			keys[i] = i;
	}
	inline int min(int _Left, int _Right) {
		return _Left < _Right ? _Left : _Right;
	}
	Graph Kruskal(Kruskal_Graph Tmp) {
		vector<vector<int> > edges(Tmp._size, vector<int>(Tmp._size, 0));
		vector<pair<int, pair<int, int> > > Weight_Set;
		for (unsigned i = 0; i < Tmp._size; ++i)
			for (unsigned j = 0; j <= i; ++j)
				if (Tmp.edges[j][i])
					Weight_Set.push_back(pair<int, pair<int, int> >(Tmp.edges[j][i], pair<int, int>(j, i)));
		sort(Weight_Set.begin(), Weight_Set.end(), [](const pair<int, pair<int, int> > &_Left, pair<int, pair<int, int> > &_Right) { return _Left.first > _Right.first; });
		unsigned _size = Tmp._size;
		for (; _size;) {
			pair<int, pair<int, int> > _Tmp = *Weight_Set.rbegin();
			Weight_Set.pop_back();
			if (Tmp.keys[_Tmp.second.first] != Tmp.keys[_Tmp.second.second]) {
				Tmp.keys[_Tmp.second.first] = Tmp.keys[_Tmp.second.second] = min(Tmp.keys[_Tmp.second.first], Tmp.keys[_Tmp.second.second]);
				edges[_Tmp.second.first][_Tmp.second.second] = edges[_Tmp.second.second][_Tmp.second.first] = _Tmp.first;
				--_size;
			}
		}
		return Graph(Tmp.vectors, edges);
	}