1. 图相干的算法
图中一个最常见的利用是，通过一个点遍历它的临边。
（1）毗邻矩阵：时间复杂度为O(V)。
（2）毗邻表：由于每一行原来存储的就是毗连的点，以是可以直接找到。
固然，以上利用将g这个图设置成public变量就可以实现，但是怎样维护g仍旧为private变量呢？由于，如许从筹划模式角度来讲是更好的，外界用户无法修改g这个图，固然可以利用一个函数，但是必要将数据复制一份，如许不是太好的，更好的方法呢？
利用迭代器。
迭代器将详细实现隐藏了，如许希奇图和稠密图的接口就可以保持划一。
代码如下：
SparseGraph.h
#ifndef VERTEX_ADJACENT_ITERATOR_SPARSEGRAPH_H#define VERTEX_ADJACENT_ITERATOR_SPARSEGRAPH_H#include <iostream>#include <vector>#include <cassert>using namespace std;// 希奇图 - 毗邻表class SparseGraph{private: int n, m; // 节点数和边数 bool directed; // 是否为有向图 vector<vector<int>> g; // 图的详细数据public: // 构造函数 SparseGraph( int n , bool directed ){ assert( n >= 0 ); this->n = n; this->m = 0; // 初始化没有任何边 this->directed = directed; // g初始化为n个空的vector, 表现每一个g都为空, 即没有任和边 g = vector<vector<int>>(n, vector<int>()); } ~SparseGraph(){ } int V(){ return n;} // 返回节点个数 int E(){ return m;} // 返回边的个数 // 向图中添加一个边 void addEdge( int v, int w ){ assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); g[v].push_back(w); if( v != w && !directed ) g[w].push_back(v); m ++; } // 验证图中是否有从v到w的边 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] == w ) return true; return false; } // 邻边迭代器, 传入一个图和一个顶点, // 迭代在这个图中和这个顶点向连的全部顶点 class adjIterator{ private: SparseGraph &G; // 图G的引用 int v; int index; public: // 构造函数 adjIterator(SparseGraph &graph, int v): G(graph){ this->v = v; this->index = 0; } ~adjIterator(){} // 返回图G中与顶点v相毗连的第一个顶点 int begin(){ index = 0; if( G.g[v].size() ) return G.g[v][index]; // 若没有顶点和v相毗连, 则返回-1 return -1; } // 返回图G中与顶点v相毗连的下一个顶点 int next(){ index ++; if( index < G.g[v].size() ) return G.g[v][index]; // 若没有顶点和v相毗连, 则返回-1 return -1; } // 检察是否已经迭代完了图G中与顶点v相毗连的全部顶点 bool end(){ return index >= G.g[v].size(); } };};#endif //VERTEX_ADJACENT_ITERATOR_SPARSEGRAPH_HDenseGraph.h
#ifndef VERTEX_ADJACENT_ITERATOR_DENSEGRAPH_H#define VERTEX_ADJACENT_ITERATOR_DENSEGRAPH_H#include <iostream>#include <vector>#include <cassert>using namespace std;// 稠密图 - 毗邻矩阵class DenseGraph{private: int n, m; // 节点数和边数 bool directed; // 是否为有向图 vector<vector<bool>> g; // 图的详细数据public: // 构造函数 DenseGraph( int n , bool directed ){ assert( n >= 0 ); this->n = n; this->m = 0; // 初始化没有任何边 this->directed = directed; // g初始化为n*n的布尔矩阵, 每一个g[j]均为false, 表现没有任和边 g = vector<vector<bool>>(n, vector<bool>(n, false)); } ~DenseGraph(){ } int V(){ return n;} // 返回节点个数 int E(){ return m;} // 返回边的个数 // 向图中添加一个边 void addEdge( int v , int w ){ assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); if( hasEdge( v , w ) ) return; g[v][w] = true; if( !directed ) g[w][v] = true; m ++; } // 验证图中是否有从v到w的边 bool hasEdge( int v , int w ){ assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); return g[v][w]; } // 邻边迭代器, 传入一个图和一个顶点, // 迭代在这个图中和这个顶点向连的全部顶点 class adjIterator{ private: DenseGraph &G; // 图G的引用 int v; int index; public: // 构造函数 adjIterator(DenseGraph &graph, int v): G(graph){ assert( v >= 0 && v < G.n ); this->v = v; this->index = -1; // 索引从-1开始, 由于每次遍历都必要调用一次next() } ~adjIterator(){} // 返回图G中与顶点v相毗连的第一个顶点 int begin(){ // 索引从-1开始, 由于每次遍历都必要调用一次next() index = -1; return next(); } // 返回图G中与顶点v相毗连的下一个顶点 int next(){ // 从当前index开始向后搜索, 直到找到一个g[v][index]为true for( index += 1 ; index < G.V() ; index ++ ) if( G.g[v][index] ) return index; // 若没有顶点和v相毗连, 则返回-1 return -1; } // 检察是否已经迭代完了图G中与顶点v相毗连的全部顶点 bool end(){ return index >= G.V(); } };};#endif //VERTEX_ADJACENT_ITERATOR_DENSEGRAPH_Hmain.cpp
#include <iostream>#include "SparseGraph.h"#include "DenseGraph.h"using namespace std;int main() { int N = 20; int M = 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) 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; } return 0;} |
