数据结构C语言版 图的广度优先遍历和深度优先遍历 急急急 会查重
/* 程序1：邻接表的dfs,bfs 其中n是点的个数,m是边的个数,你需要输入m条有向边，如果要无向只需要反过来多加一遍即可。*/#include #include #define MAXM 100000#define MAXN 10000int next[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail;void input_data(){ scanf("%d%d",&n,&m); int i,x,y; for (i=1;i#include #define MAXN 1000int n,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN];void input_data(){ scanf("%d%d",&n,&m); int i; for (i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); w[x][0]++; w[x][w[x][0]]=y; }}void pre(){ memset(flag,0,sizeof(flag)); pd=0;}void dfs(int x){ flag[x]=1; if (!pd) { pd=1; printf("%d",x); }else printf(" %d",x); int i; for (i=1;i<=w[x][0];i++) { int y=w[x][i]; if (!flag[y]) dfs(y); }}void bfs(int t){ int head=0,tail=1; dl[1]=t;flag[t]=1; while (head<tail) { int x=dl[++head]; if (!pd) { pd=1; printf("%d",x); }else printf(" %d",x); int i; for (i=1;i<=w[x][0];i++) { int y=w[x][i]; if (!flag[y]) { flag[y]=1; dl[++tail]=y; } } }}int main(){ input_data(); printf("图的深度优先遍历结果:"); pre(); int i; for (i=1;i<=n;i++) if (!flag[i]) dfs(i); printf("
---------------------------------------------------------------
"); printf("图的广度优先遍历结果:"); pre(); for (i=1;i<=n;i++) if (!flag[i]) bfs(i); printf("
-----------------------------end--------------------------------
"); return 0;}
两种各有应用，部分好坏。能否用迭代也是和你存储图的数据结构相关。
深度优先遍历，也就深入的遍历，沿着每一个分支直到走到最后，然后才返回来遍历剩余的节点。二叉树不同于图，图需要标记节点是否已经访问过，因为可能会存在环，而二叉树不会出现环，所以不需要标记。那么，我们只需要一个栈空间，来压栈就好了。因为深度优先遍历，遍历了根节点后，就开始遍历左子树，所以右子树肯定最后遍历。我们利用栈的性质，先将右子树压栈，然后在对左子树压栈。此时，左子树节点是在top上的，所以可以先去遍历左子树。
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int FirstAdjVex(int v);
int NextAdjVex(int v, int w);
void DFS(int v); //从顶点v开始对图做深度优先遍历, v是顶点数组的下标
void BFS(int v); //从顶点v开始对图做广度优先遍历，v是顶点数组的下标
int find(string a,int n);
int visited[10]={0};
int traver[10][10]={0};
string name[10];
int main()
{
int n,m,i,j,k;
string a,b;
//freopen("Traver.txt","r",stdin);
cin>>n;
cin>>m;
for(i=0; i<n; i++)
{
cin>>a;
name[i] = a;
}
for(i=0; i<m;i++){
cin>>a;
cin>>b;
j = find(a,n);
k = find(b,n);
traver[j][k] = 1;
traver[k][j] = 1;
}
for(i=0; i<n; i++){
if(visited[i] == 0)
DFS(i);
}
cout<<"
";
for(i=0; i<n; i++){
visited[i] = 0;
}
for(i=0; i<n; i++){
if(visited[i] == 0)
BFS(i);
}
cout<<"
";
return 0;
}
//寻找函数
int find(string a,int n){
int i;
for(i=0; i<n; i++){
if(a == name[i])
return i;
}
return -1;
}
int FirstAdjVex(int v)
{
int i;
//从编号大的邻接点开始访问
for (i = 9; i >= 0; i--)
{
if (traver[v][i] == 1)
return i;
}
return -1;
}
int NextAdjVex(int v, int w)
{
int i;
for (i = w - 1; i >= 0; i--)
{
if (traver[v][i] == 1)
return i;
}
return -1;
}
void DFS(int v)
{
int w;
//访问顶点v(输出顶点v的名字)
cout<<name[v]<<" ";
visited[v] = 1;
//找到顶点v的第一个邻接点w
for (w = FirstAdjVex(v); w >= 0; w = NextAdjVex(v, w))
{
//如果w没有访问过，对顶点w做深度优先搜索
if (visited[w] == 0)
DFS(w);
}
}
void BFS(int v) //从顶点v开始对图做广度优先遍历，v是顶点数组的下标
{
int w, u;
queue<int> myqueue; //定义一个队列，元素是顶点的下标
//把顶点v入队
myqueue.push(v);
cout<<name[v]<<" ";
visited[v] = 1;
while (!myqueue.empty())
{//当队列不为空时进入循环
//取队头元素
u = myqueue.front();
//队头元素出队
myqueue.pop();
//把u的所有邻接点入队
w = FirstAdjVex(u);
while (w >= 0)
{
if (visited[w] == 0)
{
//访问w
cout<<name[w]<<" ";
visited[w] = 1;
//w入队
myqueue.push(w);
}
w = NextAdjVex(u, w);
}
}
}
皇杜人胎： (1) 图的建立,按采用邻接表作为存储结构.(2) 从指定顶点出发进行深度优先搜索遍历.(3) 从指定顶点出发进行广度优先搜索遍历.#include＂stdio.h＂#include＂string.h＂#include＂stdlib.h＂#include＂math.h＂#define MAX_INT 1000#define ...
永年县19831288682： C语音算法图的广度优先算法实现代码?要C语言版的 - ？
皇杜人胎： 深度优先遍历算法(Depth-first-search),重点关注的是图的连通性(connectivity),即从图中给定的一点都能访问到哪些点.不仅如此,在遍历这些点的过程中,通过记录访问次序,可以实现其他功能,比如测试该图是否有闭环等. 广度优先...
永年县19831288682： 求c语言图的深度优先遍历算法 - ？
皇杜人胎： //两个算法使用的全局变量 --- bool visited[MAX_VERTEX_NUM]; // 访问标志数62616964757a686964616fe59b9ee7ad9431333264663039组 Status (* VisitFunc)(int v); // 函数变量 void DFSTraverse(Graph G, Status (*Visit)(int v)) {// 对图G作...
永年县19831288682： 图的广度优先遍历的C语言程序(有头文件的) - ？
皇杜人胎： // bo7-2.cpp 图的邻接表存储(存储结构由c7-2.h定义)的基本操作(15个) int LocateVex(ALGraph G,VertexType u) { // 初始条件: 图G存在,u和G中顶点有相同特征 // 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 int i; ...
永年县19831288682： 用C语言实现 图的邻接表和邻接矩阵数据结构的定义、创建;图的深度优先遍历、广度优先遍历. - ？
皇杜人胎： /* 程序1:邻接表的dfs,bfs 其中n是点的个数,m是边的个数,你需要输入m条有向边,如果要无向只需要反过来多加一遍即可. */ #include <stdio.h> #include <string.h> #define MAXM 100000 #define MAXN 10000 int next[MAXM],first[MAXN],en...
永年县19831288682： 广度优先搜索C语言算法 - ？
皇杜人胎： 它没有固定的写法, 但是大框都差不多, 一定要使用队列, 因为队列的存在可以维护程序按照广度优先的方式进行搜索.即层次遍历 可以给你一份我作过的一个题的代码,大体上就是这个样子/****************************************************\ * * ...
永年县19831288682： 数据结构 深度优先遍历和广度 - ？
皇杜人胎： 无向图:两个结点之间的路径没有方向区分 有向图:两个结点之间的路径有方向区分,从A到B的路径长和从B到A的路径长可以不同 深度优先遍历:从给定结点出发,选取它的邻接结点中某个未被访问的结点访问.被访问的结点成为新的给定结点.重复上述过程,直到当前结点没有未被访问的邻接结点.接着开始回溯,返回上一次访问的结点继续寻找其未被访问的邻接结点,直至完成遍历. 广度优先遍历:从给定结点出发,依次访问它的所有邻接结点.然后按照这些结点的被访问顺序,依次访问这些结点的所有邻接结点.重复上述过程,直至完成遍历.
永年县19831288682： 求一个C语言编程,图的遍历,深度优先和广度优先搜索的程序.要浅显易懂的~~~~？
皇杜人胎： 给你一个作为参考吧 #include <iostream> #define INFINITY 32767 #define MAX_VEX 20 //最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) //队列长度 using namespace std; bool *visited; //访问标志数组 //图的邻接矩阵存储结构 typedef struct...
永年县19831288682： 数据结构课程设计题目,图的建立以及遍历. - ？
皇杜人胎： //图的遍历算法程序 //图的遍历是指按某条搜索路径访问图中每个结点,使得每个结点均被访问一次,而且仅被访问一次.图的遍历有深度遍历算法和广度遍历算法,程序如下: #include <iostream> //#include <malloc.h> #define INFINITY 32767 ...
永年县19831288682： 数据结构:图的深度优先遍历和广度优先遍历？
皇杜人胎： 图的深度优先遍历:1->2->4->6->5->3 图的广度优先遍历:1->2->3->4->5->6
