邻接矩阵实现的带权有向图（C++）

- 相关概念
- 定义和声明
- 实现
- - 1. 距离无穷大的定义
  - 2. 构造函数
  - 3. 深度优先遍历
  - 4. 广度优先遍历
  - 6. 将邻接矩阵转换为邻接表
  - 7. 重载<<运算符打印输出
- 测试
- - 测试代码:
  - 测试结果:
- 源代码

相关概念

邻接矩阵中带权有向图的定义：
设G=（V，E），则：
e d g e [ i ] [ j ] = { w i j < v i , v j > ∈ E 0 i = = j ∞ e l s e edge[i][j]=left{begin{array}{l} w_{ij} & in E \ 0 & i==j\ infty & else end{array}right. edge[i][j]=⎩⎨⎧wij0∞∈Ei==jelse

定义和声明

AMGraph 即 Adjacency Matrix Graph 用二维数组实现

通过模板参数_N设定顶点（ Vertex ）个数，通过程序运行时读取文件确定边数和具体的边信息

template 
class AMGraph {
private:
	static const int INF;		 // declare INF
	int edge[_N][_N], edgeNum;	 // 栈上分配更快
	T vertexs[_N];				 // 存放节点值
	void dfs(char vis[], int u); // dfs core
	AMGraph();					 // 不用这个

public:
	AMGraph(T a[]);				  // 传入元素个数等于顶点数的数组构造
	void dfs();					  // 深度优先遍历
	void bfs();					  // 广度优先遍历
	ALGraph toAdjacencyList(); // 转换为邻接表
	template 	  // 打印输出
	friend std::ostream& operator<<(std::ostream& os, AMGraph& g);
	~AMGraph() {}
};

其中toAdjacencyList
邻接表在邻接表实现的有向带权图及图算法（C++）
边（ Edge )：
同一目录下的adjacency_matrix.txt文件

第一行是边的条数N，后面N行每一行都是是元组：起始顶点结束顶点权值或路径长度

实现 1. 距离无穷大的定义

已经在类中声明了：

static const int INF;		 // declare INF

随后在类外定义:

template 
const int AMGraph::INF = 0xffff; // define INF

2. 构造函数

template 
AMGraph::AMGraph(T a[]) { // 从模板参数获取节点数
	for (int i = 0; i < _N; ++i)
		vertexs[i] = a[i];
	for (int i = 0; i < _N; ++i)
		for (int j = 0; j < _N; ++j)
			edge[i][j] = i == j ? 0 : INF;
	std::ifstream cin("./adjacency_matrix.txt");
	cin >> edgeNum; // 从文件中读取边
	int u, v, w;
	for (int i = 0; i < edgeNum; ++i) {
		cin >> u >> v >> w;
		edge[u][v] = w;
	}
}

3. 深度优先遍历

template 
void AMGraph::dfs(char vis[], int u) {
	vis[u] = 1;
	std::cout << vertexs[u] << ' ';
	for (int v = 0; v < _N; ++v)
		if (edge[u][v] != INF && edge[u][v] && !vis[v]) {
			std::cout << "-(" << edge[u][v] << ")-> ";
			dfs(vis, v);
		}
}

template 
void AMGraph::dfs() {
	char vis[_N];					 // define
	std::memset(vis, 0, sizeof vis); // init
	for (int u = 0; u < _N; ++u)	 // do
		if (!vis[u])
			dfs(vis, u);
}

4. 广度优先遍历

template 
void AMGraph::bfs() {
	std::queue q;				 // define
	char vis[_N];					 // define
	std::memset(vis, 0, sizeof vis); // init
	for (int u = 0; u < _N; ++u) {	 // 避免非联通
		if (!vis[u]) {
			q.push(u);
			while (!q.empty()) {
				int v = q.front();
				q.pop();
				if (!vis[v]) { //没访问就访问
					std::cout << vertexs[v] << ' ';
					vis[v] = 1;
				}
				for (int w = 0; w < _N; ++w) // 添加可访问的
					if (edge[v][w] && edge[v][w] != INF && !vis[w])
						q.push(w);
			}
		}
	}
}

6. 将邻接矩阵转换为邻接表

template 
ALGraph AMGraph::toAdjacencyList() { // 转换为邻接表
	ALGraph ret(this->vertexs, _N);		   // 定义
	for (int i = 0; i < _N; ++i)			   // 添加边
		for (int j = 0; j < _N; ++j) {
			int w = this->edge[i][j];
			if (w && w != this->INF)
				ret.addEdge(vertexs[i], vertexs[j], w);
		}
	return ret;
}

7. 重载<<运算符打印输出

template 
std::ostream& operator<<(std::ostream& os, AMGraph& g) {
	for (int i = 0; i < W; ++i)
		os << "t" << g.vertexs[i];
	for (int i = 0; i < W; ++i) {
		os << 'n'
		   << g.vertexs[i];
		for (int j = 0; j < W; ++j) {
			if (g.edge[i][j] == g.INF)
				os << "tINF";
			else
				os << 't' << g.edge[i][j];
		}
	}
	return os;
}

测试测试代码:

#include "adjacency_matrix.h"
using namespace std;
string s[] = { "tang", "quan", "wei", "唐", "权", "威", "T", "Q", "W" };
AMGraph g(s);

int main(int argc, char const* argv[]) {
	cout << "--用邻接矩阵实现的图: n";
	cout << g << 'n';
	cout << "n--图的深度优先遍历: n";
	g.dfs();
	cout << "nn--图的广度优先遍历: n";
	g.bfs();
	cout << "nn--将邻接矩阵转换为邻接表(一行是一个顶点的所有边和权): n";
	ALGraph alg = g.toAdjacencyList();
	cout << alg;
	return 0;
}

测试结果:

源代码

adjacency_matrix.h

#if !defined(__ADJACENCY_MATRIX_H__)
#define __ADJACENCY_MATRIX_H__
#include 			// cout
#include 			// queue
#include 			// ifstream
#include 			// menset
#include "adjacency_list.h" // totoAdjacencyList


template 
class AMGraph {
private:
	static const int INF;		 // declare INF
	int edge[_N][_N], edgeNum;	 // 栈上分配更快
	T vertexs[_N];				 // 存放节点值
	void dfs(char vis[], int u); // dfs core
	AMGraph();					 // 不用这个

public:
	AMGraph(T a[]);				  // 传入元素个数等于顶点数的数组构造
	void dfs();					  // 深度优先遍历
	void bfs();					  // 广度优先遍历
	ALGraph toAdjacencyList(); // 转换为邻接表
	template 	  // 打印输出
	friend std::ostream& operator<<(std::ostream& os, AMGraph& g);
	~AMGraph() {}
};
template 
const int AMGraph::INF = 0xffff; // define INF
template 
AMGraph::AMGraph(T a[]) { // 从模板参数获取节点数
	for (int i = 0; i < _N; ++i)
		vertexs[i] = a[i];
	for (int i = 0; i < _N; ++i)
		for (int j = 0; j < _N; ++j)
			edge[i][j] = i == j ? 0 : INF;
	std::ifstream cin("./adjacency_matrix.txt");
	cin >> edgeNum; // 从文件中读取边
	int u, v, w;
	for (int i = 0; i < edgeNum; ++i) {
		cin >> u >> v >> w;
		edge[u][v] = w;
	}
}
template 
void AMGraph::dfs(char vis[], int u) {
	vis[u] = 1;
	std::cout << vertexs[u] << ' ';
	for (int v = 0; v < _N; ++v)
		if (edge[u][v] != INF && edge[u][v] && !vis[v]) {
			std::cout << "-(" << edge[u][v] << ")-> ";
			dfs(vis, v);
		}
}

template 
void AMGraph::dfs() {
	char vis[_N];					 // define
	std::memset(vis, 0, sizeof vis); // init
	for (int u = 0; u < _N; ++u)	 // do
		if (!vis[u])
			dfs(vis, u);
}
template 
void AMGraph::bfs() {
	std::queue q;				 // define
	char vis[_N];					 // define
	std::memset(vis, 0, sizeof vis); // init
	for (int u = 0; u < _N; ++u) {	 // 避免非联通
		if (!vis[u]) {
			q.push(u);
			while (!q.empty()) {
				int v = q.front();
				q.pop();
				if (!vis[v]) { //没访问就访问
					std::cout << vertexs[v] << ' ';
					vis[v] = 1;
				}
				for (int w = 0; w < _N; ++w) // 添加可访问的
					if (edge[v][w] && edge[v][w] != INF && !vis[w])
						q.push(w);
			}
		}
	}
}
template 
ALGraph AMGraph::toAdjacencyList() { // 转换为邻接表
	ALGraph ret(this->vertexs, _N);		   // 定义
	for (int i = 0; i < _N; ++i)			   // 添加边
		for (int j = 0; j < _N; ++j) {
			int w = this->edge[i][j];
			if (w && w != this->INF)
				ret.addEdge(vertexs[i], vertexs[j], w);
		}
	return ret;
}
template 
std::ostream& operator<<(std::ostream& os, AMGraph& g) {
	for (int i = 0; i < W; ++i)
		os << "t" << g.vertexs[i];
	for (int i = 0; i < W; ++i) {
		os << 'n'
		   << g.vertexs[i];
		for (int j = 0; j < W; ++j) {
			if (g.edge[i][j] == g.INF)
				os << "tINF";
			else
				os << 't' << g.edge[i][j];
		}
	}
	return os;
}
#endif // __ADJACENCY_MATRIX_H__

邻接矩阵实现的带权有向图（C++）

C/C++/C#相关栏目本月热门文章