22-1图的遍历的源代码
遍历 源代码 22
2023-09-11 14:21:07 时间
/*图遍历的源代码
通过邻接矩阵的方式来保存给结点的值,再通过边的连接形成一个图。
验证深度优先搜索、广度优先搜索。
*/
#include "stdafx.h" #include<iostream> #include<queue> #include<stack> #include<stdlib.h> #define MAX 100 using namespace std; typedef struct { int edges[MAX][MAX]; //邻接矩阵 int n; //顶点数 int e; //边数 }MGraph; bool visited[MAX]; //标记顶点是否被访问过 //清空图的标志 void Init(MGraph G) { int i,j; for(i=0;i<G.n;i++) //初始化 { for(j=0;j<G.n;j++) { G.edges[i][j]=0; } visited[i]=false; } }; void creatMGraph(MGraph &G) //用引用作参数 { int i; int s,t; //存储顶点编号 int v; //存储边的权值 Init(G); for(i=0;i<G.e;i++) //对矩阵相邻的边赋权值 { scanf("%d %d %d",&s,&t,&v); //输入边的顶点编号以及权值 G.edges[s][t]=v; } } void DFS(MGraph G,int v) //深度优先搜索 { static int k=0; int i; if(k==0) { printf("递归深度优先搜索:"); k++; } printf("%d ",v); //访问结点v visited[v]=true; for(i=0;i<G.n;i++) //访问与v相邻的未被访问过的结点 { if(G.edges[v][i]!=0&&visited[i]==false) { DFS(G,i); } } } void DFS1(MGraph G,int v) //非递归实现 { Init(G); stack<int> s; static int k=0; if(k==0) { printf("非递归深度优先搜索:"); k++; } printf("%d ",v); //访问初始结点 visited[v]=true; s.push(v); //入栈 while(!s.empty()) { int i,j; i=s.top(); //取栈顶顶点 for(j=0;j<G.n;j++) //访问与顶点i相邻的顶点 { if(G.edges[i][j]!=0&&visited[j]==false) { printf("%d ",j); //访问 visited[j]=true; s.push(j); //访问完后入栈 break; //找到一个相邻未访问的顶点,访问之后则跳出循环 } } if(j==G.n) //如果与i相邻的顶点都被访问过,则将顶点i出栈 s.pop(); } } void BFS(MGraph G,int v) //广度优先搜索 { Init(G); queue<int> Q; //STL模板中的queue static int k=0; if(k==0) { printf("广度优先搜索:"); k++; } printf("%d ",v); visited[v]=true; Q.push(v); while(!Q.empty()) { int i,j; i=Q.front(); //取队首顶点 Q.pop(); for(j=0;j<G.n;j++) //广度遍历 { if(G.edges[i][j]!=0&&visited[j]==false) { printf("%d ",j); visited[j]=true; Q.push(j); } } } } int main(void) { int n,e; //建立的图的顶点数和边数 while(scanf("%d %d",&n,&e)==2&&n>0) { MGraph G; G.n=n; G.e=e; creatMGraph(G); DFS(G,0); printf("\n"); DFS1(G,0); printf("\n"); BFS(G,0); printf("\n"); } return 0; }
相关文章
- Visual Studio 2017中使用正则修改部分内容 如何使用ILAsm与ILDasm修改.Net exe(dll)文件 C#学习-图解教程(1):格式化数字字符串 小程序开发之图片转Base64(C#、.Net) jquery遍历table为每一个单元格取值及赋值 。net加密解密相关方法 .net关于坐标之间一些简单操作
- 【JAVA】Map类、HashMap的添加、删除、遍历实例,包括泛型。
- jQeury入门:遍历
- Asp.net遍历数组实例!(源代码示例,有傻瓜说明!)
- jquery遍历的json有两层list时的解决方法
- CVE-2020-17518/17519:Apache Flink 目录遍历漏洞
- el-form 动态遍历el-form-item 输入没反应,但打印是有数据的
- 遍历指定文件夹内文件并拼接到一起到指定文件中
- python dict list 遍历的几种常见方法
- Linux-007-实用小脚本:遍历文本文件
- Map中使用和遍历map方法
- 如何高效地遍历 MongoDB 超大集合?
- nyoj 51-管闲事的小明(遍历,比较)
- java 遍历Map的4种方法
- Python 遍历Sheet 每个Sheet都单独保存为一个Excel
- leetcode算法145.二叉树的后序遍历
- leetcode算法94.二叉树的中序遍历