1.实验目的通过上机实验进一步掌握图的存储结构及基本操作的实现。

2.实验内容与要求要求：⑴能根据输入的顶点、边/弧的信息建立图；⑵实现图中顶点、边/弧的插入、删除；⑶实现对该图的深度优先遍历；⑷实现对该图的广度优先遍历。

备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。

3.数据结构设计逻辑结构：图状结构存储结构：顺序存储结构、链式存储结构4.算法设计#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAX_VERTEX_NUM 20 typedef struct ArcNode{int adjvex;struct ArcNode *nextarc; }ArcNode;typedef struct VNode{char data[2]; //顶点就设置和书上V1等等一样吧ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{AdjList vertices;int vexnum,arcnum;}ALGraph;typedef struct{int data[MAX_VERTEX_NUM+10];int front;int rear;}queue;int visited[MAX_VERTEX_NUM]; queue q;int main(){ALGraph G;int CreateUDG(ALGraph &G);int DeleteUDG(ALGraph &G);int InsertUDG(ALGraph &G);void BFSTraverse(ALGraph G, int (*Visit)(ALGraph G,ArcNode v));int PrintElement(ALGraph G,ArcNode v);void menu();void depthfirstsearch(ALGraph *g,int vi);void travel(ALGraph *g);void breadfirstsearch(ALGraph *g);int i;G.arcnum = G.vexnum = 0;while(1){menu();do{printf ( "请输入要进行的操作\n" );scanf ("%d",&i);if (i<1||i>6)printf("错误数字，请重新输入\n");}while (i<1||i>6);switch (i){case 1: CreateUDG(G);system("pause"); system("cls"); break;case 2: DeleteUDG(G); system("pause"); system("cls"); break;case 3: InsertUDG(G); system("pause"); system("cls"); break;case 4: travel(&G); system("pause"); system("cls"); break;case 5: breadfirstsearch(&G); system("pause"); system("cls"); break;case 6: exit(0); break;}}return 1;}void enterqueue(int v){q.data[q.rear]=v;q.rear++;}int deletequeue(){int t;t=q.data[q.front];q.front++;return(t);}int empty(){if(q.front==q.rear)return 1;return 0;}int LocateVex(ALGraph G,char node[2]) {int i;for(i = 0 ; i < G.vexnum ; i++){if(strcmp(G.vertices[i].data,node)= =0)return i;}return -1;}int CreateUDG(ALGraph &G){int LocateVex(ALGraph G,char node[2]);void PrintUDG(ALGraph G);int i,j,k;char node1[2],node2[2];ArcNode *p,*q;printf("请输入顶点数和弧数\n");printf("例如:5,6\n");scanf("%d,%d",&G.vexnum,&G.arc num);printf("请输入各顶点\n");for(i = 0 ; i < G.vexnum ; i++){printf("第%d个\n",i+1);scanf("%s",&G.vertices[i]);G.vertices[i].firstarc = NULL;}//这里开始构造边printf("请输入边的信息\n");printf("例如:v1 v2\n");for(i = 0 ; i < G.arcnum ; i++){printf("第%d条边\n",i+1);scanf("%s %s",&node1,&node2);j = LocateVex(G,node1);k = LocateVex(G,node2);p = (ArcNode *)malloc(sizeof(ArcNode));q = (ArcNode *)malloc(sizeof(ArcNode));p->adjvex = k;q->adjvex = j;p->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p;q->nextarc = G.vertices[k].firstarc;G.vertices[k].firstarc = q;}PrintUDG(G);return 1;}int DeleteUDG(ALGraph &G){int i,j;ArcNode *p,*q;char node[2];int LocateVex(ALGraph G,char node[2]);void PrintUDG(ALGraph G);if(G.arcnum == 0){printf("请先生成图\n");return 0;}printf("请输入要删除的节点\n");scanf("%s",&node);i = LocateVex(G,node);if(i == -1){printf("无此节点\n");return 0;}else{G.vexnum--;if((p = q = G.vertices[i].firstarc) != NULL){G.arcnum--;p = p->nextarc;G.vertices[i].firstarc = p;free(q);q = p;while(p != NULL){G.arcnum--;p = p->nextarc;G.vertices[i].firstarc = p;free(q);q = p;}}for(j = 0 ; j < G.vexnum ; j++ ){if(j >= i){strcpy(G.vertices[j].data , G.vertices[j+1].data);G.vertices[j].firstarc = G.vertices[j+1].firstarc;}if(G.vertices[j].firstarc->nextarc != NULL){p = G.vertices[j].firstarc;q = p->nextarc;if(p->adjvex == i){G.vertices[j].firstarc = q;p = q;q = q->nextarc;continue;}else if(p->adjvex > i)p->adjvex--;while(q != NULL){if(q->adjvex == i){p->nextarc = q->nextarc;free(q);q = p->nextarc;}elseif(q->adjvex > i)q->adjvex--;else{p = p->nextarc;q = q->nextarc;}}}elseif( (G.vertices[j].firstarc->nextarc == NULL) && (G.vertices[j].firstarc != NULL) )if( G.vertices[j].firstarc->adjvex == i ){G.vertices[j].firstarc = NULL;}}}PrintUDG(G);return 1;}int InsertUDG(ALGraph &G){//默认一次插入一个节点吧,不然太麻烦int i,j,k,l;char node1[2],node2[2];ArcNode *p,*q;int LocateVex(ALGraph G,char node[2]);void PrintUDG(ALGraph G);if(G.arcnum == 0){printf("请先生成图\n");return 0;}printf("请输入插入节点的名称\n");printf("WARNING:绝不可以和之前的节点重名!\n");scanf("%s",&G.vertices[G.vexnum]. data);G.vertices[G.vexnum].firstarc = NULL;printf("请输入需要插入的边的数目\n");scanf("%d",&i);G.arcnum += i;G.vexnum++;printf("请输入边的信息\n");printf("例如:v6 v2\n");printf("WARNING:一定要包含刚加入的节点名称!\n");for(j = 0 ; j < i ; j++){printf("第%d条边\n",j+1);scanf("%s %s",&node1,&node2);l = LocateVex(G,node1);k = LocateVex(G,node2);p = (ArcNode *)malloc(sizeof(ArcNode));q = (ArcNode *)malloc(sizeof(ArcNode));p->adjvex = k;q->adjvex = l;p->nextarc = G.vertices[l].firstarc;G.vertices[l].firstarc = p;q->nextarc = G.vertices[k].firstarc;G.vertices[k].firstarc = q;}PrintUDG(G);return 1;}void depthfirstsearch(ALGraph *g,int vi){ArcNode *rear;printf("%s\t",g->vertices[vi].data);visited[vi]=1;rear=g->vertices[vi].firstarc;while((rear!=NULL)&&(!visited[rear->a djvex])){depthfirstsearch(g,rear->adjvex);rear=rear->nextarc;}}void travel(ALGraph *g){int v;for(v=0;v<g->vexnum;v++)if(!visited[v])depthfirstsearch(g,v); }void breadfirstsearch(ALGraph *g) {int v,t,i;ArcNode *rear;for(i = 0 ; i <g->vexnum ; i++) visited[i] = 0;for(v=0;v<g->vexnum;v++){if(!visited[v]){printf("%s",g->vertices[v].data);visited[v]=1;enterqueue(v);}while(!empty()){t=deletequeue();rear=g->vertices[t].firstarc;while((rear!=NULL)&&(!visited[rear->a djvex])){printf("%s\t",g->vertices[rear->adjvex]. data);visited[rear->adjvex]=1;enterqueue(rear->adjvex);rear=rear->nextarc;}}}}void menu(){printf("********************************* ************\n");printf("* 作者：Dick *\n");printf("* 信计1001 xxxxxxxxxx *\n");printf("*********************MENU***** ***************\n");printf("1 建立无向图\n");printf("2 删除图中节点\n");printf("3 插入节点\n");printf("4 深度优先遍历图\n");printf("5 广度优先遍历图\n");printf("6 退出程序\n");}void PrintUDG(ALGraph G){int i;ArcNode *p;for(i = 0 ; i < G.vexnum ; i++){if(G.vertices[i].firstarc != NULL){printf("与节点%s相邻的节点为:\n",G.vertices[i].data);p = G.vertices[i].firstarc;while(p != NULL){printf("%s\t",G.vertices[p->adjvex]. data);p = p->nextarc;}printf("\n");-------------精选文档-----------------可编辑}else printf("无与节点%s 相邻的节点\n",G.vertices[i].data); }} 5. 测试结果图一：菜单项图三：插入节点图一：菜单项图二：建立图图二：建立图遍历图。