数据结构实验报告——实验8一、实验目的1、复习图的逻辑结构、存储结构及基本操作；2、掌握邻接矩阵、邻接表及图的创建、遍历；二、实验内容假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作：（1）构造图（包括有向图、有向网、无向图、无向网）；（2）根据深度优先遍历图；（3）根据广度优先遍历图。

三、算法描述（采用自然语言描述）先输入顶点个数以及边数，按照边的数量，依次输入边依附的两个顶点，构造邻接矩阵的时候，用1表示两个顶点相连接，用无穷表示两个顶点未连接。

深度优先遍历图的时候，先找到开始结点，然后找到与此结点相邻的第一个结点，进一步以此结点为开始结点递归。

若没有邻接点，回溯，直至所有结点都被访问。

广度优先遍历，依次访问与开始结点相邻的结点，然后以开始结点相邻的结点进行广度优先遍历。

四、详细设计（画出程序流程图）五、程序代码（给出必要注释）#include<stdio.h>#include<malloc.h>#include<conio.h>#include<stdlib.h>#include<string.h>#include<string.h>#include <stdbool.h>#define INFINITY 255678 /*赋初值用*/#define MAX_VERTEX_NUM 20 /* 最大顶点个数*/#define TRUE 1#define FALSE 0typedef int QueueElementType;#define MAXSIZE 25enum {DG, DN, UDG, UDN};typedef struct ArcCell{int adj;/*顶点关系类型,对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值*/ char *info;/*弧相关信息指针*/}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{char vexs[MAX_VERTEX_NUM][5];/*顶点向量*/AdjMatrix arcs; /*邻接矩阵*/int vexnum, arcnum;/*图的当前顶点数和弧数*/int kind;}MGraph;void CreateDG(MGraph *G);void CreateDN(MGraph *G);void CreateUDG(MGraph *G);void CreateUDN(MGraph *G);int LocateVex(MGraph *G, char v[]);void print(MGraph *G);int main(void){MGraph *G;bool visited[G->vexnum];G = (MGraph *)malloc(sizeof(MGraph));printf("请选择0-有向图,1-有向网,2-无向图,3-无向网: ");scanf("%d", &G->kind);switch(G->kind){case DG :CreateDG(G);print(G);break;case DN :CreateDN(G);print(G);break;case UDG :CreateUDG(G);print(G);break;case UDN :CreateUDN(G);print(G);break;default :break;}getch();}/*建立有向图*/void CreateDG(MGraph *G){int i, j, k;char v1[5], v2[5];printf("输入顶点数和弧数: ");scanf("%d%d", &G->vexnum, &G->arcnum);getchar();for(i = 0; i < G->vexnum; i++){printf("输入第%d个顶点：\n",i+1);scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/ }for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++) /*赋初值*/{G->arcs[i][j].adj = INFINITY;G->arcs[i][j].info = NULL;}}for(k = 0; k < G->arcnum; k++){printf("输入第%d条边依附的两个顶点\n",k+1);scanf("%s%s", v1, v2); /*输入一条边依附的顶点和权值*/i = LocateVex(G, v1); /*确定v1和v2在G中位置*/j = LocateVex(G, v2);G->arcs[i][j].adj = 1; /*弧的权值赋值*/}}/*建立有向网*/void CreateDN(MGraph *G){int i, j, k, w;char v1[5], v2[5];printf("输入顶点数和弧数: ");scanf("%d%d", &G->vexnum, &G->arcnum);getchar();for(i = 0; i < G->vexnum; i++){printf("输入第%d个顶点：\n",i+1);scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/ }for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++) /*赋初值*/{G->arcs[i][j].adj = INFINITY;G->arcs[i][j].info = NULL;}}for(k = 0; k < G->arcnum; k++){printf("输入第%d条边依附的两个顶点以及权值\n",k+1);scanf("%s%s%d", v1, v2, &w); /*输入一条边依附的顶点和权值*/i = LocateVex(G, v1); /*确定v1和v2在G中位置*/j = LocateVex(G, v2);G->arcs[i][j].adj = w; /*弧的权值赋值*/}}/*建立无向图*/void CreateUDG(MGraph *G){int i, j, k;char v1[5],v2[5];printf("输入顶点数和弧数: ");scanf("%d%d", &G->vexnum, &G->arcnum);getchar();for(i = 0; i < G->vexnum; i++){printf("输入第%d个顶点：\n",i+1);scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/ }for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++) /*赋初值*/{G->arcs[i][j].adj = INFINITY;G->arcs[i][j].info = NULL;}}for(k = 0; k < G->arcnum; k++){printf("输入第%d条边依附的两个顶点\n",k+1);scanf("%s%s", v1, v2); /*输入一条边依附的顶点和权值*/i = LocateVex(G, v1); /*确定v1和v2在G中位置*/j = LocateVex(G, v2);G->arcs[i][j].adj = 1; /*弧的权值赋值*/G->arcs[j][i].adj=G->arcs[i][j].adj;/*置对称弧*/}}/*建立无向网*/void CreateUDN(MGraph *G){int i, j, k, w;char v1[5], v2[5];printf("输入顶点数和弧数: ");scanf("%d%d", &G->vexnum, &G->arcnum);getchar();for(i = 0; i < G->vexnum; i++){printf("输入第%d个顶点：\n",i+1);scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/}for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++) /*赋初值*/{G->arcs[i][j].adj = INFINITY;G->arcs[i][j].info = NULL;}}for(k = 0; k < G->arcnum; k++){printf("输入第%d条边依附的两个顶点以及权值\n",k+1);scanf("%s%s%d", v1, v2, &w); /*输入一条边依附的顶点和权值*/i = LocateVex(G, v1); /*确定v1和v2在G中位置*/j = LocateVex(G, v2);G->arcs[i][j].adj = w; /*弧的权值赋值*/G->arcs[j][i].adj=G->arcs[i][j].adj;/*置对称弧*/}}int LocateVex(MGraph *G, char v[]){int k;for(k = 0; k < G->vexnum; k++){if(strcmp(G->vexs[k], v) == 0)break;}return k;}/*打印矩阵*/void print(MGraph *G){int i, j;printf("\n------------打印矩阵----------\n\n");for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++){if(G->arcs[i][j].adj == INFINITY){printf(" / ");}else{printf(" %d ", G->arcs[i][j].adj);}}printf("\n\n");}}//深度优先遍历void dfs_graph(MGraph * graph, bool visited[], const int i);void g_depth_first_search(MGraph * graph){bool visited[graph->vexnum];int i;for ( i = 0; i < graph->vexnum; i++ )visited[i] = false;visited[0] = true;dfs_graph(graph, visited, 0);printf("\n");}void dfs_graph(MGraph * graph, bool visited[], const int i){int j;printf("%c\t", graph->vexs[i]);for ( j = 0; j < graph->vexnum; j++ )//依次检查矩阵{if ( graph->arcs[i][j].adj==1 && !visited[j] )//i 代表矩阵的行, j 代表矩阵的列{visited[j] = true;dfs_graph(graph, visited, j);}}}typedef struct{QueueElementType element[MAXSIZE];int front;int rear;}SeqQueue;void InitQueue(SeqQueue*Q){Q->front=Q->rear=0;}int EnterQueue(SeqQueue *Q,QueueElementType x){if(Q->rear==Q->front)return FALSE;elseQ->element[Q->rear+1]=x;Q->rear=Q->rear+1;return TRUE;}int DeleteQueue(SeqQueue *Q){int x;x=Q->element[Q->front];Q->front=Q->front+1;printf("删除%d\n",x);return TRUE;}//广度优先遍历void g_breadth_first_search(MGraph * graph){SeqQueue queue;//队列存储的是节点数组的下标(int)bool visited[graph->vexnum];int i, pos;InitQueue(&queue);for ( i = 0; i < graph->vexnum; i++ )visited[i] = false;visited[0] = true;EnterQueue(&queue, 0);while (queue.front!=queue.rear){pos = queue.front;printf("%c\t", graph->vexs[pos]);for ( i = 0; i < graph->vexnum; i++ )//把队头元素的邻接点入队{if ( !visited[i] && graph->arcs[pos][i].adj != 1 ){visited[i] = true;EnterQueue(&queue, i);}}DeleteQueue(&queue);}printf("\n");}六、测试和结果（给出测试用例，并给出测试结果）七、用户手册（告诉用户如何使用程序，使用注意事项等）1、输入的顶点个数和边数之间用空格字符隔开；2、输入边依附的两个顶点的时候中间用空格字符隔开；3、每次输入一个顶点的时候需要打回车，进行下一个顶点输入。