一、实验目的1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构；2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和宽度优先遍历算法，复习栈和队列的应用；3．掌握图的各种应用的算法：图的连通性、连通分量和最小生成树、拓扑排序、关键路径。

二、实验内容实验内容1**图的遍历[问题描述]许多涉及图上操作的算法都是以图的遍历为基础的。

写一个程序，演示在连通无向图上遍历全部顶点。

[基本要求]建立图的邻接表的存储结构，实现无向图的深度优先遍历和广度优先遍历。

以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列。

[实现提示]设图的顶点不超过30个，每个顶点用一个编号表示（如果一个图有N个顶点，则它们的编号分别为1，2，…，N）。

通过输入图的全部边输入一个图，每条边是两个顶点编号对，可以对边依附顶点编号的输入顺序作出限制（例如从小到大）。

[编程思路]首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意无向是对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，深度遍历算法采用递归调用，其中最主要的是NextAdjVex(Graph G, int v, int w)；FirstAdjVex （）函数的书写，依次递归下去，广度遍历用队列的辅助。

[程序代码]头文件：#include<stdio.h>#include<stdlib.h>#define MAX_VERTEX_NUM 30#define MAX_QUEUE_NUMBER 30#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define TRUE 1#define FALSE 0typedef int Status;typedef int InfoType;typedef int Status;/* 定义弧的结构*/typedef struct ArcNode{int adjvex; /*该边所指向的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条边的指针*/ InfoType info; /*该弧相关信息的指针*/}ArcNode;/*定义顶点的结构*/typedef struct VNode{char data[40]; /*顶点信息*/ArcNode *firstarc; /*指向第一条依附该顶点的弧的指针*/}VNode,AdjList[MAX_VERTEX_NUM];/*定义图的结构*/typedef struct {AdjList vertices;int vexnum,arcnum; /*图的当前顶点数和弧数*/int kind; /*图的类型标志*/}Graph;/*定义队列的结构*/typedef struct{int *elem;int front, rear;}Queue;/*功能选择*/void MenuSelect(int w);/*顶点定位*/int LocateVex(Graph G,char *name);/*创建无向图*/void CreateGraph(Graph &G);/*求第一个顶点*/int FirstAdjVex(Graph G, int v);/*求下一个顶点*/int NextAdjVex(Graph G, int v, int w);/*深度递归*/void DFS(Graph G, int v) ;/*深度遍历*/void DFSTravel(Graph G,int v);/*广度遍历*/void BFSTraverse(Graph G,char *name);/*初始化队列*/Status InitQueue(Queue &Q);/*判空*/Status EmptyQueue(Queue Q);/*进队*/Status EnQueue(Queue &Q, int e);/*出队*/Status DeQueue(Queue &Q, int &e);实现文件：#include <stdio.h>#include"malloc.h"#include "tuhead.h"#include "stdlib.h"#include "string.h"bool visited[MAX_VERTEX_NUM];/************************************************************ 顶点定位************************************************************/int LocateVex(Graph G,char *name){int i;for(i=1;i<=G.vexnum;i++) //从1号位置开始存储if(strcmp(name,G.vertices[i].data)==0) //相等则找到，返回位序return i;return -1;}/************************************************************ 创建无向图************************************************************/void CreateGraph(Graph &G){ArcNode *p;char name1[10],name2[10];int i,j,k;printf(" 请输入顶点数,按回车键结束：");scanf("%d",&G.vexnum);printf(" 请输入弧数,按回车键结束：");scanf("%d",&G.arcnum);printf(" 请依次输入顶点名（用空格分开且字符小于10）,按回车键结束：\n");printf(" ");for(i=1;i<=G.vexnum;i++) //从1号位置开始存储{scanf("%s",G.vertices[i].data); //从一号位置开始初始化G.vertices[i].firstarc=NULL;}printf("\n\n\n\n");printf(" ………………………………………输入小提示………………………………………\n");printf(" &&&&1 为避免输入遗漏，最好从选择任意一点，输入所有相邻边\n");printf(" &&&&2 输入边时格式(用空格分开，即格式为顶点（空格）顶点（空格)）\n");printf(" ………………………………………输入小提示………………………………………\n\n\n\n");for(k=0;k<G.arcnum;k++){printf("请输入相邻的两个顶点,按回车键结束：");scanf("%s%s",name1,name2);i=LocateVex(G,name1); //返回位序j=LocateVex(G,name2);p=(ArcNode *)malloc(sizeof(ArcNode)); //申请边节点p->adjvex=j; //插入到邻接表中，注意此处为逆向插入到单链表中p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;//无向图，注意是对称插入结点p=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex=i;p->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p;}}/************************************************************ 求第一个顶点************************************************************/int FirstAdjVex(Graph G, int v){ArcNode *p;if(v>=1 && v<=G.vexnum){p=G.vertices[v].firstarc;if(p->nextarc==NULL)return 0;elsereturn (p->nextarc->adjvex); //返回第一个顶点字符}return -1;}/************************************************************ 求下一个顶点************************************************************/int NextAdjVex(Graph G, int v, int w){ //在图G中寻找第v个顶点的相对于w的下一个邻接顶点ArcNode *p;if(v>=1 && v<=G.vexnum && w>=1 && w<=G.vexnum){p=G.vertices[v].firstarc;while(p->adjvex!=w)p=p->nextarc; //在顶点v的弧链中找到顶点wif(p->nextarc!=NULL)return 0; //若已是最后一个顶点，返回0 elsereturn(p->nextarc->adjvex); //返回下一个邻接顶点的序号}return -1;}/************************************************************ 深度递归************************************************************/void DFS(Graph G, int v){int w;ArcNode *p;visited[v]=1;printf("%s ",G.vertices[v].data); //访问第v个顶点p=G.vertices[v].firstarc; //p为依附顶点的第一条边while (p!=NULL){w=p->adjvex;if(visited[w]==0)DFS(G,w);p=p->nextarc; //下移指针}}/************************************************************ 深度遍历************************************************************/void DFSTravel(Graph G,int v){for(int i=1;i<=G.vexnum;i++)visited[i]=0;int w;ArcNode *p;visited[v]=1;printf("%s ",G.vertices[v].data); //访问第v个顶点p=G.vertices[v].firstarc;while (p!=NULL){w=p->adjvex;if(visited[w]==0)DFS(G,w);p=p->nextarc;}}/************************************************************ 初始化队列************************************************************/Status InitQueue(Queue &Q){Q.elem = new int[MAX_QUEUE_NUMBER];Q.front = Q.rear = 0;return OK；}Status EmptyQueue(Queue Q){if(Q.front==Q.rear)return 0;elsereturn 1;}/*********************************************************** * 进队列* ***********************************************************/ Status EnQueue(Queue &Q, int e){if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)Q.elem[Q.rear ] = e;else ;Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;return OK；}/*********************************************************** * 出队列* ***********************************************************/ Status DeQueue(Queue &Q, int &e){if(Q.rear != Q.front)e = Q.elem[Q.front];else ;Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;return OK；}/*********************************************************** * 广度遍历************************************************************/void BFSTraverse(Graph G,char *name){ArcNode *p;int v,w,u,k=0;Queue Q;int visited[20];for(v=1;v<=G.vexnum;v++) //初始化visited[v]=0;InitQueue(Q);for(v=LocateVex(G,name);k!=2;v=(v+1)%(G.vexnum-1)) //v为输入的字符转化的位序{if(v+1==LocateVex(G,name)) //从v开始走完图的所有顶点k++;if(visited[v]==0){visited[v]=1;printf("%s ",G.vertices[v].data); //访问第v个顶点EnQueue(Q,v); // 进队while(EmptyQueue(Q)!=0){DeQueue(Q,u); //出队p=G.vertices[u].firstarc;while(p!=NULL){w=p->adjvex; //p边的下一个顶点if(visited[w]==0){printf("%s ",G.vertices[w].data);visited[w]=1;EnQueue(Q,w);}p=p->nextarc; //下移指针}}}}}主文件：#include <stdio.h>#include"malloc.h"#include "tuhead.h"#include "stdlib.h"#include "string.h"/************************************************************ 界面控制************************************************************/void main(){printf("\n################################# 图的遍历#################################\n");printf("\n $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");printf("\n");printf(" 1 ------- 图的创建\n");printf(" 2 ------- 图的深度优先遍历\n");printf(" 3 ------- 图的广度优先遍历\n");printf(" 0 ------- 退出\n");printf("\n $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");printf("\n");printf("请输入选择的操作代码（0-3）按回车键结束\n");MenuSelect(1);}/************************************************************ 功能选择************************************************************/void MenuSelect(int w){int select,done;int v;Graph G; char name[10];while (done) {printf("input the operating code : ");scanf("%d",&select);switch(select){case 1: printf("根据要求创建图:\n ");CreateGraph(G);break;case 2: printf("请输入深度优先遍历开始点的名：");scanf("%s",name);v=LocateVex(G,name); //将输入字符找到在顶点数组name对应的序号Vprintf("深度优先遍历：");DFSTravel(G,v);printf("\n");break;case 3: printf("请输入广度优先遍历开始点的名：");scanf("%s",name);printf("广度优先遍历：");BFSTraverse(G,name);printf("\n");break;case 0: done=0; break;default: printf(" ERROR\n");}printf("\n");}}[实验数据与结果]测试数据：实验结果。