实验四图的存储、遍历与应用姓名：班级：学号：日期：一、实验目的：二、实验内容：三、基本思想，原理和算法描述:四、源程序：（1）邻接矩阵的存储：#include<stdio.h>#include<stdlib.h>#define INFINITY 10000 //定义最大值无穷大#define MAX_VERTEX_NUM 20 //最大顶点个数typedef int AdjMatrix[MAX_VERTEX_NUM ][MAX_VERTEX_NUM ]; typedef struct{int vexs[MAX_VERTEX_NUM ]; //顶点向量AdjMatrix arcs; //邻接矩阵int vexnum,arcnum; //图的当前顶点数和弧或边数}MGraph;void CreatGragh(MGraph G) //用邻接矩阵构造图{int i,j,k,w;printf("请输入顶点个数和边数:\n");scanf("%d %d",&G.vexnum,&G.arcnum);printf("请按顺序输入顶点中间用‘空格’间隔\n");for(i=0;i<G.vexnum;i++)scanf("%d",&G.vexs[i]); //构造顶点向量for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arcs[i][j]= INFINITY; //初始化邻接矩阵for(k=1;k<=G.arcnum;k++){printf("请输入边的顶点序号和对应的权值中间用‘空格’间隔:\n");scanf("%d %d %d",&i,&j,&w);G.arcs[i][j]=G.arcs[j][i]=w;}}int main(){MGraph G1;CreatGragh(G1);return 0;}(2)图的遍历：#include <stdio.h>#include <string.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OVERFLOW -2#define OK 1#define ERROR 0typedef int Status;#define INFINITY 10000 //最大#define MAX_VERTEX_NUM 20 //最大顶点个数typedef int Boolean;typedef char VertexType[20];typedef int VRType;typedef int QElemType;typedef struct QNode{QElemType data;struct QNode *next;} QNode, *QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;} LinkQueue;Status InitQueue(LinkQueue *Q) //初始化队列{(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));if (!(*Q).front)exit(OVERFLOW);(*Q).front->next=NULL;return OK;}Status QueueEmpty (LinkQueue Q) //判断队列是否为空{if (Q.front==Q.rear)return TRUE;elsereturn FALSE;}Status EnQueue(LinkQueue *Q, QElemType e) // 入队列{QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if (!p)exit(OVERFLOW);p->data=e; p->next=NULL;(*Q).rear->next=p;(*Q).rear=p;return OK;}Status DeQueue(LinkQueue *Q, QElemType *e) //出队列{QueuePtr p;if ((*Q).front==(*Q).rear)return ERROR;p=(*Q).front->next;*e=p->data;(*Q).front->next=p->next;if ((*Q).rear==p)(*Q).rear=(*Q).front;free(p);return OK;}typedef struct ArcCell{VRType adj;} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{VertexType vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;} MGraph;void CreateGraph(MGraph *G) //建立无向图的邻接矩阵{int i,j,k;VertexType v1,v2;printf("输入顶点数和边数中间用','隔开:");scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);printf("输入%d 顶点:",(*G).vexnum);for(i=0;i<(*G).vexnum;i++){scanf("%s",(*G).vexs[i]); }//printf("vexs list\n");// for(i=0;i<G->vexnum;i++)// puts(G->vexs[i]);for(i=0;i<(*G).vexnum;i++)for(j=0;j<(*G).vexnum;j++)(*G).arcs[i][j].adj=0;printf("\n输入%d 条边，分别输入两顶点，中间用空格隔开\n",(*G).arcnum);printf("输入一条后按'ENTER'后输入下一条边:\n");for(k=0;k<(*G).arcnum;k++){scanf("%s%s",v1,v2);i=LocateVex(*G,v1);j=LocateVex(*G,v2);(*G).arcs[i][j].adj=1;(*G).arcs[j][i]=(*G).arcs[i][j];}}int LocateVex(MGraph G,VertexType v)// 顶点在顶点向量中的定位{int i;for(i=0;i<G.vexnum;i++)if (strcmp(v,G.vexs[i])==0) break;return i;}int FirstAdjVex(MGraph G,int v) //查找第1个邻接点{int j,p=-1;for(j=0;j<G.vexnum;j++)if (G.arcs[v][j].adj==1) {p=j; break;}return p;}int NextAdjVex(MGraph G,int v,int w) //查找下一个邻接点{int j,p=-1;for(j=w+1;j<G.vexnum;j++)if (G.arcs[v][j].adj==1){p=j; break;}return p;}Boolean visited[MAX_VERTEX_NUM]; //深度遍历void Dfs(MGraph G, int v){int w;visited[v]=TRUE;printf("%s",G.vexs[v]);for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))if(!visited[w]) Dfs(G,w);}void DFSTraverse(MGraph G){int v;for (v=0; v<G.vexnum; v++)visited[v]=FALSE;for(v=0; v<G.vexnum; v++)if (!visited[v])Dfs(G,v);}void BFSTraverse(MGraph G) //广度遍历{int v,u,w;LinkQueue Q;for(v=0; v<G.vexnum; v++)visited[v]=FALSE;InitQueue(&Q);for(v=0; v<G.vexnum; v++)if (!visited[v]){visited[v]=TRUE;printf("%s",G.vexs[v]);EnQueue(&Q,v);while(!QueueEmpty(Q)){DeQueue(&Q,&u);for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))if (!visited[w]) {visited[w]=TRUE;printf("%s",G.vexs[w]);EnQueue(&Q,w);}}}}int main(){int w;MGraph G;CreateGraph(&G);printf("\n深度遍历:");DFSTraverse(G);printf("\n");printf("\n广度遍历:");BFSTraverse(G);printf("\n");return 0;}五、运行结果分析：图1:邻接矩阵的存储六、实验总结：。