图

图

目录

​​基础：​​

​​ 邻接矩阵，邻接表表示图的基本实现​​

​​邻接表，邻接矩阵的迭代器类的实现​​

​​稀疏图和稠密图的深度优先遍历​​

​​图的深度优先遍历，得出图的路径​​

​​广度优先遍历，使用队列的数据结构，可实现查找图的最短路径​​

​​整套代码​​

​​测试代码​​

基础：

无向图是一种特殊的有向图

简单图，一般不包括自环边，平行边

用邻接矩阵、邻接表表示图，前一个可能更加适用于稠密图，后一个更加适用于稀疏图

邻接矩阵，邻接表表示图的基本实现

#include//稠密图-邻接矩阵class DenseGraph {public: DenseGraph(int n,bool directed) { this->n = n; this->m = 0; this->directed = n; //初始化邻接矩阵 for (int i = 0; i < n; i++) { g.push_back(vector(n, false)); } } ~DenseGraph() { } //给图增加一条边，前提是这两个节点之间原来是没有边的 void AddEdge(int a, int b) { //检查越界 assert(a >= 0 && a < n); assert(b >= 0 && b < n); //判断a,b之间是否有边，如果已经存在边，返回 if (hasedge(a, b)) return; //赋值 g[a][b] = true; //判断是否是有向图 if (!directed) { g[b][a] = true; } //维护变量 m++; } //两个节点之间是否存在一条边 bool hasedge(int a, int b) { //检查越界 assert(a >= 0 && a < n); assert(b >= 0 && b < n); return g[a][b]; } //返回图的边数 int E() { return m; } //返回图的点数 int V() { return n; }private: //n表示图的点数，m表示图的边数 int n, m; //表示是否是有向图 bool directed; //表示稀疏矩阵 vector>g; };//稀疏图-邻接表class SparseGraph{public: SparseGraph(int n, int directed) { this->n = n; this->m = 0; this->directed = directed; for (int i = 0; i < n; i++) { //将向量中的元素设为空 g.push_back(vector()); } } ~SparseGraph() { } //给图添加一条边,因为没有考虑平行边，所以该函数可能会导致平行边 void AddEdge(int a, int b) { //检查越界问题 assert(a >= 0 && a < n); assert(b >= 0 && b < n); //如果两点间存在边，则返回，如果加了下列几行代码，则时间复杂度编程O（N），故一般不考虑平行边， //if (hasEdge(a, b)) // return ; //赋值 g[a].push_back(b); //判断是否是自环边，或者是都是有向图，只有非自环边，或者无向图，才满足条件 if (a!=b&&!directed) g[b].push_back(a); m++; } //判断是否两点是否存在边 bool hasEdge(int a, int b) { //检查越界问题 assert(a >= 0 && a < n); assert(b >= 0 && b < n); for (int i = 0; i < g[a].size(); i++) { if (g[a][i] == b) { return true; } } return false; } //返回图的边数 int E() { return m; } //返回图的点数 int V() { return n; }private: //n 表示点，m表示边 int n, m; //判断是否是有向图 int directed; //邻接表 vector>g;};

邻接表，邻接矩阵的迭代器类的实现

（图的实现算法没有变，只是在各自的类中添加了迭代器实现，并且两种图的迭代器的接口一样）使得后面可以用泛型编程，通过使用相同接口的迭代器访问两种不同类型图，以至于实现适用于两种类型的图算法

#pragma once#include//稠密图-邻接矩阵 class DenseGraph { private: //n表示图的点数，m表示图的边数 int n, m; //表示是否是有向图 bool directed; //将变量放在了public权限中，因为遍历方便 //表示稀疏矩阵 vector>g; public: DenseGraph(int n, bool directed) { this->n = n; this->m = 0; this->directed =directed; //初始化邻接矩阵 for (int i = 0; i < n; i++) { g.push_back(vector(n, false)); } } ~DenseGraph() { } //给图增加一条边，前提是这两个节点之间原来是没有边的 void AddEdge(int a, int b) { //检查越界 assert(a >= 0 && a < n); assert(b >= 0 && b < n); //判断a,b之间是否有边，如果已经存在边，返回 if (hasedge(a, b)) return; //赋值 g[a][b] = true; //判断是否是有向图 if (!directed) { g[b][a] = true; } //维护变量 m++; } //两个节点之间是否存在一条边 bool hasedge(int a, int b) { //检查越界 assert(a >= 0 && a < n); assert(b >= 0 && b < n); return g[a][b]; } //返回图的边数 int E() { return m; } //返回图的点数 int V() { return n; } //展示图 void show() { cout << "==========DenseGraph===============" << endl; for (int i = 0; i < n; i++) { cout << i << ": "; for (int j = 0; j < n; j++) { cout << g[i][j]<<" "; } cout << endl; } } class adjIterator { private: //定义一个图的引用 DenseGraph &G; //迭代器指向的节点 int v; //当前迭代器指向的索引 int index; public: //初始化引用类型数据成员的唯一机会是在构造函数初始化列表中 adjIterator(DenseGraph &g, int v) :G(g) { this->v = v; this->index = -1; } //迭代器的头 //返回第一个不为false的索引 int begin() { //index 是这个类的属性，只有赋值改变，才会改变，当几点序列改变时，index得初始化 index = -1; return next(); } //迭代器下一个 //返回下一个不为false的索引 int next() { //index 是这个类的属性，只有赋值改变，才会改变 for (index += 1; index < G.V(); index++) { if (G.g[v][index]) { //为了返回下一个不为false的索引，下一次跳入循环后需要index+1,跳过刚刚返回的索引值 return index; } } return -1; } //迭代的结尾 //返回这个图的总点数 int end() { return index >= G.V(); } }; };//稀疏图-邻接表 class SparseGraph { private: //n 表示点，m表示边 int n, m; //判断是否是有向图 int directed; //邻接表 vector>g; public: SparseGraph(int n, int directed) { this->n = n; this->m = 0; this->directed = directed; for (int i = 0; i < n; i++) { //将向量中的元素设为空 g.push_back(vector()); } } ~SparseGraph() { } //给图添加一条边,因为没有考虑平行边，所以该函数可能会导致平行边 void AddEdge(int a, int b) { //检查越界问题 assert(a >= 0 && a < n); assert(b >= 0 && b < n); //如果两点间存在边，则返回，如果加了下列几行代码，则时间复杂度编程O（N），故一般不考虑平行边， //if (hasEdge(a, b)) // return ; //赋值 g[a].push_back(b); //判断是否是自环边，或者是都是有向图，只有非自环边，或者无向图，才满足条件 if (a != b && !directed) g[b].push_back(a); m++; } //判断是否两点是否存在边 bool hasEdge(int a, int b) { //检查越界问题 assert(a >= 0 && a < n); assert(b >= 0 && b < n); for (int i = 0; i < g[a].size(); i++) { if (g[a][i] == b) { return true; } } return false; } //返回图的边数 int E() { return m; } //返回图的点数 int V() { return n; } //展示图 void show() { cout << "==========SparseGraph===============" << endl; for (int i = 0; i < n; i++) { cout << i << ": "; for (int j = 0; j < g[i].size(); j++) { cout << g[i][j] << " "; } cout << endl; } } //邻接表的迭代器类 class adjIterator { private: SparseGraph &G; //当前迭代器节点的索引 int v; //当前迭代器节点中的索引 int index; public: //初始化引用类型的数据成员，只能在构造函数的初始化列表中初始化 adjIterator(SparseGraph &g, int v) :G(g) { this->v = v; this->index = 0; } //迭代器的开始，返回当前节点中的第一个索引 int begin() { //对于后面的节点，begin必须将index初始化为0才行 index = 0; //此处不应该是G.V(),应该是对应每个节点中的多少个索引 if (G.g[v].size()) return G.g[v][index]; //return -1; } //迭代器的迭代，返回当前节点中下一个索引 int next() { index++; //此处不应该是G.V(),应该是对应每个节点中的多少个索引 if (index < G.g[v].size()) return G.g[v][index]; //return -1; } //迭代器的接受 int end() { return index >= G.g[v].size(); } }; };

稀疏图和稠密图的深度优先遍历

并可通过深度优先遍历得出图的连通分量数

//适用于稀疏图和稠密图的深度优先遍历，可得出连通分量数template class Component {private: //为了存储一份图 Graph &G; //记录每一个指针是否被访问过 bool *visited; //记录多少个连通分量 int ccount; //记录图中连接 int *unionfind; //深度优先遍历 void dfs(int v) { visited[v] = true; //每个连通分量一个连接，用ccount最为合适 unionfind[v] = ccount; typename Graph::adjIterator iterator(G, v); for (int i = iterator.begin(); !iterator.end(); i = iterator.next()) { if (!visited[i]) { dfs(i); } } }public: Component(Graph & graph):G(graph) { visited = new bool[G.V()]; unionfind = new int[G.V()]; ccount = 0; for (int i = 0; i < G.V(); i++) { visited[i] = false; unionfind[i] = -1; } for(int i=0;i= 0 && v < G.V()); assert(w >= 0 && w < G.V()); return unionfind[v] == unionfind[w]; } };

图的深度优先遍历，得出图的路径

图的深度优先遍历，得到图的某点到另一个点的路径，并打印出来

深度优先遍历：遍历到没有被访问的a点，先遍历与a点相邻的没有被访问过的b点，再遍历跟b点相邻没有遍历过的点，递归下去，知道这支递归中的点都没被访问了，再返回遍历与a点相邻的没有被访问过的c点

稀疏图的深度优先遍历的时间复杂度：O(V+E)

稠密图的深度优先遍历的时间复杂度：O（V^2）

//通过图的深度优先遍历，得到图的某点到另一个点的路径，并打印出来template class Path {private: //图的引用 Graph&G; //这个点到其他点的路径 int s; //表示点是否被遍历过 bool *visited; //根据from就能倒推出两点之间的路径 int *from;public: Path(Graph&graph,int s):G(graph) { assert(s >= 0 && s < G.V()); visited = new bool[G.V()]; from = new int[G.V()]; this->s = s; for (int i = 0; i < G.V(); i++) { visited[i] = false; from[i] = -1; } dfs(s); } ~Path() { delete[] visited; delete[] from; } //判断s与w之间是否有路 bool haspath(int w) { assert(w >= 0 && w < G.V()); return visited[w]; } //s与w之间是一个怎样的路径,存在vector 中 void path(int w, vector&vec) { //因为希望打印出来是从s到w,但是索引只能从w->s，所以需要用到栈 stack st; while (w!=-1) { //当由from[w]迭代过来的w=-1的前一个时，则w=s，则s也存入 st.push(w); w = from[w]; } //初始化vec vec.clear(); //将栈的元素转到向量的元素 while (!st.empty()) { vec.push_back(st.top()); st.pop(); } } //打印出s与w之间的路径 void showpath(int w) { vector vec; path(w, vec); cout << s<<"->"<= 0 && v < G.V()); visited[v] = true; //利用迭代器访问稀疏图，稠密图节点中的元素 typename Graph::adjIterator iterator(G, v); for (int i = iterator.begin(); !iterator.end(); i = iterator.next()) { //如果i没有被访问，则从i递归下去，直到访问完为止 if (!visited[i]) { from[i] = v; dfs(i); } } }};

广度优先遍历，使用队列的数据结构，可实现查找图的最短路径

广度优先遍历：先选择没有被访问过的a点，再将与a点相邻的b,c，d....等点加入队列，当访问到b点时，再将与b点相邻的e,f...等点加入队列中，依次下去

//无权图的广度优先遍历得出无向图最短路径 template class Shortpath {private: //图的引用 Graph&G; //这个点到其他点的路径 int s; //表示点是否被遍历过 bool *visited; //from[i] 表示i节点是由from[i]得到 int *from; //记录s到其他点的最短距离 int *ord;public: Shortpath(Graph &graph, int s) :G(graph) { assert(s >= 0 && s < G.V()); this->s = s; visited = new bool[G.V()]; from = new int[G.V()]; ord = new int[G.V()]; for (int i = 0; i < G.V(); i++) { visited[i] = false; from[i] = -1; ord[i] = -1; } //无向图最短路径算法 //使用一个队列 queueq; q.push(s); visited[s] = true; ord[s] = 0; while (!q.empty()) { //提取队首元素，有返回值 int v = q.front(); //弹出队首，无返回值 q.pop(); //利用迭代器访问稀疏图，稠密图节点中的元素 typename Graph::adjIterator iterator(G, v); for (int i = iterator.begin(); !iterator.end(); i = iterator.next()) { //如果i没有被访问， if (!visited[i]) { //在队尾加入元素 q.push(i); visited[i] = true; //广度优先遍历，通过from，找到最短路径 from[i] = v; //经过一条路径加1 ord[i] = ord[v] + 1; } } } } ~Shortpath() { delete[] visited; delete[] from; delete[] ord; } //判断s与w之间是否有路 bool haspath(int w) { assert(w >= 0 && w < G.V()); return visited[w]; } //s与w之间是一个怎样的路径,存在vector 中 void path(int w, vector&vec) { //因为希望打印出来是从s到w,但是索引只能从w->s，所以需要用到栈 stack st; while (w != -1) { //当由from[w]迭代过来的w=-1的前一个时，则w=s，则s也存入 st.push(w); w = from[w]; } //初始化vec vec.clear(); //将栈的元素转到向量的元素 while (!st.empty()) { vec.push_back(st.top()); st.pop(); } } //打印出s与w之间的路径 void showpath(int w) { vector vec; path(w, vec); cout << s << "->" << w << " :"; //vec中元素的打印 for (int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << endl; } //返回s到w的最短路径长度 int length(int w) { assert(w >= 0 && w < G.V()); return ord[w]; }};

整套代码

#pragma once#include//稠密图-邻接矩阵 class DenseGraph { private: //n表示图的点数，m表示图的边数 int n, m; //表示是否是有向图 bool directed; //将变量放在了public权限中，因为遍历方便 //表示稀疏矩阵 vector>g; public: DenseGraph(int n, bool directed) { this->n = n; this->m = 0; this->directed = directed; //初始化邻接矩阵 for (int i = 0; i < n; i++) { g.push_back(vector(n, false)); } } ~DenseGraph() { } //给图增加一条边，前提是这两个节点之间原来是没有边的 void AddEdge(int a, int b) { //检查越界 assert(a >= 0 && a < n); assert(b >= 0 && b < n); //判断a,b之间是否有边，如果已经存在边，返回 if (hasedge(a, b)) return; //赋值 g[a][b] = true; //判断是否是有向图 if (!directed) { g[b][a] = true; } //维护变量 m++; } //两个节点之间是否存在一条边 bool hasedge(int a, int b) { //检查越界 assert(a >= 0 && a < n); assert(b >= 0 && b < n); return g[a][b]; } //返回图的边数 int E() { return m; } //返回图的点数 int V() { return n; } //展示邻接矩阵图 void show() { cout << "==========DenseGraph===============" << endl; for (int i = 0; i < n; i++) { cout << i << ": "; for (int j = 0; j < n; j++) { cout << g[i][j]<<" "; } cout << endl; } } class adjIterator { private: //定义一个图的引用 DenseGraph &G; //迭代器指向的节点 int v; //当前迭代器指向的索引 int index; public: //初始化引用类型数据成员的唯一机会是在构造函数初始化列表中 adjIterator(DenseGraph &g, int v) :G(g) { this->v = v; this->index = -1; } //迭代器的头 //返回第一个不为false的索引 int begin() { //index 是这个类的属性，只有赋值改变，才会改变，当几点序列改变时，index得初始化 index = -1; return next(); } //迭代器下一个 //返回下一个不为false的索引 int next() { //index 是这个类的属性，只有赋值改变，才会改变 for (index += 1; index < G.V(); index++) { if (G.g[v][index]) { //为了返回下一个不为false的索引，下一次跳入循环后需要index+1,跳过刚刚返回的索引值 return index; } } return -1; } //迭代的结尾 //返回这个图的总点数 int end() { return index >= G.V(); } }; };//稀疏图-邻接表 class SparseGraph { private: //n 表示点，m表示边 int n, m; //判断是否是有向图 int directed; //邻接表 vector>g; public: SparseGraph(int n, int directed) { this->n = n; this->m = 0; this->directed = directed; for (int i = 0; i < n; i++) { //将向量中的元素设为空 g.push_back(vector()); } } ~SparseGraph() { } //给图添加一条边,因为没有考虑平行边，所以该函数可能会导致平行边 void AddEdge(int a, int b) { //检查越界问题 assert(a >= 0 && a < n); assert(b >= 0 && b < n); //如果两点间存在边，则返回，如果加了下列几行代码，则时间复杂度编程O（N），故一般不考虑平行边， //if (hasEdge(a, b)) // return ; //赋值 g[a].push_back(b); //判断是否是自环边，或者是都是有向图，只有非自环边，或者无向图，才满足条件 if (a != b && !directed) g[b].push_back(a); m++; } //判断是否两点是否存在边 bool hasEdge(int a, int b) { //检查越界问题 assert(a >= 0 && a < n); assert(b >= 0 && b < n); for (int i = 0; i < g[a].size(); i++) { if (g[a][i] == b) { return true; } } return false; } //返回图的边数 int E() { return m; } //返回图的点数 int V() { return n; } //展示图 void show() { cout << "==========SparseGraph===============" << endl; for (int i = 0; i < n; i++) { cout << i << ": "; for (int j = 0; j < g[i].size(); j++) { cout << g[i][j] << " "; } cout << endl; } } //邻接表的迭代器类 class adjIterator { private: SparseGraph &G; //当前迭代器节点的索引 int v; //当前迭代器节点中的索引 int index; public: //初始化引用类型的数据成员，只能在构造函数的初始化列表中初始化 adjIterator(SparseGraph &g, int v) :G(g) { this->v = v; this->index = 0; } //迭代器的开始，返回当前节点中的第一个索引 int begin() { //对于后面的节点，begin必须将index初始化为0才行 index = 0; //此处不应该是G.V(),应该是对应每个节点中的多少个索引 if (G.g[v].size()) return G.g[v][index]; //return -1; } //迭代器的迭代，返回当前节点中下一个索引 int next() { index++; //此处不应该是G.V(),应该是对应每个节点中的多少个索引 if (index < G.g[v].size()) return G.g[v][index]; //return -1; } //迭代器的接受 int end() { return index >= G.g[v].size(); } }; };//适用于稀疏图和稠密图的泛型读图编程实现template class ReadGraph{public: ReadGraph(Graph &g,const string &filetxt) { //读取文件 ifstream file(filetxt); //存储文件每行的数据 string line; int V, E; //确认文件是否打开 assert(file.is_open()); //将文件的第一行读取到line中，确认是否读取成功 assert(getline(file, line)); //将第一行输入到stringstream中，解析出变量V，E，即文件中开头第一行给出的string stringstream ss(line); ss >> V >> E; //检查读取的点数和引用图的点数是否是一致的 assert(g.V() == V); for (int i = 0; i < E; i++) { //读取下一行 assert(getline(file, line)); stringstream ss(line); int a, b; ss >> a >> b; //如果a,b不越界 assert(a >= 0 && a < V); assert(b >= 0 && b < V); g.AddEdge(a, b); } }private:};//适用于稀疏图和稠密图的深度优先遍历，可得出连通分量数template class Component {private: //为了存储一份图 Graph &G; //记录每一个指针是否被访问过 bool *visited; //记录多少个连通分量 int ccount; //记录图中连接 int *unionfind; //深度优先遍历 void dfs(int v) { visited[v] = true; //每个连通分量一个连接，用ccount最为合适 unionfind[v] = ccount; typename Graph::adjIterator iterator(G, v); for (int i = iterator.begin(); !iterator.end(); i = iterator.next()) { if (!visited[i]) { dfs(i); } } }public: Component(Graph & graph):G(graph) { visited = new bool[G.V()]; unionfind = new int[G.V()]; ccount = 0; for (int i = 0; i < G.V(); i++) { visited[i] = false; unionfind[i] = -1; } for(int i=0;i= 0 && v < G.V()); assert(w >= 0 && w < G.V()); return unionfind[v] == unionfind[w]; } };//通过图的深度优先遍历，得到图的某点到另一个点的路径，并打印出来template class Path {private: //图的引用 Graph&G; //这个点到其他点的路径 int s; //表示点是否被遍历过 bool *visited; //from[i] 表示i节点是由from[i]得到 int *from;public: Path(Graph&graph,int s):G(graph) { assert(s >= 0 && s < G.V()); visited = new bool[G.V()]; from = new int[G.V()]; this->s = s; for (int i = 0; i < G.V(); i++) { visited[i] = false; from[i] = -1; } dfs(s); } ~Path() { delete[] visited; delete[] from; } //判断s与w之间是否有路 bool haspath(int w) { assert(w >= 0 && w < G.V()); return visited[w]; } //s与w之间是一个怎样的路径,存在vector 中 void path(int w, vector&vec) { //因为希望打印出来是从s到w,但是索引只能从w->s，所以需要用到栈 stack st; while (w!=-1) { //当由from[w]迭代过来的w=-1的前一个时，则w=s，则s也存入 st.push(w); w = from[w]; } //初始化vec vec.clear(); //将栈的元素转到向量的元素 while (!st.empty()) { vec.push_back(st.top()); st.pop(); } } //打印出s与w之间的路径 void showpath(int w) { vector vec; path(w, vec); cout << s<<"->"<= 0 && v < G.V()); visited[v] = true; //利用迭代器访问稀疏图，稠密图节点中的元素 typename Graph::adjIterator iterator(G, v); for (int i = iterator.begin(); !iterator.end(); i = iterator.next()) { //如果i没有被访问，则从i递归下去，直到访问完为止 if (!visited[i]) { from[i] = v; dfs(i); } } }};//无权图的广度优先遍历得出无向图最短路径 template class Shortpath {private: //图的引用 Graph&G; //这个点到其他点的路径 int s; //表示点是否被遍历过 bool *visited; //from[i] 表示i节点是由from[i]得到 int *from; //记录s到其他点的最短距离 int *ord;public: Shortpath(Graph &graph, int s) :G(graph) { assert(s >= 0 && s < G.V()); this->s = s; visited = new bool[G.V()]; from = new int[G.V()]; ord = new int[G.V()]; for (int i = 0; i < G.V(); i++) { visited[i] = false; from[i] = -1; ord[i] = -1; } //无向图最短路径算法 //使用一个队列 queueq; q.push(s); visited[s] = true; ord[s] = 0; while (!q.empty()) { //提取队首元素，有返回值 int v = q.front(); //弹出队首，无返回值 q.pop(); //利用迭代器访问稀疏图，稠密图节点中的元素 typename Graph::adjIterator iterator(G, v); for (int i = iterator.begin(); !iterator.end(); i = iterator.next()) { //如果i没有被访问， if (!visited[i]) { //在队尾加入元素 q.push(i); visited[i] = true; //广度优先遍历，通过from，找到最短路径 from[i] = v; //经过一条路径加1 ord[i] = ord[v] + 1; } } } } ~Shortpath() { delete[] visited; delete[] from; delete[] ord; } //判断s与w之间是否有路 bool haspath(int w) { assert(w >= 0 && w < G.V()); return visited[w]; } //s与w之间是一个怎样的路径,存在vector 中 void path(int w, vector&vec) { //因为希望打印出来是从s到w,但是索引只能从w->s，所以需要用到栈 stack st; while (w != -1) { //当由from[w]迭代过来的w=-1的前一个时，则w=s，则s也存入 st.push(w); w = from[w]; } //初始化vec vec.clear(); //将栈的元素转到向量的元素 while (!st.empty()) { vec.push_back(st.top()); st.pop(); } } //打印出s与w之间的路径 void showpath(int w) { vector vec; path(w, vec); cout << s << "->" << w << " :"; //vec中元素的打印 for (int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << endl; } //返回s到w的最短路径长度 int length(int w) { assert(w >= 0 && w < G.V()); return ord[w]; }};

测试代码

#include#include#include #include "Graph.h"#include //文件操作用到的库#include#include using namespace std;int main(){ string filetext_0= "testG1.txt"; //读取的文件有13个节点，不是有向图 DenseGraph g1(13, false); ReadGraph readgraph(g1, filetext_0); //跟后面迭代器一样的功能，用来显示打印图 g1.show(); //迭代器方式的输出 cout << "=======迭代器方式的输出========" << endl; for (int i = 0; i < g1.V(); i++) { cout << i << ": "; DenseGraph::adjIterator iterator(g1, i); for (int j = iterator.begin(); !iterator.end(); j = iterator.next()) { cout << j << " "; } cout << endl; } //路径的起点 int s = 0; //路径的终点 int w = 4; PathDenseGraph_p(g1, s); DenseGraph_p.showpath(w); cout << "============================" << endl; Componentc_1(g1); cout << "DenseGraph的连通分量" << c_1.count() << endl; cout << "11 和 12是否相连" << c_1.isConnected(11, 12)< DenseGraph_sp(g1, s); DenseGraph_sp.showpath(w); cout << "路径长度：" << DenseGraph_sp.length(w) << endl; string filetext_1 = "testG2.txt"; SparseGraph g2(6, false); ReadGraph readgraph_1(g2, filetext_1); //跟后面迭代器一样的功能，用来显示打印图 g2.show(); //迭代器方式的输出 cout << "=======迭代器方式的输出========" << endl; for (int i = 0; i < g2.V(); i++) { cout << i << " : "; SparseGraph::adjIterator iterator(g2, i); for (int j = iterator.begin(); !iterator.end(); j = iterator.next()) { cout << j << " "; } cout << endl; } Componentc_2(g2); cout << "SparseGraph的连通分量" << c_2.count() << endl; //路径的起点 int s_1 = 4; //路径的终点 int w_1 = 5; Path SparseGraph_p(g2, s_1); SparseGraph_p.showpath(w_1); cout << "====无向无权图的两点之间最短路径=======" << endl; Shortpath SparseGraph_sp(g2, s_1); SparseGraph_sp.showpath(w_1); cout<<"路径长度："<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。