------------------------siwuxie095
相邻点迭代器
在图算法中，有一个很常见的操作，即 通过一个点来遍历这个点
相关的邻边
「遍历邻边，图算法中最常见的操作」
不难想象，只有使用这样的方式才能逐渐的将一个图中的所有信
息都收集完，从而进行进一步的计算，那么通过一个点怎么遍历
它所有的邻边呢？
看如下实例：
在这张图中，点 0 有三个邻边，分别连接点 3、5、8
在实现时，有两种实现方式：
（1）对于邻接矩阵，要想找到顶点 0 所有的邻边和相邻的顶点，就要
将这张图中的所有顶点全都遍历一遍。如果为 0，说明不相邻，如果为
1，说明相邻。换言之，在邻接矩阵的实现中，该操作要花 O(V) 的时
间（V 是图中的顶点个数）
（2）对于邻接表，就非常容易了。因为邻接表中，0 这一行存的就是
所有和 0 相邻的顶点，即 能以最小的代价找到和 0 相邻的所有顶点
这也是邻接表的实现方式的优势所在，而且在实际的处理中，大多数图
都是稀疏图。在这种情况下，使用邻接表来存储图，由于遍历邻边更加
高效，使得图算法整体也更加高效
「遍历邻边，其实也是遍历相邻的顶点」
程序：
SparseGraph.h：
#ifndef SPARSEGRAPH_H #define SPARSEGRAPH_H
#include <iostream> #include <vector> #include <cassert> using namespace std;
// 稀疏图 - 邻接表 class SparseGraph {
private:
int n, m; //n 和 m 分别表示顶点数和边数 bool directed; //directed表示是有向图还是无向图 vector<vector<int>> g; //g[i]里存储的就是和顶点i相邻的所有顶点
public:
SparseGraph(int n, bool directed) { //初始化时，有n个顶点，0条边 this->n = n; this->m = 0; this->directed = directed; //g[i]初始化为空的vector for (int i = 0; i < n; i++) { g.push_back(vector<int>()); } }
~SparseGraph() {
}
int V(){ return n; } int E(){ return m; }
//在顶点v和顶点w之间建立一条边 void addEdge(int v, int w) {
assert(v >= 0 && v < n); assert(w >= 0 && w < n);
g[v].push_back(w); //（1）顶点v不等于顶点w，即 不是自环边 //（2）且不是有向图，即 是无向图 if (v != w && !directed) { g[w].push_back(v); }
m++; }
//hasEdge()判断顶点v和顶点w之间是否有边 //hasEdge()的时间复杂度：O(n) bool hasEdge(int v, int w) {
assert(v >= 0 && v < n); assert(w >= 0 && w < n);
for (int i = 0; i < g[v].size(); i++) { if (g[v][i] == w) { return true; } }
return false; }
//相邻点迭代器（相邻，即 adjacent） // //使用迭代器可以隐藏迭代的过程，按照一定的 //顺序访问一个容器中的所有元素 class adjIterator { private:
SparseGraph &G; //图的引用，即 要迭代的图 int v; //顶点v int index; //相邻顶点的索引
public:
adjIterator(SparseGraph &graph, int v) : G(graph) { this->v = v; this->index = 0; }
//要迭代的第一个元素 int begin() { //因为有可能多次调用begin()， //所以显式的将index设置为0 index = 0; //如果g[v]的size()不为0 if (G.g[v].size()) { return G.g[v][index]; }
return -1; }
//要迭代的下一个元素 int next() { index++; if (index < G.g[v].size()) { return G.g[v][index]; }
return -1; }
//判断迭代是否终止 bool end() { return index >= G.g[v].size(); } }; };
//事实上，平行边的问题，就是邻接表的一个缺点 // //如果要在addEdge()中判断hasEdge()，因为hasEdge()是O(n)的复 //杂度，那么addEdge()也就变成O(n)的复杂度了 // //由于在使用邻接表表示稀疏图时，取消平行边（即 在addEdge() //中加上hasEdge()），相应的成本比较高 // //所以，通常情况下，在addEdge()函数中就先不管平行边的问题， //也就是允许有平行边。如果真的要让图中没有平行边，就在所有 //边都添加进来之后，再进行一次综合的处理，将平行边删除掉
#endif |
DenseGraph.h：
#ifndef DENSEGRAPH_H #define DENSEGRAPH_H
#include <iostream> #include <vector> #include <cassert> using namespace std;
// 稠密图 - 邻接矩阵 class DenseGraph {
private:
int n, m; //n 和 m 分别表示顶点数和边数 bool directed; //directed表示是有向图还是无向图 vector<vector<bool>> g; //二维矩阵，存放布尔值，表示是否有边
public:
DenseGraph(int n, bool directed) { //初始化时，有n个顶点，0条边 this->n = n; this->m = 0; this->directed = directed; //二维矩阵：n行n列，全部初始化为false for (int i = 0; i < n; i++) { g.push_back(vector<bool>(n, false)); } }
~DenseGraph() {
}
int V(){ return n; } int E(){ return m; }
//在顶点v和顶点w之间建立一条边 void addEdge(int v, int w) {
assert(v >= 0 && v < n); assert(w >= 0 && w < n);
//如果顶点v和顶点w之间已经存在一条边， //则直接返回，即排除了平行边 if (hasEdge(v, w)) { return; }
g[v][w] = true; //如果是无向图，则g[w][v]处也设为true（无向图沿主对角线对称） if (!directed) { g[w][v] = true; }
m++; }
//hasEdge()判断顶点v和顶点w之间是否有边 //hasEdge()的时间复杂度：O(1) bool hasEdge(int v, int w) { assert(v >= 0 && v < n); assert(w >= 0 && w < n); return g[v][w]; }
//相邻点迭代器（相邻，即 adjacent） class adjIterator { private:
DenseGraph &G; //图的引用，即 要迭代的图 int v; //顶点v int index; //相邻顶点的索引
public:
adjIterator(DenseGraph &graph, int v) : G(graph) { this->v = v; this->index = -1; }
//要迭代的第一个元素 int begin() { //找第一个为true的元素，即为要迭代的第一个元素 index = -1; return next(); }
//要迭代的下一个元素 int next() { for (index += 1; index < G.V(); index++) { if (G.g[v][index]) { return index; } }
return -1; }
//判断迭代是否终止 bool end() { return index >= G.V(); } }; };
//addEdge()函数隐含着：当使用邻接矩阵表示稠密图时，已经 //不自觉的将平行边给去掉了，即 在添加边时，如果发现已经 //存在该边，就不做任何操作，直接返回即可 // //事实上，这也是使用邻接矩阵的一个优势可以非常方便的处理 //平行边的问题 // //另外，由于使用的是邻接矩阵，可以非常快速的用O(1)的方式， //来判断顶点v和顶点w之间是否有边
#endif |
main.cpp：
#include "SparseGraph.h" #include "DenseGraph.h" #include <iostream> #include <ctime> using namespace std;
int main() {
int N = 20; //20个顶点 int M = 100; //100条边 srand(time(NULL));
// Sparse Graph：随机生成一张稀疏图 //（因为实现中没有过滤平行边，所以 //有可能存在平行边） SparseGraph g1(N, false); for (int i = 0; i < M; i++) { int a = rand() % N; int b = rand() % N; g1.addEdge(a, b); }
// 打印所有的邻边，时间复杂度：O(E) //即 有多少边就遍历多少次 for (int v = 0; v < N; v++) { cout << v << " : "; //对于每一个顶点都声明一个相邻点迭代器 SparseGraph::adjIterator adj(g1, v); for (int w = adj.begin(); !adj.end(); w = adj.next()) { cout << w << " "; } cout << endl; }
cout << endl;
// Dense Graph：随机生成一张稠密图 DenseGraph g2(N, false); for (int i = 0; i < M; i++) { int a = rand() % N; int b = rand() % N; g2.addEdge(a, b); }
// 打印所有的邻边，时间复杂度：O(V^2)， //如果V^2远远大于E的话，就能看出来这种 //稀疏图的实现的优势 for (int v = 0; v < N; v++) { cout << v << " : "; DenseGraph::adjIterator adj(g2, v); for (int w = adj.begin(); !adj.end(); w = adj.next()) { cout << w << " "; } cout << endl; }
system("pause"); return 0; }
//原本的实现思路： //最简单的方式其实是将DenseGraph和SparseGraph类中的 g 的访问控制符， //由 private 改成 public，在外面就可以直接对 g 的某一行进行循环，就 //已经实现了遍历邻边的功能 // //但它的缺点就是将 g 这个数据暴露在了外面，外面的调用用户就有可能不 //经意间修改 g，导致产生奇怪的 bug，当然如果大家只是写一些小的算法， //或者应付面试中的一个算法的实现，这样实现就完全够了 // // // //现在的实现思路： //保持 g 本身还是 private，借助迭代器让外面能够遍历 //（PS：如果不用迭代器，也可以写一个函数，直接要到某一个顶点的所有 //相邻顶点，但这样做的缺点是:不得不要把 g 的某一行复制一份，这也是 //不够好的，所以这里借助迭代器的思想） // // //之所以设置这样的一个迭代器，还有一个非常重要的意义，就是将稀疏图 //和稠密图这两个类里面的具体实现屏蔽了，而从用户的角度看，它们呈现 //给外面的接口是完全一样的，这为后续实现图相关的算法带来了方便 // //每一个图的算法都将对稀疏图和稠密图同时成立，因为都是调用同样的接 //口，换句话说，图算法都将封装在模板类中，那么这个模板就可以任意的 //传入稀疏图或稠密图 |
【made by siwuxie095】