(1)DFS
图采用邻接表的结构,头文件algraph.h如下:
#defineMAX_VERTEX_NUM20
typedefintInfoType;
typedefcharVertexType;
typedefenum...{DG,DN,UDG,UDN}GraphKind;
typedefstructArcNode...{
intadjvex;
structArcNode*next;
InfoTypeinfo;
}ArcNode;
typedefstructVNode...{
VertexTypedata;
ArcNode*firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct...{
AdjListvertex;
intvexnum,arcnum;
GraphKindkind;
}algraph;
boolflag[MAX_VERTEX_NUM];
DFS的递归算法如下:
#include"algraph.h"
#include"stdio.h"
#include"stdlib.h"
voidcreateDN(algraph&g)...{}
voidcreateUDN(algraph&g)...{}
voidcreateUDG(algraph&g)...{}
//gettheverticename'sindex
intlocate(algraphg,charname)...{
for(inti=0;i<g.vexnum;i++)...{
if(name==g.vertex[i].data)...{
returni;
}
}
return-1;
}
voidcreateDG(algraph&g)...{
printf("inputthenumberofvertexandarcs: ");
scanf("%d%d",&g.vexnum,&g.arcnum);
fflush(stdin);
inti=0,j=0,k=0;
printf("inputthenameofvertex: ");
//initthevertexnames
for(i=0;i<g.vexnum;i++)...{
scanf("%c",&g.vertex[i].data);
fflush(stdin);
g.vertex[i].firstarc=NULL;
}
//constructthegraph'sadjacentlinklist
charv1,v2;
intw;
ArcNode*p;
printf("inputthe%darcsv1v2andweight: ",g.arcnum);
for(k=0;k<g.arcnum;k++)...{
scanf("%c%c%d",&v1,&v2,&w);
fflush(stdin);
i=locate(g,v1);
j=locate(g,v2);
//newalinknode
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->info=w;
p->next=NULL;
//insertthenewnodetotheheadoflist
if(!g.vertex[i].firstarc)...{
g.vertex[i].firstarc=p;
}else...{
p->next=g.vertex[i].firstarc;
g.vertex[i].firstarc=p;
}
}
}
//printthegraph
voidprintGraph(algraphg)...{
for(inti=0;i<g.vexnum;i++)...{
printf("theedgesofvretice%c: ",g.vertex[i].data);
ArcNode*p=g.vertex[i].firstarc;
while(p)...{
printf("%c(%d) ",g.vertex[p->adjvex].data,p->info);
p=p->next;
}
printf(" ");
}
}
voidcreateGragh(algraph&g)...{
printf("pleaseinputthetypeofgraph: ");
scanf("%d",&g.kind);
switch(g.kind)...{
caseDG:
createDG(g);
printGraph(g);
break;
caseDN:
createDN(g);
break;
caseUDG:
createUDG(g);
break;
caseUDN:
createUDN(g);
break;
}
}
voidvisit(algraphg,intv)...{
printf("%c",g.vertex[v].data);
}
//dfsthegraph
voiddfs(algraphg,inti,void(*f)(algraph,int))...{
flag[i]=1;
f(g,i);
ArcNode*p=g.vertex[i].firstarc;
while(p)...{
intadj=p->adjvex;
if(!flag[adj])...{
dfs(g,adj,f);
}
p=p->next;
}
}
voiddfsTraval(algraphg,void(*f)(algraph,int))...{
for(inti=0;i<g.vexnum;i++)...{
flag[i]=0;
}
for(i=0;i<g.vexnum;i++)...{
if(!flag[i])...{
dfs(g,i,f);
}
}
}
voidmain()...{
algraphg;
createGragh(g);
void(*f)(algraph,int);
f=visit;
dfsTraval(g,f);
}
(2)BFS
使用队列对图节点进行遍历。
程序略。
关于图的遍历算法的复杂度:
1. 图的DFS:使用的是邻接表的结构时,算法的复杂度是O(n + e);使用的是邻接矩阵的结构时,算法的复杂度是O(n2)。
2. 遍历图的过程实质是通过边或者弧找邻接点的过程,所以BDS和DFS的算法的复杂度相同,二者的区别在于对顶点的访问顺序不同。
分享到:
相关推荐
C语言数据结构 图的遍历课程设计 带源码及实验说明书
这是我们数据结构的实验 精心编制 希望对学习者有所帮助
数据结构课程设计关于树的遍历,图遍历的演示
数据结构之图的遍历 数据结构 图的遍历
图的遍历 数据结构 课程设计图的遍历 数据结构 课程设计图的遍历 数据结构 课程设计图的遍历 数据结构 课程设计图的遍历 数据结构 课程设计
图的遍历 C语言 数据结构 上机作业 邻接矩阵
前序中序等遍历二叉树的算法源代码, 广度优先:首先访问初始点vi,并将其标记为已访问,接着访问vi的所有未被访问的邻接点vi1到vit;并都记为已访问过,然后按照vi1到vit的顺序,访问一个接点的所有未被访问的邻...
图的遍历(深度、广度、各自递归、非递归实现)代码 配套文档可下载
数 据 结 构实 验 报 告 实验:图的遍历 一、实验目的: 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度...
C语言数据结构实现图的遍历 DFS
数据结构图的遍历class LinkedDigraph; class LinkedGraph; template <class T> class LinkedWDigraph; template <class T> class LinkedWGraph; template class LinkedBase: virtual public Network { friend ...
图的遍历,数据结构,PPT,掌握图的深度优先和广度优先遍历的性质和方法,以及基于邻接矩阵和邻接表存储结构的递归和非递归的算法实现
1. 以邻接多重表为存储结构,实现连通或非连通的无向图的深度优先与广度优先遍历。 2. 设图的结点不超过30个,每个结点用一个编号表示。通过输入图的边输入一个图,每条边为一个数对。 3. 问题描述: 4. 以用户...
利用广度优先算法实现图的遍历,算法结构清晰,比较容易看懂。
数据结构 二叉树的遍历 自己写的代码,可以完整运行,适合数据结构课后实验
1. 以邻接表为存储结构,演示在连通无向图上访问全部节点的操作。该无向图为一个交通网络,共25个节点,30条边,遍历时需要以用户指定的节点为起点,建立深度优先生成树和广度优先生成树,再按凹入表或树形打印生成...
数据结构 二叉树的遍历 课程设计 C/C ++ 语言
问题描述: 设计算法,演示连通无向图访问所有结点的过程。 功能要求: ...(6)给出至少3组测试数据,其中图顶点的个数大于10小于30。 较高要求:建立深度和广度生成树,按凹入表或树形打印生成树。
c++的数据结构实现图的深度遍历 1.分别采用邻接矩阵存储结构实现图的深度优先遍历 2.对任意给定的图(顶点数边树自定)建立它的邻接矩阵并输出 3.实现图的深度优先遍历
数据结构图的遍历PPT学习教案.pptx