- 相关概念
- 定义和声明
- 实现
- 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} &
AMGraph 即 Adjacency Matrix Graph 用二维数组实现
通过模板参数_N设定顶点（ Vertex ）个数，通过程序运行时读取文件确定边数和具体的边信息
/**
* @brief 用邻接矩阵实现的带权值的有向图
* @tparam T 顶点类型
* @tparam _N 顶点个数
*/
template <class T, int _N>
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<T> toAdjacencyList(); // 转换为邻接表
template <class Q, int W> // 打印输出
friend std::ostream& operator<<(std::ostream& os, AMGraph<Q, W>& g);
~AMGraph() {}
};
其中toAdjacencyList
邻接表在邻接表实现的有向带权图 及 图算法（C++）
边（ Edge )：
同一目录下的adjacency_matrix.txt文件
11
0 1 5
0 2 3
0 3 4
1 4 2
2 4 1
3 5 6
4 6 8
4 7 11
5 7 9
6 8 7
7 8 10
第一行是边的条数N，后面N行每一行都是是元组： 起始顶点 结束顶点 权值或路径长度
已经在类中声明了：
static const int INF; // declare INF
随后在类外定义:
template <class T, int _N>
const int AMGraph<T, _N>::INF = 0xffff; // define INF
template <class T, int _N>
AMGraph<T, _N>::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 <class T, int _N>
void AMGraph<T, _N>::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 <class T, int _N>
void AMGraph<T, _N>::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 <class T, int _N>
void AMGraph<T, _N>::bfs() {
std::queue<int> 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 <class T, int _N>
ALGraph<T> AMGraph<T, _N>::toAdjacencyList() { // 转换为邻接表
ALGraph<T> 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 <class Q, int W>
std::ostream& operator<<(std::ostream& os, AMGraph<Q, W>& 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<string, 9> g(s);
int main(int argc, char const* argv[]) {
cout << "--用邻接矩阵实现的图: \n";
cout << g << '\n';
cout << "\n--图的深度优先遍历: \n";
g.dfs();
cout << "\n\n--图的广度优先遍历: \n";
g.bfs();
cout << "\n\n--将邻接矩阵转换为邻接表(一行是一个顶点的所有边和权): \n";
ALGraph<string> alg = g.toAdjacencyList();
cout << alg;
return 0;
}
adjacency_matrix.h
#if !defined(__ADJACENCY_MATRIX_H__)
#define __ADJACENCY_MATRIX_H__
#include 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）