邻接表实现的有向带权图及图算法（C++）_C

邻接表实现的有向带权图

- 相关概念
- 声明和定义
- 实现
- - 1. 构造函数
  - 2. 析构函数
  - 3. 深度优先遍历
  - 4。广度优先遍历
  - 5. 获取顶点在邻接表中对应的下标
  - 6. 添加顶点
  - 7. 移除顶点
  - 8. 添加边
  - 9. 移除边
  - 10. 转化为邻接矩阵
  - 11. 使用Prim算法求最小生成树
  - 12. 使用Kruskal算法求最小生成树
  - 13. 计算联通分量
  - 14. 使用Dijkstra算法求单元最短路
  - 15. 使用Floyd算法求每一对顶点上的最短路径
  - 16. 判断是否图中是否有环
  - 17. 拓扑排序
  - 18. 拓扑排序（递归）
  - 19. 单源最长路径
  - 20.关键路径
  - 21. 打印输出
- 测试
- - 测试代码
- 后记
- - 源代码

相关概念

邻接表（Adjacency List）：
我实现的方法相当于数组加链表

	struct Edge {	  // 边
		int toVertex; // 到达的那个顶点
		int weight;	  // 边的权重,或两个顶点之间的路径(不同算法不同解释,没有冲突)
		Edge* next;	  // 指向下一条边的指针
		Edge(int v, int w, Edge* nxt = nullptr) : toVertex(v), weight(w), next(nxt) {}
	};

	struct Vertex { // 顶点
		T val;
		Edge* edge; // 从当前顶点发出的边
		Vertex() : edge(nullptr) {}
	};

	Vertex* adj;   // 这就是邻接表了

邻接表是一个 Vertex类型的数组（ adj = new Vertex[ ] ）

数组元素Vertex中有一个指向Edge对象的指针（相当于链表的头节点），用来存放与对应Vertex相连的边

声明和定义

#include 
using std::vector;
using std::stack;
using std::cout;
using std::string;
using std::ifstream;
using std::function;
using VVI = vector<vector<int>>; // 重命名
/**
 * @brief 用邻接表(Adjcency List)实现的带权(Weighted)有向图(Directed Graph)
 *	也可以用来表示无向图(Undireced Graph), 即双向图(Bidirection Graph)
 * @tparam T 节点值的类型
 */
template <typename T>
class ALGraph {
public:
	struct Edge {	  // 边
		int toVertex; // 到达的那个顶点
		int weight;	  // 边的权重,或两个顶点之间的路径(不同算法不同解释,没有冲突)
		Edge* next;	  // 指向下一条边的指针
		Edge(int v, int w, Edge* nxt = nullptr) : toVertex(v), weight(w), next(nxt) {}
	};
	struct Vertex { // 顶点
		T val;
		Edge* edge; // 从当前顶点发出的边
		Vertex() : edge(nullptr) {}
	};
	struct Triple { // 三元组, 可以表示边
		int from, to, weight;
		Triple() = default;
		Triple(int f, int t, int w) : from(f), to(t), weight(w) {}
		bool operator<(const Triple& t) const { return weight > t.weight; }
	};
	struct UF { // Union Find
		int* p;
		UF(int n) { // init
			p = new int[n];
			for (int i = 0; i < n; ++i)
				p[i] = i;
		}
		~UF() { delete[] p; }
		int find(int u) {
			while (u != p[u])
				u = p[u] = p[p[u]];
			return u;
		}
		void unio(int u, int v) { p[find(u)] = find(v); }
		bool connected(int u, int v) { return find(u) == find(v); }
	};
	struct MST { // Minimal Spanning Tree
		int weight;
		vector<Triple> edges;
	};
	struct CC { // Connected Component
		int count;
		vector<Vertex> vertexs;
	};
	struct SSP {						   // Single Source Shortest Path
		int src;						   // 源点
		vector<int> path;				   // 到各点的路径
		vector<int> dist;				   // 到各点的距离
		virtual void print(int e, T a[]) { // 用来打印路径
			if (src == e)
				return;
			if (dist[e] == INF) {
				std::cout << "->" << a[e];
				return;
			}
			print(path[e], a);
			std::cout << "->" << a[e];
		}
	};
	struct MSP {					 // Mutiply Source Shortest Path
		VVI dist;					 // 各源点到各目标点的距离
		vector<vector<string>> path; //各源点到各目标点的路径
		MSP(int vertexs) {
			dist.resize(vertexs, vector<int>(vertexs));
			path.resize(vertexs, vector<string>(vertexs));
		}
	};
	struct SLP : public SSP { // Single Source Longset Path
		virtual void print(int e, T a[]) override {
			if (this->src == e)
				return;
			if (this->dist[e] == INT_MIN) {
				std::cout << "->" << a[e];
				return;
			}
			print(this->path[e], a);
			std::cout << "->" << a[e];
		}
	};
	struct CP : public MST { // Critical Path
		VVI path;
		vector<int> vs;
		void print(T a[]) { print(0, path.size() - 1, a); }
		void print(int s, int e, T a[]) {
			if (s == e) {
				vs.push_back(s);
				for (int i = vs.size() - 1; i >= 0; --i)
					cout << vs[i] << (i > 0 ? "->" : "\n");
				vs.pop_back();
				return;
			}
			vs.push_back(e);
			for (int i = 0; i < path[e].size(); i++)
				print(s, path[e][i], a);
			vs.pop_back();
		}
	};


private:
	int vertexNum; // 最大顶点数(可扩展)
	int edgeNum;   // 边数
	int curNum;	   // 当前顶点数
	Vertex* adj;   // 这就是邻接表了
	void dfs(function<void(Vertex&)> cb, bool vis[], int v);
	bool isCyclicDfs(bool* vis, bool* path, int u);
	void topologicalDfs(bool* vis, vector<int>& s, int u); //将某个顶点出发的拓扑序列添加到stack

public:
	static const int INF;					 // 对距离无穷大的"声明"
	ALGraph() = delete;						 // 不用这个构造
	ALGraph(T a[], int n);					 // 没有边
	ALGraph(T a[], int n, std::istream& in); // 从标准流获取边
	~ALGraph();								 // 主要是析构邻接表
	void dfs(function<void(Vertex&)> cb);	 // cb(Call Back)回调函数 O(n+e)
	void bfs(function<void(Vertex&)> cb);	 // 可以接收lambda表达式 O(n+e)
	int getVertexIndex(T v);				 // 获取给定值在邻接表中的下标 O(n)
	bool addVertex(T v);					 // 添加顶点 O(1)/O(n)
	bool removeVertex(T v);					 // 移除顶点(没有边与之相连) O(n)
	bool addEdge(T from, T to, int weight);	 // 添加边(带权) O(n)
	bool removeEdge(T from, T to);			 // 移除边 O(n)
	VVI toAdjcencyMatrix();					 // 转化为邻接矩阵 O(e)
	MST mstPrim();							 // 稠密图 O(nlogn)
	MST mstKruskal();						 // 稀疏图 O(eloge)
	CC connectedComponet();					 // 联通分量 O(n+e)
	SSP spDijkstra(T from);					 // 单源最短路 O(nlogn)
	MSP spFloyd();							 // 多源最短路 O(n^3)
	bool isCyclic();						 // 是否有环 O(n+e)
	vector<int> topologicalSort();			 // 拓扑排序 O(n+e)
	vector<int> topologicalSortRecursive();	 // 拓扑排序
	SLP longsetPath(T from);				 // 最长路径 O(n+e)
	CP criticalPath();						 // 关键路径
	template <typename Q>					 // 将图打印输出
	friend std::ostream& operator<<(std::ostream& os, ALGraph<Q>& g);
};
template <typename T>
const int ALGraph<T>::INF = 0x7ffff; // define

前面 public 的结构体是后面一些成员函数的返回值（因为有的要返回多个值有点要用特定的方式处理返回值）和一些后面的算法会用到的（并查集）。

实现 1. 构造函数

没有边的

template <typename T>
ALGraph<T>::ALGraph(T a[], int n) {
	curNum = vertexNum = n;
	adj = new Vertex[vertexNum];
	for (int i = 0; i < vertexNum; ++i)
		(adj + i)->val = a[i];
}

从输入流获取边的

template <typename T>
ALGraph<T>::ALGraph(T a[], int n, std::istream& in) {
	curNum = vertexNum = n;
	adj = new Vertex[vertexNum];
	for (int i = 0; i < vertexNum; ++i)
		(adj + i)->val = a[i];
	int u, v, w;
	in >> edgeNum;
	for (int i = 0; i < edgeNum; ++i) {
		in >> u >> v >> w;
		adj[u].edge = new Edge(v, w, adj[u].edge);
	}
}

2. 析构函数

就删除边和顶点对象

template <typename T>
ALGraph<T>::~ALGraph() {
	for (int i = 0; i < curNum; ++i)
		for (auto j = adj[i].edge; j;) {
			auto toDel = j;
			j = j->next;
			delete toDel;
		}
	delete[] adj;
	adj = nullptr;
}

3. 深度优先遍历

function 接受一个参数为Vertex&返回值为void的函数或者lambda表达式

cb ：Call Back (Function) 回调函数

template <typename T>
void ALGraph<T>::dfs(function<void(Vertex&)> cb) {
	bool vis[curNum];
	memset(vis, 0, curNum);
	for (int i = 0; i < curNum; ++i)
		if (!vis[i])
			dfs(cb, vis, i);
}

template <typename T>
void ALGraph<T>::dfs(function<void(Vertex&)> cb, bool vis[], int v) {
	cb(adj[v]);
	vis[v] = true;
	for (auto p = adj[v].edge; p; p = p->next)
		if (!vis[p->toVertex])
			dfs(cb, vis, p->toVertex);
}

4。广度优先遍历

template <typename T>
void ALGraph<T>::bfs(function<void(Vertex&)> cb) {
	std::queue<int> q;
	bool vis[curNum];
	memset(vis, 0, sizeof vis);
	for (int i = 0; i < curNum; ++i) {
		if (vis[i])
			continue;
		q.push(i);
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			if (vis[v])
				continue;
			cb(adj[v]);
			vis[v] = true;
			for (auto p = adj[v].edge; p; p = p->next)
				if (!vis[p->toVertex])
					q.push(p->toVertex);
		}
	}
}

5. 获取顶点在邻接表中对应的下标

template <typename T>
int ALGraph<T>::getVertexIndex(T v) {
	for (int i = 0; i < curNum; ++i)
		if (adj[i].val == v)
			return i;
	return -1;
}

6. 添加顶点

template <typename T>
bool ALGraph<T>::addVertex(T v) {
	if (curNum == vertexNum) { // recreate
		vertexNum <<= 1;
		Vertex* temp = new Vertex[vertexNum];
		for (int i = 0; i < curNum; ++i)
			temp[i] = adj[i];
		delete[] adj;
		adj = temp;
	}
	adj[curNum++].val = v;
	return true;
}

7. 移除顶点

只有当顶点没有边与之相连的时候才能移除

边存在或顶点不存在都删除失败返回false

template <typename T>
bool ALGraph<T>::removeVertex(T v) {
	int i = 0;
	for (; i < curNum; ++i)
		if (adj[i].val == v)
			break;
	if (i == curNum || adj[i].edge) //没找到或存在边
		return false;
	--curNum;
	for (int j = i; j < curNum; ++i) // remove
		adj[j] = std::move(adj[j + 1]);
	for (int i = 0; i < curNum; ++i) // fix
		for (auto p = adj[i].edge; p; p = p->next)
			if (p->toVertex > i)
				--p->toVertex;
	return true;
}

8. 添加边

template <typename T>
bool ALGraph<T>::addEdge(T from, T to, int weight) {
	int f = getVertexIndex(from), t = getVertexIndex(to); // O(n)
	adj[f].edge = new Edge(t, weight, adj[f].edge);
	++edgeNum;
	return true;
}

9. 移除边

template <typename T>
bool ALGraph<T>::removeEdge(T from, T to) {
	int f = getVertexIndex(from), t = getVertexIndex(to); // O(n)
	for (auto p = adj[f].edge, pre = p; p;)
		if (p->toVertex == t) {
			if (p == pre)
				adj[f].edge = p->next;
			else
				pre->next = p->next;
			delete p;
			--edgeNum;
			return true;
		}
	return false;
}

10. 转化为邻接矩阵

template <typename T>
VVI ALGraph<T>::toAdjcencyMatrix() {
	VVI ret(curNum, vector<int>(curNum, INF));
	for (int i = 0; i < curNum; ++i)
		ret[i][i] = 0;
	for (int i = 0; i < curNum; ++i) // 遍历所有边
		for (auto p = adj[i].edge; p; p = p->next)
			ret[i][p->toVertex] = p->weight;
	return ret;
}

11. 使用Prim算法求最小生成树

template <typename T>
typename ALGraph<T>::MST ALGraph<T>::mstPrim() {
	std::priority_queue<Triple> pq; // 使用优先队列
	bool vis[curNum];				// vertexNum
	memset(vis, 0, sizeof vis);
	MST ret;
	int w = 0;
	vis[0] = true;
	for (auto p = adj[0].edge; p; p = p->next) {
		int to = p->toVertex;
		if (!vis[to]) {
			Triple t(0, to, p->weight);
			pq.push(t);
		}
	}
	while (!pq.empty()) {
		Triple tp = pq.top();
		pq.pop();
		if (vis[tp.to])
			continue;
		w += tp.weight;
		ret.edges.push_back(tp);
		vis[tp.to] = true;
		for (auto p = adj[tp.to].edge; p; p = p->next) {
			int to = p->toVertex;
			if (!vis[to]) {
				Triple t(tp.to, to, p->weight);
				pq.push(t);
			}
		}
	}
	ret.weight = w;
	return ret;
}

12. 使用Kruskal算法求最小生成树

template <typename T>
typename ALGraph<T>::MST ALGraph<T>::mstKruskal() {
	std::priority_queue<Triple> pq; // 使用优先队列
	for (int i = 0; i < curNum; ++i)
		for (auto p = adj[i].edge; p; p = p->next) {
			Triple t(i, p->toVertex, p->weight);
			pq.push(t);
		}
	MST mst; // 返回值
	int& w = mst.weight = 0;
	UF uf(edgeNum); // 并查集
	while (!pq.empty()) {
		auto t = pq.top();
		pq.pop();
		if (uf.connected(t.from, t.to))
			continue;
		w += t.weight;
		uf.unio(t.from, t.to);
		mst.edges.push_back(t);
	}
	return mst;
}

13. 计算联通分量

返回联通分量的个数和每个联通分支的起始节点

template <typename T>
typename ALGraph<T>::CC ALGraph<T>::connectedComponet() {
	CC ret;
	bool vis[curNum];
	int cnt = 0;
	memset(vis, 0, curNum);
	for (int i = 0; i < curNum; ++i)
		if (!vis[i]) {
			++cnt;
			ret.vertexs.push_back(adj[i]);
			dfs([](Vertex& x) {}, vis, i);
		}
	ret.count = cnt;
	return ret;
}

14. 使用Dijkstra算法求单元最短路

返回最短路的路径和长度

template <typename T>
typename ALGraph<T>::SSP ALGraph<T>::spDijkstra(T from) {
	using PII = std::pair<int, int>;
	SSP ret;
	int& src = ret.src;
	for (int i = 0; i < curNum; ++i) // O(n)
		if (adj[i].val == from)
			src = i;
	vector<int>& dist = ret.dist;
	vector<int>& path = ret.path;
	path.resize(curNum);
	for (int i = 0; i < curNum; ++i) // O(n)
		dist.push_back(ALGraph::INF);
	dist[src] = 0;
	bool vis[curNum];
	memset(vis, 0, sizeof vis);
	std::priority_queue<PII> pq;
	pq.push({ 0, src });
	while (!pq.empty()) { // n
		PII p = pq.top(); // logn
		pq.pop();
		int u = p.second;
		if (vis[u])
			continue;
		vis[u] = true;
		for (auto p = adj[u].edge; p; p = p->next) { // e
			int v = p->toVertex, d = p->weight + dist[u];
			if (dist[v] > d) {
				dist[v] = d;
				path[v] = u;
				pq.push({ d, v });
			}
		}
	}
	return ret;
}

15. 使用Floyd算法求每一对顶点上的最短路径

这个参考《数据结构C++》上面的将连接表转化为邻接矩阵实现

template <typename T>
typename ALGraph<T>::MSP ALGraph<T>::spFloyd() {
	MSP msp(curNum);
	auto& dist = msp.dist;
	auto& path = msp.path;
	auto edge = toAdjcencyMatrix();
	for (int i = 0; i < curNum; ++i)
		for (int j = 0; j < curNum; ++j) {
			dist[i][j] = edge[i][j];
			if (dist[i][j] != INF)
				path[i][j] = { adj[i].val, adj[j].val };
			else
				path[i][j] = "";
		}
	for (int k = 0; k < curNum; ++k) // 中间节点
		for (int i = 0; i < curNum; ++i)
			for (int j = 0; j < curNum; ++j)
				if (dist[i][j] > dist[i][k] + dist[k][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
					path[i][j] = path[i][k] + path[k][j];
				}
	return msp;
}

16. 判断是否图中是否有环

template <typename T>
bool ALGraph<T>::isCyclicDfs(bool* vis, bool* path, int u) {
	if (!vis[u]) { // 没访问->访问&加入路径
		vis[u] = path[u] = true;
		for (auto p = adj[u].edge; p; p = p->next)
			if (!vis[p->toVertex] && isCyclicDfs(vis, path, p->toVertex) ||
				path[p->toVertex])
				return true; // 没访问->访问||访问过&在栈中->true
	}
	return (path[u] = false); // 访问过&d出栈
}
template <typename T>
bool ALGraph<T>::isCyclic() {
	bool vis[curNum], path[curNum]; // 环:遇到已经访问过&在栈中的顶点
	memset(vis, 0, sizeof vis);
	memset(path, 0, sizeof path);
	for (int i = 0; i < curNum; ++i) // n
		if (!vis[i] && isCyclicDfs(vis, path, i))
			return true;
	return false;
}

17. 拓扑排序

template <typename T>
vector<int> ALGraph<T>::topologicalSort() {
	bool vis[curNum];			// 用来标记是否访问过
	int deg[curNum];			// 记录每个顶点的入读
	int q[curNum], idx = 0;		// 队列, 它的下标
	memset(deg, 0, sizeof deg); // init
	memset(vis, 0, sizeof vis);
	memset(q, 0, sizeof q);
	for (int i = 0; i < curNum; ++i) // 1.计算入度 o(e)
		for (auto p = adj[i].edge; p; p = p->next)
			++deg[p->toVertex];
	for (int i = 0; i < curNum; ++i) // 2. if in-deg=0 : 入队
		if (deg[i] == 0) {
			q[idx++] = i;
			vis[i] = true;
		}
	vector<int> ret;								   //保存结果
	while (idx) {									   // 3.bfs
		int cur = q[--idx];							   //出队
		ret.push_back(cur);							   //添加到结果数组
		for (auto p = adj[cur].edge; p; p = p->next) { // AOVnet
			int v = p->toVertex;
			if (!vis[v]) {
				--deg[v];
				if (deg[v] == 0) { //  in-deg==0 入队
					q[idx++] = v;
					vis[v] = true;
				}
			}
		}
	}
	return (ret.size() == curNum ? ret : vector<int>()); // 有回路返回空
}

18. 拓扑排序（递归）

template <typename T>
void ALGraph<T>::topologicalDfs(bool* vis, vector<int>& s, int u) {
	vis[u] = true;
	for (auto p = adj[u].edge; p; p = p->next) {
		if (!vis[p->toVertex])
			topologicalDfs(vis, s, p->toVertex);
	}
	s.push_back(u);
}

template <typename T>
vector<int> ALGraph<T>::topologicalSortRecursive() {
	bool vis[curNum];
	vector<int> s;
	for (int i = 0; i < curNum; ++i)
		if (!vis[i])
			topologicalDfs(vis, s, i);
	reverse(s.begin(), s.end());
	return s;
}

19. 单源最长路径

类似 Dijkstra

template <typename T>
typename ALGraph<T>::SLP ALGraph<T>::longsetPath(T from) {
	SLP slp; // init start
	int& src = slp.src;
	for (int i = 0; i < curNum; ++i)
		if (adj[i].val == from)
			src = i;
	vector<int>& path = slp.path;
	path.resize(curNum);
	vector<int>& dist = slp.dist;
	dist.assign(curNum, INT_MIN);
	dist[src] = 0;
	bool vis[curNum];
	memset(vis, 0, sizeof vis);
	vector<int> s; // 存放所有点的拓扑序列的逆序
	for (int i = 0; i < curNum; ++i)
		if (!vis[i])
			topologicalDfs(vis, s, i);
	while (!s.empty()) {
		int u = *(s.end() - 1); // 倒数第一个
		s.pop_back();
		if (dist[u] != INT_MIN) //从src开始
			for (auto p = adj[u].edge; p; p = p->next) {
				int v = p->toVertex, d = dist[u] + p->weight;
				if (dist[v] < d) {
					dist[v] = d;
					path[v] = u;
				}
			}
	}
	return slp;
}

20.关键路径

没什么，就是调了两天的代码

template <typename T>
typename ALGraph<T>::CP ALGraph<T>::criticalPath() {
	CP cp;							  // 返回值 Critical Path
	vector<Triple>& edges = cp.edges; // 就是边了
	VVI& path = cp.path;			  // 打印路径时需要
	path.resize(curNum);			  // init
	int ve[curNum + 1] = { 0 };		  // 事件(vertex)最早发生时间
	int vl[curNum + 1];				  // 事件(vertex)最迟发生时间
	int deg[curNum + 1] = { 0 };	  // 入度
	stack<int> topo;				  // 存放逆拓扑序
	std::queue<int> q;				  // 求拓扑序时使用
	for (int u = 0; u < curNum; ++u)  // 初始化入度
		for (auto p = adj[u].edge; p; p = p->next)
			++deg[p->toVertex];
	for (int i = 0; i < curNum; i++)
		if (deg[i] == 0)
			q.push(i);
	while (!q.empty()) { // 使用顺拓扑序列求ve[]
		int u = q.front();
		// cout << u << ' '; // debug topo order
		q.pop();
		topo.push(u);
		for (auto p = adj[u].edge; p; p = p->next) {
			int v = p->toVertex, w = p->weight;
			--deg[v];
			if (deg[v] == 0)
				q.push(v);
			if (ve[u] + w > ve[v])
				ve[v] = ve[u] + w;
		}
	}
	// cout << "\n"; // end debug
	std::fill(vl, vl + curNum, ve[curNum - 1]);
	while (!topo.empty()) { // 使用逆拓扑序列求vl[]
		int u = topo.top();
		topo.pop();
		for (auto p = adj[u].edge; p; p = p->next) {
			int v = p->toVertex, w = p->weight;
			if (vl[v] - w < vl[u])
				vl[u] = vl[v] - w;
		}
	}
	for (int u = 0; u < curNum; u++) {
		for (auto p = adj[u].edge; p; p = p->next) {
			int v = p->toVertex, w = p->weight;
			int e = ve[u];	   //活动(边)最早发生时间
			int l = vl[v] - w; //活动(边)最晚发生时间
			if (e == l) {
				Triple tp(u, v, w);
				edges.push_back(tp);  // edges
				path[v].push_back(u); // path
			}
		}
	}
	cp.weight = ve[curNum - 1];
	return cp;
}

21. 打印输出

template <typename Q>
std::ostream& operator<<(std::ostream& os, ALGraph<Q>& g) {
	for (int i = 0; i < g.curNum; ++i) {
		os << g.adj[i].val;
		for (auto p = g.adj[i].edge; p; p = p->next)
			os << '-' << '(' << p->weight << ")->" << (g.adj[p->toVertex].val);
		os << '\n';
	}
	return os;
}

测试测试代码

每个功能一个用一个函数来测试

#include "adjacency_list.h"
using std::for_each;
char a[] = { 'T', 'A', 'N', 'G', 'Q', 'U', 'A', 'N', 'W' };
ifstream cin("adjacency_matrix.txt");
ALGraph<char> g(a, sizeof(a) / sizeof(a[0]), cin);

void test_triversal() {
	cout << "\n- 测试遍历 -\n";
	cout << "图g:" << '\n';
	cout << g;
	cout << "\n深度优先遍历\n";
	g.dfs([](ALGraph<char>::Vertex& x) { cout << x.val << ' '; });
	cout << "\n广度优先遍历\n";
	g.bfs([](ALGraph<char>::Vertex& x) { cout << x.val << ' '; });
}

void test_add_remove() {
	cout << "\n\n- 测试顶点和边的添加删除 -\n";
	cout << "添加顶点 x: " << (g.addVertex('x') ? "True" : "False") << '\n';
	cout << g;
	cout << "添加边 'x'->'T' w=100:" << (g.addEdge('x', 'T', 100) ? "True" : "False") << '\n';
	cout << g;
	cout << "移除存在边的节点 x: " << (g.removeVertex('x') ? "True" : "False") << '\n';
	cout << g;
	cout << "移除边 'x'->'T': " << (g.removeEdge('x', 'T') ? "True" : "False") << '\n';
	cout << g;
	cout << "移除不存在边的节点: " << (g.removeVertex('x') ? "True" : "False") << '\n';
	cout << g;
}

void test_mst() {
	cout << "\n\n- 测试最小生成树 -\n";
	cout << "-测试Kruskal算法:\n";
	ALGraph<char>::MST m1 = g.mstKruskal();
	cout << "权值: " << m1.weight << '\n';
	cout << "得到的最小生成树:\n";
	for_each(m1.edges.begin(), m1.edges.end(), [](ALGraph<char>::Triple x) { cout << '(' << x.from << ", " << x.to << ", " << x.weight << ") "; });
	cout << "\n-测试Prim算法:\n";
	ALGraph<char>::MST m2 = g.mstPrim();
	cout << "权值: " << m2.weight << '\n';
	cout << "得到的最小生成树:\n";
	for_each(m2.edges.begin(), m2.edges.end(), [](ALGraph<char>::Triple x) { cout << '(' << x.from << ", " << x.to << ", " << x.weight << ") "; });
}

void test_CC() {
	cout << "\n\n- 测试联通分支 -\n";
	auto cc = g.connectedComponet();
	cout << "联通分支数: " << cc.count << '\n';
	cout << "分支头顶点:\n";
	for_each(cc.vertexs.begin(), cc.vertexs.end(), [](ALGraph<char>::Vertex x) { cout << x.val << '\n'; });
}

void test_toMatrix() {
	cout << "\n\n- 测试转换为邻接矩阵 -\n";
	auto m = g.toAdjcencyMatrix();
	for_each(m.begin(), m.end(), [](vector<int>& x) {
		for_each(x.begin(), x.end(), [](int i) {
			if (i == ALGraph<char>::INF)
				cout << "INF\t";
			else
				cout << i << '\t';
		});
		cout << '\n';
	});
}

void test_SSP() {
	cout << "\n\n- 测试最短路 -\n";
	cout << "-使用Dijkstra算法:\n";
	int src = 0;
	cout << "起始顶点: " << a[src] << '\n';
	auto sp = g.spDijkstra(a[src]);
	cout << "到各点的距离: \n";
	for_each(sp.dist.begin(), sp.dist.end(), [](int x) { cout << x << ' '; });
	cout << "\n回溯的路径(下标): \n";
	for_each(sp.path.begin(), sp.path.end(), [](int x) { cout << x << ' '; });
	cout << "\n具体路径及长度(边权):\n";
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) {
		if (i == src)
			continue;
		cout << a[src];
		sp.print(i, a);
		cout << " (" << sp.dist[i] << ")\n";
	}
}

void test_MSP() {
	cout << "-使用Floyd算法:\n";
	auto msp = g.spFloyd();
	cout << "多元最短路(长度):\n\t";
	int cnt = 0;
	for (int i = 0; i < msp.path.size(); ++i)
		cout << a[i] << "\t\t";
	for_each(msp.dist.begin(), msp.dist.end(), [&](vector<int>& x) {
		cout << "\n"
			 << a[cnt++] << ":";
		for_each(x.begin(), x.end(), [](int i) {
			if (i == ALGraph<char>::INF)
				cout << '\t' << "INF\t";
			else
				cout << '\t' << i << '\t';
		});
	});
	cout << "\n多元最短路(具体路径):\n\t";
	for (int i = 0; i < msp.path.size(); ++i)
		cout << a[i] << "\t\t";
	cnt = 0;
	for_each(msp.path.begin(), msp.path.end(), [&](vector<string>& x) {
		cout << "\n"
			 << a[cnt++] << ":";
		for_each(x.begin(), x.end(), [](string& i) {
			cout << "\t" << i << "\t";
		});
	});
}
void test_isCyclic() {
	cout << "\n\n- 测试是否有环 -\n";
	cout << "是否有环: " << (g.isCyclic() ? "True" : "False") << '\n';
}
void test_topoSort() {
	cout << "\n\n- 测试拓扑排序 -\n";
	cout << "-非递归拓扑排序:\n";
	auto tp = g.topologicalSort();
	cout << "-拓扑序列:\n";
	for_each(tp.begin(), tp.end(), [](int x) { cout << x << ' '; });
	cout << "\n-递归拓扑排序:\n";
	auto to = g.topologicalSortRecursive();
	cout << "-拓扑序列:\n";
	for_each(to.begin(), to.end(), [](int x) { cout << x << ' '; });
}
void test_LP() {
	cout << "\n\n- 测试最长路径 -\n";
	int src = 0;
	cout << "起始顶点: " << a[src] << '\n';
	auto slp = g.longsetPath(a[src]);
	cout << "到各点的最长距离: \n";
	for_each(slp.dist.begin(), slp.dist.end(), [](int x) { cout << x << ' '; });
	cout << "\n回溯的路径(下标): \n";
	for_each(slp.path.begin(), slp.path.end(), [](int x) { cout << x << ' '; });
	cout << "\n具体路径及长度(边权):\n";
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) {
		if (i == src)
			continue;
		cout << a[src];
		slp.print(i, a);
		cout << " (" << slp.dist[i] << ")\n";
	}
}
void test_CP() {
	cout << "\n\n- 测试关键路径 -\n";
	ALGraph<char>::CP cp = g.criticalPath();
	cout << "关键活动: \n";
	for_each(cp.edges.begin(), cp.edges.end(), [](ALGraph<char>::Triple tp) { cout << "(" << tp.from << ", " << tp.to << ") "; });
	cout << "\n关键路径: \n";
	cp.print(a);
	cout << "\n长度: " << cp.weight << '\n';
}


int main() {
	test_triversal();
	test_add_remove();
	test_mst();
	test_CC();
	test_toMatrix();
	test_SSP();
	test_MSP();
	test_isCyclic();
	test_topoSort();
	test_LP();
	test_CP();
	return 0;
}

后记

我发现测试的时候一个函数一个函数的测没有问题

但是一起测就有问题了，代码太长还不好找

后面再看看吧。。。😑😑😑

源代码

==> Gitee

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/1324106.html

邻接表实现的有向带权图及图算法（C++）

发表评论

评论列表（0条）

邻接表实现的有向带权图 及 图算法（C++）

发表评论

评论列表（0条）

邻接表实现的有向带权图及图算法（C++）