【2019暑假刷题笔记-图的存储和图的遍历】绪论（代码模板-总结自《算法笔记》）

一、图的存储

图有两种存储办法，分别是邻接矩阵(顶点数≤1000，0表示不连通，数字表示权重)和邻接表(用vector数组实现)，具体实现如下： /* 邻接矩阵，G[][] */G[2][3]=1; //2和3连接（可以认为权重为1） G[4][5]=0; //4和5不连接 G[7][8]=6; //7和8连接且权重为6 /* 邻接表 vector<int> Adj[N]; */Adj[1].push_back(3); //1和3连接//邻接表加权重 struct Node{int v; //边的终点编号int w; //边权 }; vector<Node> Adj[N]; //这样vector的邻接表的类型就是Node了Node temp; temp.v=3; temp.w=4; Adj[1].push_back(temp);//邻接表的另一种构造 struct Node{int v,w;Node(int_v,int_w):v(_v),w(_w){}; //构造函数 };Adj[1].push_back(Node(3,4));

以DFS法遍历图：

/* 伪码思想：不管是邻接表还是邻接矩阵都是采用这种办法的（注：连通图一次DFS解决） */ DFS(u){ //访问定点uvis[u]=true; //设置u被访问过了for(从u出发能到达的所有顶点v) //枚举从u出发的所有顶点vif vis[v]==false //如果v没有被访问过DFS(v); }DFSTrave(G){ //遍历Gfor(G的所有顶点u) //对G的所有顶点uif vis[u]==false //如果u未被访问DFS(u); //访问u所在的连通块 } /* 邻接矩阵版DFS *///首先定义MAXV为最大顶点数、INF为一个很大的数字 const int MAXV=1000; const int INF=1000000000;int n,G[MAXV][MAXV]; //n为顶点数，MAXV为最大顶点数 bool vis[MAXV]={false}; void DFS(int u,int depth){vis[u]=true; //设置u已被访问//如果需要对u进行一些操作，可以在这里进行//下面对所有从u出发能到达的分支顶点进行枚举for(int v=0;v<n;v++){ //对每个顶点vif(vis[v]==false&&G[u][v]!=INF){ //如果v没有被访问且u可以达到vDFS(v,depth+1); //访问v，深度加1}} }void DFSTrave(){ //遍历图Gfor(int u=0;u<n;u++){ //对每个顶点uif(vis[u]==false){ //若u没有被访问过DFS(n,1); //访问u和u所在的连通块，1表示初试的第一层}} } /* 邻接表版 */ const int MAXV=1000; vector<int> Adj[MAXV]; //图G的邻接表 int n; //n为顶点数，MAXV为最大顶点数 bool vis[MAXV]={false}; //若顶点i已经被访问过了，则vis[i]==true.初值为falsevoid DFS(int u,int depth){ //u为当前访问的顶点标号，depth为深度vis[u]=true; //设置u已经被访问//如果需要对u进行一些操作，可以在此处进行for(int i=0;i<Adj[u].size();i++){ //对从u出发可以到达的所有顶点vint v=Adj[u][i];if(vis[v]==false){ //若v没有被访问过DFS(v,depth+1); //访问v，深度+1}} }void DFSTrave(){ //遍历图Gfor(int u=0;u<n;u++){ //对每个顶点uif(vis[u]==false){ //若u未被访问DFS(u,1); //访问u和u所在的联通块，1表示初始值为第一层}} }

 

以BFS法遍历图：

/* 伪码思想 */ BFS(u){ //遍历u所在的连通块queue q;将u入队；inq[u]=true; //设置u已经被加入过队列while(q非空){ //只要队列非空取出q的队首元素u进行访问for(u出发可达的所有顶点v){ //枚举从u所能直接到达的顶点vif(inq[v]==false){ //若v未曾加入过队列将v入队inq[v]=true; //设置v已被加入过队列}}} }BFSTrave(){ //遍历图Gfor(G的所有顶点u) //枚举G的所有顶点uif(inq[u]==false){ //若u未曾加入过队列BFS(G); //遍历u所在的连通块} } /* 邻接矩阵版 */ int n,G[MAXV][MAXV]; //n为顶点数，MAXV为最大顶点数 bool inq[MAXV]=false; //若顶点i曾入过队列，则inq[i]==true。初值为falsevoid BFS(int u){ //遍历u所在的连通块queue<int> q; //定义队列qq.push(u); //将初始点u入队inq[u]=true; //设置u已经进入过队列while(!q.empty()){ //只要队列非空int u=q.front(); //取出队首元素q.pop(); //将队首元素出队for(int v=0;v<n;v++){ if(inq[v]==false&&G[u][v]!=INF){ //若u的邻接点v未曾加入过队列q.push(v); //将v入队inq[v]=true; //标记v为已经被加入过队列}}} }void BFSTrave(){ //遍历图Gfor(int u=0;u<n;u++){ //枚举所有顶点if(inq[u]==false){ //若u未曾加入过队列BFS(q); //遍历u所在连通块}} } /* 邻接表版 */ vector<int> Adj[MAXV]; //图G，Adj[u]存放从顶点u出发可以到达的所有顶点 int n; //n为顶点数，MAXV为最大顶点数 bool inq[MAXV]={false}; //若顶点i曾入过队列，则inq[i]==true。初值为falsevoid BFS(int u){ //遍历u所在的连通块queue<int> q; //定义队列qq.push(u); //将初始点u入队inq[u]=true; //设置u已经进入过队列while(!q.empty()){ //只要队列非空int u=q.front(); //取出队首元素q.pop(); //将队首元素出队for(int i=0;i<Adj[u].size();i++){ //枚举从u出发能到达的所有顶点int v=Adj[u][i]; if(inq[v]==false){ //若u的邻接点v未曾加入过队列q.push(v); //将v入队inq[v]=true; //标记v为已经被加入过队列}}} }void BFSTrave(){ //遍历图Gfor(int u=0;u<n;u++){ //枚举所有顶点if(inq[u]==false){ //若u未曾加入过队列BFS(q); //遍历u所在连通块}} }

 

/* 邻接表版，设置层号和编号 */ struct Node{int v;int layer; }vector<Node> Adj[MAXV]; //图G，Adj[u]存放从顶点u出发可以到达的所有顶点 int n; //n为顶点数，MAXV为最大顶点数 bool inq[MAXV]={false}; //若顶点i曾入过队列，则inq[i]==true。初值为falsevoid BFS(int s){ //遍历s为起编号queue<Node> q; //定义队列qNode start;start.v=s;start.layer=0;q.push(start); //将初始点start入队inq[start.v]=true; //设置start已经进入过队列while(!q.empty()){ //只要队列非空Node topNode=q.front(); //取出队首元素q.pop(); //将队首元素出队int u=topNode.v; //队首顶点的编号for(int i=0;i<Adj[u].size();i++){ //枚举从u出发能到达的所有顶点int next=Adj[u][i]; next.layer=topNode.layer+1;if(inq[next.v]==false){ //若next的邻接点v未曾加入过队列q.push(next); //将next入队inq[next.v]=true; //标记next为已经被加入过队列}}} }void BFSTrave(){ //遍历图Gfor(int u=0;u<n;u++){ //枚举所有顶点if(inq[u]==false){ //若u未曾加入过队列BFS(q); //遍历u所在连通块}} }

 

总结

以上是生活随笔为你收集整理的【2019暑假刷题笔记-图的存储和图的遍历】绪论（代码模板-总结自《算法笔记》）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。