1.图的2种常用存储方式
邻接矩阵，即用二维数组表示，i->j的点1（true）代表右边，0（false）无边。邻接表 常用的一个数组，数组中的每一个都变为单链表的形式。2.图的遍历
深度优先遍历 深度优先遍历，为了防止节点被重复访问，增加对应的一个标志的二维数组，每次访问之前，判断是否被访问过，没访问过即能访问，访问过就不能再次访问。 能解决连通量的个数，变种是小岛的数量。 深度遍历思路： 1.先从v顶点出发，访问v. 2.再访问v的邻接未被访问的节点，再从新的节点开始，继续访问新的邻接未被访问的节点，依次类推。直到访问过的节点再也没有未被访问的节点为止。 3.如果当前节点再也没有未被访问过的邻接点，那么回退到上一次的节点，看上一次的节点周围还有未被访问过的节点，有则就访问，没有，就继续回退到上一次的节点。重复2,3. 4.直到图中所有节点都被访问，搜索结束。 深度优先搜索连通图 bool visited[num]; void DFS(Graph G,int v){ //从第v个顶点出发递归地深度搜索图G cout<< v; visited[v] = true; for(w = FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) //依次检查v的有所邻接点w，FirstAdjVex(G,v)表示v第一个邻接点 //NextAdjVex(G,v,w)表示v相对于w的下一个邻接点，w>=0表示存在邻接点 if(!visited[w]) DFS(G，w); //对v尚未访问过的邻接顶点w递归调用dfs }深度优先搜索遍历非连通图
void DFSTraverse(Graph G) { //对非连通图G做深度优先遍历 for(v=0;v<G.vexnum;++v) visited[v] = false; //访问标志数组初始化 for(v = 0;v<G.verxnum;++v) //循环调用访问连通图的方法 if(!visited[v]) DFS(G,v);邻接矩阵表示图的深度优先遍历搜索
void DFS_AM(AMGraph G,int v){ //从v顶点开始深度搜索遍历G cout<<v; visited[v] = true; for(w = 0;w<G.vexnum;w++){ //依次检查邻接矩阵v的行 if((G.arcs[v][w]!=0)&&(!visited[w])) DFS_AM(G,w); //G.arcs[v][w]!=0表示w是v的邻接点，如果w未访问，则递归调用dfs_am邻接表表示图的深度遍历
void DFS_AL(ALGraph G,int v) { //从v开始 cout<<v; visited[v] = true; p = G.vertices[v].firstarc; //p指向v的边链表的第一个边节点 while(p!=NULL) //边节点非空 { w = p->adjvex; //表示w是v的邻接点 if(!visited[w]) DFS_AL(G,w); p = p->nextarc; /p指向下一个 广度优先遍历 广度优先遍历，则是用来寻找最短路径，因为根据广度优先搜索，先找自己节点的附近的，再逐渐往深入。 广度搜索类似树的层序遍历,需要用队列来保存。 广度优先遍历连通图 void BFS(Graph G,int v){ //广度优先非递归遍历G cout<<v; visited[v] = true; INitQueue(q); //初始化队列 EnQueue(Q,v); //v进队 while(!QueueEmpty(Q)) //队列非空 { DeQueue(Q,u); //队头元素出队置u for(w = FirstAdjVex(G,u);w>=0;w = NextAdjVex(G,u,w)) //依次检查u的所有邻接点w,FirstAdjVex(G,u)表示u第一个邻接点 //NextAdjVex(G,u,w)表示u相对于w的下一邻接点，w>=0表示存在邻接点 if(!visited[w]) //w为u的尚未访问的邻接点 { cout<<w; visited[w] = true; // EnQueue(Q,w); } } }邻接表
// // Created by Administrator on 2019/5/24. // #ifndef INC_06_FINDING_A_PATH_SPARSEGRAPH_H #define INC_06_FINDING_A_PATH_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[i]都为空, 即没有任和边 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][i] == w ) return true; return false; } // 显示图的信息 void show(){ for( int i = 0 ; i < n ; i ++ ){ cout<<"vertex "<<i<<":\t"; for( int j = 0 ; j < g[i].size() ; j ++ ) cout<<g[i][j]<<"\t"; cout<<endl; } } // 邻边迭代器, 传入一个图和一个顶点, // 迭代在这个图中和这个顶点向连的所有顶点 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 //INC_06_FINDING_A_PATH_SPARSEGRAPH_H邻接矩阵
#ifndef INC_06_FINDING_A_PATH_DENSEGRAPH_H #define INC_06_FINDING_A_PATH_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[i][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]; } // 显示图的信息 void show(){ for( int i = 0 ; i < n ; i ++ ){ for( int j = 0 ; j < n ; j ++ ) cout<<g[i][j]<<"\t"; cout<<endl; } } // 邻边迭代器, 传入一个图和一个顶点, // 迭代在这个图中和这个顶点向连的所有顶点 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 //INC_06_FINDING_A_PATH_DENSEGRAPH_H #ifndef INC_06_FINDING_A_PATH_READGRAPH_H #define INC_06_FINDING_A_PATH_READGRAPH_H #include <iostream> #include <string> #include <fstream> #include <sstream> #include <cassert> using namespace std; // 读取图算法 template <typename Graph> class ReadGraph{ public: // 从文件filename中读取图的信息, 存储进图graph中 ReadGraph(Graph &graph, const string &filename){ ifstream file(filename); string line; int V, E; assert( file.is_open() ); // 第一行读取图中的节点个数和边的个数 assert( getline(file, line) ); stringstream ss(line); ss>>V>>E; assert( V == graph.V() ); // 读取每一条边的信息 for( int i = 0 ; i < E ; i ++ ){ assert( getline(file, line) ); stringstream ss(line); int a,b; ss>>a>>b; assert( a >= 0 && a < V ); assert( b >= 0 && b < V ); graph.addEdge( a , b ); } } }; #endif //INC_06_FINDING_A_PATH_READGRAPH_H计算路径，点与点之间的长度，能否到达
#ifndef INC_06_FINDING_A_PATH_PATH_H #define INC_06_FINDING_A_PATH_PATH_H #include <vector> #include <stack> #include <iostream> #include <cassert> using namespace std; // 路径查询 template <typename Graph> class Path{ private: Graph &G; // 图的引用 int s; // 起始点 bool* visited; // 记录dfs的过程中节点是否被访问 int * from; // 记录路径, from[i]表示查找的路径上i的上一个节点 // 图的深度优先遍历 void dfs( int v ){ visited[v] = true; typename Graph::adjIterator adj(G, v); for( int i = adj.begin() ; !adj.end() ; i = adj.next() ){ if( !visited[i] ){ from[i] = v; dfs(i); } } } public: // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径 Path(Graph &graph, int s):G(graph){ // 算法初始化 assert( s >= 0 && s < G.V() ); visited = new bool[G.V()]; from = new int[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ){ visited[i] = false; from[i] = -1; } this->s = s; // 寻路算法 dfs(s); } // 析构函数 ~Path(){ delete [] visited; delete [] from; } // 查询从s点到w点是否有路径 bool hasPath(int w){ assert( w >= 0 && w < G.V() ); return visited[w]; } // 查询从s点到w点的路径, 存放在vec中 void path(int w, vector<int> &vec){ assert( hasPath(w) ); stack<int> s; // 通过from数组逆向查找到从s到w的路径, 存放到栈中 int p = w; while( p != -1 ){ s.push(p); p = from[p]; } // 从栈中依次取出元素, 获得顺序的从s到w的路径 vec.clear(); while( !s.empty() ){ vec.push_back( s.top() ); s.pop(); } } // 打印出从s点到w点的路径 void showPath(int w){ assert( hasPath(w) ); vector<int> vec; path( w , vec ); for( int i = 0 ; i < vec.size() ; i ++ ){ cout<<vec[i]; if( i == vec.size() - 1 ) cout<<endl; else cout<<" -> "; } } }; #endif //INC_06_FINDING_A_PATH_PATH_H广度搜索最短路径
// // Created by Administrator on 2019/5/24. // #ifndef DEMOGRAPH_SHORTESTPATH_H #define DEMOGRAPH_SHORTESTPATH_H #include <iostream> #include <cassert> #include "queue" #include "stack" using namespace std; template <typename Graph> class ShortestPath{ private: Graph &G; int s; bool *visited; int *from; int *ord; //从s 到每一个i的最短距离 public: ShortestPath(Graph &graph,int s):G(graph){ //算法初始化 assert(s>=0&&s<graph.V()); visited = new bool[graph.V()]; from = new int[graph.V()]; ord = new int[graph.V()]; for(int i=0;i<graph.V();i++){ visited[i] = false; from[i] = -1; ord[i] = 1; } this->s = s; queue<int> q; //无向图最短路径算法 q.push(s); visited[s] = true; //自己到自己最短 ord[s] = 0; while(!q.empty()){ int v = q.front(); q.pop(); typename Graph::adjIterator adj(G,v); for(int i=adj.begin();!adj.end();i = adj.next()){ if(!visited[i]){ q.push(i); visited[i] = true; //为啥是这样 from[i] = v; //为啥是这样 ord[i] = ord[v]+1; } } } } ~ShortestPath(){ delete [] visited; delete [] from; delete [] ord; } //查询从s到w是否有路径 bool hasPath(int w){ assert(w>=0&&w<G.V()); return visited[w]; } //查询从s到w点的路径，存放在Vec中 void path(int w, vector<int> &vec){ assert( w >= 0 && w < G.V() ); stack<int> s; // 通过from数组逆向查找到从s到w的路径, 存放到栈中 int p = w; while( p != -1 ){ s.push(p); p = from[p]; } // 从栈中依次取出元素, 获得顺序的从s到w的路径 vec.clear(); while( !s.empty() ){ vec.push_back( s.top() ); s.pop(); } } //打印出从s到w点的路径 void showPath(int w){ assert( w >= 0 && w < G.V() ); vector<int> vec; path(w, vec); for( int i = 0 ; i < vec.size() ; i ++ ){ cout<<vec[i]; if( i == vec.size()-1 ) cout<<endl; else cout<<" -> "; } } //查看从s到w点的最短路径长度 int length(int w){ assert( w >= 0 && w < G.V() ); return ord[w]; } }; #endif //DEMOGRAPH_SHORTESTPATH_H