淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：图形数据结构实验班级：软件081学号：110831123姓名：XX图形数据结构实验报告要求1目的与要求:1）掌握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的c语言实现；2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现；3）掌握AOV-网普里姆构造最小生成树算法的数据结构和算法实现；4）掌握AOE-网关路经的生成算法和实现；5）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；6）认真书写实验报告,并按时提交（第12周周一提交）。
2 实验内容或题目题目：一、图形数据结构实验——图的建立与遍历。
内容：1）使用邻接矩阵和邻接表储表示分别实现如下给定的图1和或图2所示图的物理存储结构。
2）在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。
题目：二、连通网的最小生成树及其应用实验（选做）内容：对下图所示通信连通网，按照普里姆算法实现其最小生成树。
V1v6v5v4v3V26513566425例2 有向图3 实验步骤与源程序#include <stdio.h>#include <stdlib.h>#include <string.h>#include<conio.h>#include<math.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define NULL 0#define MAX_VErR_NUM 10#define QueueSize 30/*邻接矩阵存储表示定义*/typedef enum{False,True}Boolean;Boolean visited[MAX_VErR_NUM ];typedef char VertexType;typedef int EdgeType;typedef struct{VertexType vexs[MAX_VErR_NUM ]; //顶点表EdgeType arcs[MAX_VErR_NUM ][MAX_VErR_NUM ]; //邻接矩阵,可看做边表 int n,e; //图中当前的顶点数和边数}MGraph;/*邻接表定义*/typedef struct Node{int elem;struct Node *next;}Node,*QNode;typedef struct{QNode front;QNode rear;}Queue;typedef struct ArcNode /*头节点*/{int adjvex; /*该边所指向的顶点的位置*/struct ArcNode *nextarc; /*指向下一条边*/}ArcNode;typedef struct VNode /*表节点*/{int data; /*顶点信息*/ArcNode *firstarc; /*指向第一条依附该节点的边的指针*/}VNode,AdjList[MAX_VErR_NUM ];typedef struct{AdjList vertices; /*表节点*/int vexnum; /*节点的个数*/int arcnum; /*边的条数*/}Graph;int Visited[MAX_VErR_NUM ];/* 邻接矩阵的存储*/void CreateMGraph(MGraph *G){int i,j,k;VertexType ch1,ch2;printf("输入顶点数和边数(中间以空格隔开):\n");fflush(stdin);scanf("%d%d",&(G->n),&(G->e));printf("输入顶点号每个顶点以空格作为结束:\n");for(i=0;i<G->n;i++){getchar();scanf("%c",&(G->vexs[i]));}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->arcs[i][j]=0;printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n"); for(k=0;k<G->e;k++){printf("请输入第%d条边的顶点序号：",k+1);fflush(stdin);scanf("%c,%c",&ch1,&ch2);for(i=0;ch1!=G->vexs[i];i++);for(j=0;ch2!=G->vexs[j];j++);G->arcs[i][j]=1;}}/*邻接矩阵的深度优先遍历搜索*/void DFSM(MGraph *G,int i){int j;printf("v%c ",G->vexs[i]);visited[i]=True;for(j=0;j<G->n;j++) //依次搜索vi邻接点if(G->arcs[i][j]==1 && !visited[j])DFSM(G,j);}void DFSTraverseM(MGraph *G){int i;for(i=0;i<G->n;i++)visited[i]=False;for(i=0;i<G->n;i++)if(!visited[i])DFSM(G,i);}/* 邻接矩阵的广度优先遍历搜索*/ typedef struct{int front;int rear;int count;int data[QueueSize];}CirQueue;void InitQueue(CirQueue *Q){Q->front=Q->rear=0;Q->count=0;}int QueueEmpty(CirQueue *Q){return Q->count=QueueSize;}int QueueFull(CirQueue *Q){return Q->count==QueueSize;}void EnQueue(CirQueue *Q,int x){if (QueueFull(Q))printf("Queue overflow");else{Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;}}int DeQueue(CirQueue *Q){int temp;if(QueueEmpty(Q)){printf("Queue underflow");return NULL;}else{temp=Q->data[Q->front];Q->count--;Q->front=(Q->front+1)%QueueSize;return temp;}}void BFSM(MGraph *G,int k){int i,j;CirQueue Q;InitQueue(&Q);printf("v%c ",G->vexs[k]);visited[k]=True;EnQueue(&Q,k);while (!QueueEmpty(&Q)){i=DeQueue(&Q);for (j=0;j<G->n;j++)if(G->arcs[i][j]==1&&!visited[j]){printf("广度优先遍历结点:%c\n",G->vexs[j]); visited[j]=True;EnQueue(&Q,j);}}}void BFSTraverseM(MGraph *G){int i;for (i=0;i<G->n;i++)visited[i]=False;for (i=0;i<G->n;i++)if (!visited[i])BFSM(G,i);}/*邻接表*/void InitQueue(Queue *Q) /*初始化操作*/{Q->front=Q->rear=(QNode)malloc(sizeof(Node));if(!Q->front) exit(OVERFLOW);Q->front->next=NULL;}void EnQueue(Queue *Q,int e) /*进队操作*/{QNode p=(QNode)malloc(sizeof(Node));if(!p) exit(OVERFLOW);p->elem=e;p->next=NULL;Q->rear->next=p;Q->rear=p;}void DeQueue(Queue *Q,int *e) /*出队操作*/{QNode p;p=Q->front->next;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;*e=p->elem;free(p);}int QueueEmpty(Queue Q){if(Q.rear==Q.front) return TRUE;else return -1;}int LocateVex(Graph *G,int v) /*返回节点v在图中的位置*/{int i;for(i=0;i<G->vexnum;++i)if(G->vertices[i].data==v) break;else continue;if(i<G->vexnum) return i;else return 0;}/*邻接表创建*/void CreateGraph(Graph *G){int m,n,i,j,k,v1,v2,flag=0;ArcNode *p1,*q1,*p,*q;printf("请输入有向图的顶点数目: ");scanf("%d",&m);printf("请输入有向图的边的数目: ");scanf("%d",&n);G->vexnum=m; /*顶点数目*/G->arcnum=n; /*边的数目*/for(i=0;i<G->vexnum;++i){G->vertices[i].data=i+1; /*顶点信息*/G->vertices[i].firstarc=NULL;}for(k=0;k<G->arcnum;++k){printf("请输入第 %d 条边的起点和终点（中间以空格隔开）: ",k+1);scanf("%d%d",&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);if(i>=0&&j>=0){++flag;p=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=NULL;if(!G->vertices[i].firstarc) G->vertices[i].firstarc=p;else{for(p1=G->vertices[i].firstarc;p1->nextarc;p1=p1->nextarc); p1->nextarc=p;}q=(ArcNode *)malloc(sizeof(ArcNode));q->adjvex=i;q->nextarc=NULL;if(!G->vertices[j].firstarc) G->vertices[j].firstarc=q;else{for(q1=G->vertices[j].firstarc;q1->nextarc;q1=q1->nextarc); q1->nextarc=q;}}else{printf("Not hava this edge!\n");k=flag;}}}int FirstAdjVex(Graph G,int v)/*返回v的第一个邻接顶点*/{if(G.vertices[v].firstarc)return G.vertices[v].firstarc->adjvex;elsereturn -1;}int NextAdjVex(Graph G,int v,int w)/*返回v中相对于w的下一个邻接顶点*/ {int flag=0;ArcNode *p;p=G.vertices[v].firstarc;while(p){if(p->adjvex==w){flag=1;break;}p=p->nextarc;}if(flag && p->nextarc)return p->nextarc->adjvex;elsereturn -1;}/*邻接表深度优先遍历*/void DFS(Graph G,int v){int w;Visited[v]=TRUE;printf("v%d ",G.vertices[v].data);for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!Visited[w]) DFS(G,w);}void DFSTraverse(Graph 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(Graph G)/*广度优先遍历*/{int v,v1,w;Queue 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("v%d ",G.vertices[v].data);EnQueue(&q,v); /*第一个顶点入队*/while(!QueueEmpty(q)){DeQueue(&q,&v1); /*第一个顶点出对*/for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,w))if(!Visited[w]){Visited[w]=TRUE;printf("v%d ",G.vertices[w].data);EnQueue(&q,w);}}}}void main(){int a,flag=1;MGraph G;Graph g;char ch;printf("1 对邻接矩阵进行深度优先遍历与广度优先遍历 \n2 对邻接表进行深度优先遍历与广度优先遍历 \n3 退出 \n");while(flag){printf("请选择：");scanf("%d",&a);switch(a){case 1:CreateMGraph(&G);printf("深度优先遍历结点: ");DFSTraverseM(&G);printf("\n");printf("广度优先遍历结点:");BFSTraverseM(&G);printf("\n");break;case 2:CreateGraph(&g);printf("深度优先搜索为:\n");DFSTraverse(g);printf("\n");printf("广度优先搜索为:\n");BFSTraverse(g);printf("\n");break;case 3:flag=0;break;}}}4 测试数据与实验结果（可以抓图粘贴）邻接矩阵的深度与广度遍历并输出，如下图输出结果：邻接表的深度与广度遍历，输出结果如下图所示：5 结果分析与实验体会这次的实验说实话比前几次难点，特别是邻接表的遍历会应用到前面所学到的队列，就明显增加了难度，并且图中所涉及的语句比较难理解，幸好老师让我们上机讲了一遍，不然自己真不知道从哪里入手，也对程序了解了点。
