资源描述：
《柴伦洋作业数据结构四.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数据结构（四）图1、实验目的（1）熟悉图的数组表示法和邻接表存储结构。（2）掌握构造有向图、无向图的算法。（3）在掌握以上知识的基础上，熟悉图的深度优先遍历算法和广度优先遍历算法，并实现之。2、实验要求（1）图的数组表示法定义及基本操作的实现。（2）图的邻接表表示法及基本操作的实现。（3）写出函数实现图的深度优先遍历3、实验内容图的邻接表表示法和遍历算法（1）以邻接表作为存储结构，定义图结点vertexnode；（2）实现图的下列运算：a以邻接表作为存储结构建立图b按照深度遍历算法遍历图c按照广度遍历算法遍历图。根据程序得到运
2、算结果：#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum50//定义最大顶点数typedefstructnode{//边表结点intadjvex;//邻接点域structnode*next;//链域}EdgeNode;typedefstructvnode{//顶点表结点charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjLis
3、t是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中当前顶点数和边数}ALGraph;//图类型//=========建立图的邻接表=======voidCreatALGraph(ALGraph*G){inti,j,k;chara;EdgeNode*s;//定义边表结点printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);//读入顶点数和边数fflush(stdin);//清空内存缓冲pri
4、ntf("InputVertexstring:");for(i=0;in;i++)//建立边表{scanf("%c",&a);G->adjlist[i].vertex=a;//读入顶点信息G->adjlist[i].firstedge=NULL;//边表置为空表}printf("Inputedges,CreatAdjacencyList");for(k=0;ke;k++){//建立边表scanf("%d%d",&i,&j);//读入边（Vi，Vj）的顶点对序号s=(EdgeNode*)malloc(size
5、of(EdgeNode));//生成边表结点s->adjvex=j;//邻接点序号为js->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;//将新结点*S插入顶点Vi的边表头部s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=i;//邻接点序号为is->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s;//将新结点*S插入顶点Vj的边表头部}}//======
6、===定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voidDFSM(ALGraph*G,inti){//以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode*p;printf("%c",G->adjlist[i].vertex);//访问顶点Vivisited[i]=TRUE;//标记Vi已访问p=G->adjlist[i].firstedg
7、e;//取Vi边表的头指针while(p){//依次搜索Vi的邻接点Vj，这里j=p->adjvexif(!visited[p->adjvex])//若Vj尚未被访问DFSM(G,p->adjvex);//则以Vj为出发点向纵深搜索p=p->next;//找Vi的下一个邻接点}}voidDFS(ALGraph*G){inti;for(i=0;in;i++)visited[i]=FALSE;//标志向量初始化for(i=0;in;i++)if(!visited[i])//Vi未访问过DFSM(G,i);//以Vi
8、为源点开始DFS搜索}//==========BFS：广度优先遍历=========voidBFS(ALGraph*G,intk){//以Vk为源点对用邻接链表表示的图G进行广度优先搜索inti,f=0,r=0;EdgeNode*p;intcq[MaxVertexNum];/
