数据结构实验—图的建立与遍历

数据结构实验五---图的遍历及其应用实现实验五图的遍历及其应用实现一、实验目的1．熟悉图常用的存储结构。

2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。

3．会用图的遍历解决简单的实际问题。

二、实验内容[题目] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。

该程序包括图类型以及每一种操作的具体的函数定义和主函数。

三、实验步骤（一）、数据结构与核心算法的设计描述：本实验主要在于图的基本操作，关键是图的两种遍历，仔细分析图的遍历的特点，不难发现，其符合递归的特点，因此可以采用递归的方法遍历。

本实验图的存储结构主要采用邻接表，总共分为四个模块：图的创建、位置的查找、深度优先遍历、广度优先遍历。

以下是头文件中数据结构的设计和相关函数的声明：#include#include#include#nclude#define OVERFLOW -2#define MAX_VERTEX_NUM 50 //最大顶点数#define MAXQSIZE 100# define OK 1typedef int VRType;typedef int InfoType;typedef int QElemType;typedef enum{DG,DN,UDG,UDN}GraphKind;typedef struct ArcNode // 弧结点{int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置struct ArcNode *nextarc; //链域指向vi的下一条边或弧的结点，InfoType *info; //定义与弧相关的权值，无权则为0 }ArcNode;typedef struct VNode //表头结点{char vexdata; //存放顶点信息struct ArcNode *firstarc; //指示第一个邻接点}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{ //图的结构定义AdjList vertices; //顶点向量int vexnum, arcnum; //vexnum为顶点数arcnum为弧或边的个数GraphKind kind; // 图的种类标志}MGraph;typedef struct Queue //构建循环队列{QElemType *base;int front;int rear;}Queue;void CreateGraph(MGraph &G); //图的创建void DFSTraverse(MGraph &G) ; //深度优先遍历void BFSTraverse(MGraph &G); //广度优先遍历int LocateVex(MGraph &G, char &v);//查找顶点v的位置（二）、函数调用及主函数设计void main(){int x;MGraph G;CreateGraph(G);cout<<"创建图成功!"<<endl;< p="">cout<<"1 深度优先搜索"<<endl<<"2 p="" 广度优先搜索"<<endl;<="">cin>>x;if(x==1){DFSTraverse(G);cout<<"深度优先搜索结束!"<<endl;< p="">}else if(x==2){BFSTraverse(G);cout<<"广度优先搜索结束!"<<endl;< p="">}elsecout<<"输入有误!"<<endl<<"再见!"<<endl;< p="">}（三）、实验总结由于图的基本操作在图这一章节中起着很主要的作用，所以在实验前就对实验做了充分的准备，实验的成功核心在于两种遍历的实现，因此只有充分理解遍历算法的精髓，才能更好的做好实验。

数据结构中图的建立与深度优先、广度优先遍历《数据结构》实验报告实验内容：图的建立（邻接矩阵）及其深度优先、广度优先遍历学号：姓名：一、上机实验的问题和要求（需求分析）：[ 题目]二、程序设计的基本思想，原理和算法描述：设计一个程序，建立图的邻接矩阵，并且进行图的广度优先遍历。

三、调试和运行程序过程中产生的问题及采取的措施：（略）四、源程序及注释[ 源程序] 程序名：9.cpp#include"stdio.h"#include"stdlib.h"#define INFINITY 100#define MAX_VERTEX_NUM 20#define MAX 100#define OK 1#define ERROR 0#define NULL 0typedef int VRType;typedef int VertextType;typedef int Status;typedef enum {DG,DN,UDG,UDN}GraphKind;typedef struct ArcCell{VRType adj;}ArcCell,AdjMatrix[MAX_VERTEX_NUM ][MAX_VERTEX_NUM ]; typedef struct{int vexs[MAX_VERTEX_NUM ];int arcs[4][4] ;int vexnum,arcnum;GraphKind Kind;}MGraph;int LocateVex(MGraph G,int v1){ int i;for(i=0;i<g.vexnum;i++)< p="">if(G.vexs[i]==v1)printf("%d\n",i);return i;}Status CreateUDN(MGraph &G){ int v1,v2;int i,j,k,w;printf("输入图的顶点数和弧数：");scanf("%d,%d",&G.vexnum,&G.arcnum); printf("输入顶点:");for(i=0;i<g.vexnum;i++)< p="">scanf("%d",&G.vexs[i]);for(i=0;i<g.vexnum;i++)< p="">for(j=0;j<g.vexnum;j++)< p="">G.arcs[i][j]=INFINITY ;printf("输入顶点关系：");for(k=0;k<g.arcnum;k++)< p="">{scanf("%d%d%d",&v1,&v2,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=G.arcs[i][j];printf("%d\n%d\n",G.arcs[i][j],G.arcs[j][i]);}printf("图的邻接矩阵图是:\n");for(i=0;i<g.vexnum;i++)< p="">{for(j=0;j<g.vexnum;j++)< p="">printf("%d",G.arcs[i][j]);printf("\n");}return OK;}Status Visit(int e){//输出函数printf("%d\n",e);return OK;}//PrintElement//Status(*VisitFunc)(char v);int visited[MAX];void DFS(MGraph G,int v){ int j;Visit (v);visited[v]=1;for(j=1;j<g.vexnum;j++)< p="">if(!visited[j]&&G.arcs[v][j]!=INFINITY)DFS(G,j); } void DFSTraverse(MGraph G){ int v;for(v=0;v<g.vexnum;++v)< p="">visited[v]=0;for(v=0;v<g.vexnum;++v)< p="">if(!visited[v])DFS(G,v);/* 有关队列的操作*/#define MAX SIZE 100#define QElemType int#define OVERFLOW 0typedef struct{QElemType *base;int front;int rear;}SqQueue;Status InitQueue(SqQueue &Q){ Q.base=(QElemType*)malloc(MAXSIZE* sizeof(QElemType)); if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;return 0;}Status EnQueue(SqQueue &Q,QElemType e){if(Q.rear+1==Q.front)return ERROR;Q.base[Q.rear]=e;Q.rear=Q.rear+1;return OK;}Status DeQueue(SqQueue &Q,QElemType &e){if(Q.front==Q.rear)return ERROR;e=Q.base[Q.front];Q.front=Q.front+1;return OK;}Status QueueEmpty(SqQueue Q){if(Q.front==Q.rear)return OK;else return ERROR;void BFSTraverse(MGraph &G){ int v,u,j;SqQueue Q;for(v=0;v<g.vexnum;v++)< p=""> visited[v]=0;InitQueue(Q);for(v=0;v<g.vexnum;++v)< p="">if(!visited[v]){visited[v]=1;Visit(v);EnQueue(Q,v);while(!QueueEmpty(Q)){ DeQueue(Q,u);for(j=1;j<g.vexnum;j++)< p="">if(!visited[j]&&G.arcs[v][j]!=INFINITY) { visited[j]=1;Visit(j);EnQueue(Q,j);}} }}void main(){ MGraph G;CreateUDN(G);printf("建图成功！");printf("深度优先遍历的结果:\n"); DFSTraverse(G);printf("广度优先遍历的结果:\n"); BFSTraverse(G);}五、运行结果运行结果：上一页下一页</g.vexnum;j++)<></g.vexnum;++v)<></g.vexnum;v++)<></g.vexnum;++v)<> </g.vexnum;++v)<> </g.vexnum;j++)<> </g.vexnum;j++)<> </g.vexnum;i++)<> </g.arcnum;k++)<> </g.vexnum;j++)<> </g.vexnum;i++)<> </g.vexnum;i++)<> </g.vexnum;i++)<>。

数据结构实验报告实验：图的遍历一、实验目的：1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表2、掌握图的构造方法3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法4、掌握图的深度优先遍历和广度优先原理二、实验内容：1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。

2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图3、深度优先遍历第一步中构造的图G，输出得到的节点序列4、广度优先遍历第一部中构造的图G，输出得到的节点序列三、实验要求：1、无向图中的相关信息要从终端以正确的方式输入；2、具体的输入和输出格式不限；3、算法要具有较好的健壮性，对错误操作要做适当处理；4、程序算法作简短的文字注释。

四、程序实现及结果：1、邻接矩阵：#include <stdio.h>#include <malloc.h>#define VERTEX_MAX 30#define MAXSIZE 20typedef struct{intarcs[VERTEX_MAX][VERTEX_MAX] ;int vexnum,arcnum;} MGraph; void creat_MGraph1(MGraph *g) { int i,j,k;int n,m;printf("请输入顶点数和边数:");scanf("%d%d",&n,&m);g->vexnum=n;g->arcnum=m;for (i=0;i<n;i++)for (j=0;j<n;j++)g->arcs[i][j]=0;while(1){printf("请输入一条边的两个顶点：\n");scanf("%d%d",&i,&j);if(i==-1 || j==-1)break;else if(i==j || i>=n || j>=n){printf("输入错误,请重新输入！\n");}else{g->arcs[i][j]=1;g->arcs[j][i]=1;}}}void printMG(MGraph *g) {int i,j;for (i=0;i<g->vexnum;i++){for (j=0;j<g->vexnum;j++)printf(" %d",g->arcs[i][j]);printf("\n");}printf("\n");}main(){int i,j;int fg;MGraph *g1;g1=(MGraph*)malloc(sizeof(MGraph));printf("1:创建无向图的邻接矩阵\n\n");creat_MGraph1(g1);printf("\n此图的邻接矩阵为：\n"); printMG(g1);}2、邻接链表:#include<stdio.h>#include<malloc.h>#define MAX_SIZE 10typedef struct node{int vertex;struct node *next;}node,adjlist[MAX_SIZE];adjlist g;int visited[MAX_SIZE+1];int que[MAX_SIZE+1];void creat(){int n,e;int i;int start,end;node *p,*q,*pp,*qq;printf("输入无向图的顶点数和边数:");scanf("%d%d",&n,&e);for(i = 1; i <= n ; i++){visited[i] = 0;g[i].vertex = i;g[i].next = NULL;}printf("依次输入边:\n");for(i = 1; i <= e ; i++){scanf("%d%d",&start,&end);p=(node *)malloc(sizeof(node));p->vertex = end;p->next = NULL;q = &g[start];while(q->next)q = q->next;q->next = p;p1=(node*)malloc(sizeof(node));p1->vertex = start;p1->next = NULL;q1 = &g[end];while(qq->next)q1 = q1->next;q1->next = p1;}}void bfs(int vi){int front,rear,v;node *p;front =0;rear = 1;visited[vi] = 1;que[0] = vi;printf("%d ",vi);while(front != rear){v = que[front];p = g[v].next;while(p){if(!visited[p->vertex]){visited[p->vertex]= 1;printf("%d",p->vertex);que[rear++] = p->vertex;}p = p->next;}front++;}}int main(){creat();bfs(1);printf("\n");return 0;}五．实验心得与体会：(1)通过这次实验，使我基本上掌握了图的存储和遍历，让我弄清楚了如何用邻接矩阵和邻接链表对图进行存储(2)深度优先遍历和广度优先遍历都有着各自的优点，通过程序逐步调试，可以慢慢的理解这两种遍历方法的内涵和巧妙之处。

问题描述：若用有向网表示网页的链接网络，其中顶点表示某个网页，有向弧表示网页之间的链接关系。

试设计一个网络蜘蛛系统，分别以广度优先和深度优先的策略抓取网页。

一、需求分析：1．本程序要求采用利用图实现广度优先搜索。

2．首先输入顶点的数量，然后是各顶点对应的字母，再输入各条弧（权值都置为1）。

3．在Dos界面输出从首个顶点开始的广度优先遍历序列。

4．测试数据输入输入顶点数和弧数:8 9输入8个顶点.输入顶点0:a输入顶点1:b输入顶点2:c输入顶点3:d输入顶点4:e输入顶点5:f输入顶点6:g输入顶点7:h输入9条弧.输入弧0:a b 1输入弧1:b d 1输入弧2:b e 1输入弧3:d h 1输入弧4:e h 1输入弧5:a c 1输入弧6:c f 1输入弧7:c g 1输入弧8:f g 1输出广度优先遍历: a b d h e c f g深度优先遍历: a b c d e f g h二、概要设计：抽象数据类型：图的定义：ADT Graph {数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}VR={<v,w>|v,w∈v且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作P：CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图GFirstAdjV ex(G,v)初始条件：图G存在,v是G中某个顶点操作结果：返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回“空”Next AdjV ex(G,v,w)初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点操作结果：返回v的（相对于w的）下一个邻接顶点，若w是v的最后一个邻接点，则返回“空”visit(G, k)初始条件：图G存在操作结果：访问图G中的第K个节点Locate(G, c)初始条件：图G存在操作结果：访问图G中的c顶点DFS(G, v)初始条件：图G存在操作结果：以图G中的第v个节点为起点深度优先访问图GBFS(G)初始条件：图G存在操作结果：广度优先访问图G} ADT Graph算法的基本思想：（1）图的特点是没有首尾之分，所以算法的参数要指定访问的第一个顶点。

实验项目名称：图的遍历一、实验目的应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。

二、实验内容问题描述：建立有向图，并用深度优先搜索和广度优先搜素。

输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。

三、实验仪器与设备计算机，Code::Blocks。

四、实验原理用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。

五、实验程序及结果#define INFINITY 10000 /*无穷大*/#define MAX_VERTEX_NUM 40#define MAX 40#include<>#include<>#include<>#include<>typedef struct ArCell{int adj;}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{ char name[20];}infotype;{ infotype vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;int LocateVex(MGraph *G,char* v){ int c = -1,i;for(i=0;i<G->vexnum;i++)if(strcmp(v,G->vexs[i].name)==0){ c=i; break;}return c;}MGraph * CreatUDN(MGraph *G)d:",i+1);scanf("%s",G->vexs[i].name);}for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++)G->arcs[i][j].adj=INFINITY;printf("请输入一条边依附的两个顶点和权值:\n");for(k=0;k<G->arcnum;k++){printf("第%d条边:\n",k+1);printf("起始结点:");scanf("%s",v1);printf("结束结点:");scanf("%s",v2);dj=w;G->arcs[j][i]=G->arcs[i][j];}}return G;}int FirstAdjVex(MGraph *G,int v){int i;if(v<=0 && v<G->vexnum){ dj!=INFINITY)return i;}return -1;}void VisitFunc(MGraph *G,int v){printf("%s ",G->vexs[v].name);}int NextAdjVex(MGraph *G,int v,int w){int k;if(v>=0 && v<G->vexnum && w>=0 && w<G->vexnum)dj!=INFINITY) return k;return -1;}int visited[MAX];void DFS(MGraph *G,int v)//从第v个顶点出发递归地深度优先遍历图G {int w;visited[v]=1;VisitFunc(G,v);//访问第v个结点for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w]){DFS(G,w);printf("%d ",G->arcs[v][w]);}}void DFSTraverse(MGraph *G,char *s)//深度优先遍历{int v,k;for(v=0;v<G->vexnum;v++)visited[v]=0;k=LocateVex(G,s);if(k>=0&&k<G->vexnum){for(v=k;v>=0;v--){if(!visited[v])DFS(G,v);}for(v=k+1;v<G->vexnum;v++)if(!visited[v])DFS(G,v);}}typedef struct Qnode{int vexnum;struct Qnode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue *Q){Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));if(!Q->front)exit(0);Q->front->next=NULL;return 1;}void EnQueue(LinkQueue *Q,int a )QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);p->vexnum=a;p->next=NULL;Q->rear->next=p;Q->rear=p;}int DeQueue(LinkQueue *Q,int *v){ QueuePtr p;if(Q->front==Q->rear){printf("结点不存在!\n");exit(0);}p=Q->front->next;*v=p->vexnum;Q->front->next=p->next;if(Q->rear==p)Q->front=Q->rear;return *v;}int QueueEmpty(LinkQueue *Q){if(Q->rear==Q->front)return 0;return 1;}int Visited[MAX];void BFSTraverse(MGraph *G,char *str)//广度优先遍历{int w,u,v,k;LinkQueue Q,q;for(v=0;v<G->vexnum;v++) Visited[v]=0;InitQueue(&Q);InitQueue(&q);k=LocateVex(G,str);for(v=k;v>=0;v--)if(!Visited[v]){Visited[v]=1;VisitFunc(G,v);EnQueue(&Q,v);//v入队while(!QueueEmpty(&Q)){DeQueue(&Q,&u);//出队for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))if(!Visited[w]){VisitFunc(G,v);EnQueue(&Q,w);}}}for(v=k+1;v<G->vexnum;v++)if(!Visited[v]){Visited[v]=1;VisitFunc(G,v);EnQueue(&Q,v);//v入队while(!QueueEmpty(&Q)){DeQueue(&Q,&u);//出队for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)) if(!Visited[w]){Visited[w]=1;VisitFunc(G,v);EnQueue(&Q,w);}}}}void main(){MGraph *G,b;char v[10];G=CreatUDN(&b);printf("请输入起始结点名称:");scanf("%s",v);printf("\n深度优先遍历:\n");DFSTraverse(G,v);printf("\n广度优先遍历:\n");BFSTraverse(G,v);getch();}六、实验总结实验要求输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。

实验五图的存储与遍历1、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(dfs)和广度优先遍历（BFS）操作的实现。

2、实验预备知识（1）图的存储结构：邻接矩阵表示法和邻接表表示法。

邻接矩阵表示法除了要用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外还有图的顶点数和边数。

邻接表表示法类似于树的孩子链表表示法。

（2）图的遍历方法有深度优先遍历（Depth－First Traersal）和广度优先遍历（Breadth－First Traversal），简称 DFS和BFS。

DFS对图遍历时尽可能先对纵深方向进行搜索；BFS是类似于树的按层次遍历。

3、实验内容题目1对以邻接矩阵为存储结构的图进行 DFS和 BFS遍历(1) 问题描述：以邻接矩阵为图的存储结构，实现图的DFS和BFS遍历。

(2) 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS和BFS序列。

(3) 测试数据：如图4．18所示。

(4) 实现提示：图的DFS遍历可通过递归调用或用栈来实现。

其思想是：只要当前结点未访问过，就访问该结点，沿着其一条分支深入下去，每深入一个未访问过的结点，就访问这个结点，然后从这个结点继续进行DFS遍历。

在这一过程中，若深入时遇到一个已访问过的结点，则查找是否有与这个结点相邻的下一个未访问过的结点。

若有则继续深人，否则将退回到这个结点的前一个结点，再找下一个相邻的本访问过的结点，……如此进行下去，直到所有的结点都被访问过。

BFS遍历可利用队列来帮助实现，也可以用栈。

实现方法与二叉树的层次遍历类似。

题目2对以邻接表为存储结构的图进行DFS和BFS遍历(1) 问题描述：以邻接表为存储结构，实现图的DFS和BFS遍历。

(2) 基本要求：建立一个图的邻接表存储，输出顶点的一种DFS和BFS序列。

(3) 测试数据：如图4.19所示：(4) 实现提示：以邻接表为存储结构的图的DFS和BFS算法的实现思想与以邻接矩阵为存储结构的实现是一样的。

实验五（1）：图的创建与遍历
1．实验目的：
1．掌握图的含义；
2．掌握用邻接矩阵和邻接表的方法描述图的存储结构；
3．理解并掌握深度优先遍历和广度优先遍历的存储结构。

2．实验内容：
（1）以邻接矩阵为存储结构，实现连通有向图（下图）的所有顶点出度与入度的计算。

（2）设计两个算法分别实现深度优先遍历和广度优先遍历。

1 调试程序。

设计一个有向图和一个无向图，任选一种存储结构，完成有向
图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。

邻接矩阵作为存储结构的运行结果：
邻接链表作为存储结构的运行结果：
实验报告要求
画出你所设计的图，写出两种方法的遍历序列。

邻接矩阵：
V0 V1 V2 V3 V4 V5 V6 V7
V0 0 1 1 0 0 0 0 0 V1 1 0 0 1 1 0 0 0 V2 1 0 0 0 0 1 1 0 V3 0 1 0 0 0 0 0 1 V4 1 0 0 0 0 0 0 1 V5 0 1 0 0 0 0 1 0 V6 0 1 0 0 0 1 0 0 V7 0
1
1
V6 V4 V5 V7 V2 V3 V1 V0 图G 的示例
V0 0 2 1 ^
V1 1 4 3 ^ 0 ^ V2 2 6 5 0 ^ V3 3 4 1 ^
V4 4 7 1 ^
V5 5 6 2 ^
V6 6 5 2 ^
V7 7 4 3 ^
深度遍历为：0→2→6→5→1→4→7→3
广度遍历为：3→7→1→4→0→2→6→5。

//图的建立#include <stdio.h>#define MAX_VERTEX_NUM 20//图的数据结构typedef struct{int adj;int *info; //该弧相关信息的指针}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];struct MGraph{char vertex[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum, arcnum;};//返回顶点在数组的下标int LocateVex(MGraph G,char v){int j=0,i;for(i=0;i<G.vexnum;++i)if(G.vertex[i]==v){j=i;break;}return j;}//创建无向图void CreateUDG(MGraph &G){int i,j,k;char v1,v2,t;printf("请输入无向图G的顶点数,边数:\n");scanf("%d%d",&G.vexnum,&G.arcnum);printf("请输入%d个顶点的值,空格隔开:\n",G.vexnum);for(i=0;i<G.vexnum;++i){scanf("%c%c",&t,&G.vertex[i]);}printf("请输入%d条边的顶点(如0 1):\n",G.arcnum);for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=0;}for(k=0;k<G.arcnum;++k){scanf("%c%c%c%c",&t,&v1,&t,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j].adj=G.arcs[j][i].adj=1;}}//输出图的邻接矩阵void Display(MGraph G){int i,j;printf("该图的邻接矩阵为：\n");for(i=0;i<G.vexnum;++i){for(j=0;j<G.vexnum;++j)printf("%d ",G.arcs[i][j].adj);printf("\n");}}//主函数int main(){MGraph G;CreateUDG(G);Display(G);return 0;}//图的遍历#include<stdio.h>#include<malloc.h>#define MaxVerNum 50struct edgenode{int endver; //该边所指向的顶点的位置int inform;edgenode* edgenext;//指向下一条边的指针};struct vexnode{char vertex; //顶点信息（字符型）edgenode* edgelink;//指向第一条依附于该顶点的指针};struct Graph //图信息{vexnode adjlists[MaxVerNum];int vexnum,arcnum;//无向图的当前顶点和边数};struct QueueNode{//队列的定义及相关函数的实现int data;QueueNode* next;};struct QueueList{QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){*q=(QueueNode *)malloc(sizeof(QueueNode));q->data=e;q->next=NULL;if(Q==NULL)return;if(Q->rear==NULL)Q->front=Q->rear=q;else{Q->rear->next=q;Q->rear=Q->rear->next;}}void DeQueue(QueueList* Q,int* e){if (Q==NULL)return;if (Q->front==Q->rear){*e=Q->front->data;Q->front=Q->rear=NULL;}else{*e=Q->front->data;Q->front=Q->front->next;}}void CreatAdjList(Graph* G)//创建图{int i,j,k;edgenode* p1;edgenode* p2;printf("请输入顶点数和边数:\n");scanf("%d,%d",&G->vexnum,&G->arcnum);printf("开始输入顶点信息:\n");for (i=0;i<G->vexnum;i++){scanf("%d",&G->adjlists[i].vertex);G->adjlists[i].edgelink=NULL;}printf("开始输入边表信息:\n");for (k=0;k<G->arcnum;k++){printf("请输入边<Vi,Vj>对应的顶点:");scanf("%d,%d",&i,&j);p1 =(edgenode *)malloc(sizeof(edgenode));p1->endver=j;//endve指该边所指向的顶点的位置p1->edgenext=G->adjlists[i].edgelink;//edgenext指向下一条边的指针G->adjlists[i].edgelink=p1;// edgelink指向第一条依附于该顶点的指针p2 =(edgenode *)malloc(sizeof(edgenode));p2->endver=i;p2->edgenext=G->adjlists[j].edgelink;G->adjlists[j].edgelink=p2;//因为是无向图，所以有两次建立边表的过程}void PrintGaph(Graph * G)//无向图的邻接表的输出{edgenode *p;for(int k=1;k<=G->vexnum;k++){printf("%d",G->adjlists[k]. vertex);p=G->adjlists[k].edgelink;while(p!=NULL){printf("%d",p->endver);p=p->edgenext;if(p!=NULL)printf("->");}printf("\n");}}void DFS(Graph *G,int i,int visit[]) //深度优先遍历,从第v个顶点出发递归地深度优先遍历无向图G{printf("%d",G->adjlists[i].vertex);printf(" ");visit[i]=1; //设置访问标志数组，未访问为0，访问后后为1edgenode *p=new edgenode;p=G->adjlists[i].edgelink; //指向第一条依附于该顶点vi的边的指针if(G->adjlists[i].edgelink&&!visit[p->endver]){ //指向第一条依附于该顶点vi 的便得指针非空，且顶点位被访问DFS(G,p->endver,visit); //递归自我调用}}void DFStraversal(Graph *G,char c) //深度优先遍历结果输出{printf("该图的深度优先遍历结果为:\n");int visit[MaxVerNum];for(int i=0;i<G->vexnum;i++)visit[i]=0;//全部初始化为0，即未访问状态}int m;for (i=0;i<G->vexnum;i++){if (G->adjlists[i].vertex==c)//根据字符查找序号{m=i;DFS(G,i,visit);//调用上面的函数break;}}for(i=0;i<G->vexnum;i++)//继续访问未被访问的结点{if(visit[i]==0)DFS(G,i,visit);}printf("\n");}void BFS(Graph* G,int v,int visit[])//广度优先遍历{QueueList *Q=new QueueList;Q->front=Q->rear=NULL;//初始化队列EnQueue(Q,v);//v入队列while(Q->rear!=NULL){int e=0;DeQueue(Q,&e);//对头（指定的）元素出队并设置为eprintf("%d",G->adjlists[e].vertex);//输出定点信息printf(" ");visit[e]=1;edgenode* p =(edgenode *)malloc(sizeof(edgenode));p=G->adjlists[e].edgelink;//指向第一天依附于该顶点的边的指针if(p){int m=p->endver;//该边所指向的顶点的位置if(m==0){EnQueue(Q,m);while(visit[m]==0){p=p->edgenext;if(p==NULL)break;m=p->endver;EnQueue(Q,m);}}}}}void BFStraversal(Graph *G,char c){printf("该图的广度优先遍历结果为:\n");int visited[MaxVerNum];for (int i=0;i<G->vexnum;i++){visited[i]=0;}int m;for (i=0;i<G->vexnum;i++){if (G->adjlists[i].vertex==c)//顶点信息{m=i;BFS(G,i,visited);break;}}for(i=0;i<G->vexnum;i++)//继续访问未被访问的结点{if(visited[i]==0)BFS(G,i,visited);}printf("\n");}void main(){Graph * G=(Graph *)malloc(sizeof(Graph));CreatAdjList(G);// PrintGaph(G);char ch;printf("请输入开始遍历的顶点:\n");scanf("%d",&ch);DFStraversal(G,ch);BFStraversal(G,ch); }。

实验八图的创建与遍历实验目的：通过上机实验进一步掌握图的存储结构及基本操作的实现。

实验内容与要求：分别基于邻接矩阵和邻接表存储结构实现图的基本运算，要求：⑴能根据输入的顶点、边/弧的信息建立图；⑵实现图中顶点、边/弧的插入、删除；⑶实现对该图的深度优先遍历；⑷实现对该图的广度优先遍历。

源程序：#include<stdio.h>#include<stdlib.h>#define intinity 1024#define maxvex 20typedef struct{char vex[maxvex];int arcs[maxvex][maxvex];}Mgraph;\\数组式结构体void Createmgraph(Mgraph &G,int n)\\创建邻接矩阵图函数，这个简单按照一般步骤就可以了{int i,j;printf("请输入顶点\n");for(i=1;i<=n;i++){scanf("%c",&G.vex[i]);fflush(stdin);}printf("请输入邻接矩阵(先行后列)\n");for(i=1;i<=n;i++)for(j=1;j<=n;j++){scanf("%d",&G.arcs[i][j]);fflush(stdin);}printf("创建图的邻接矩阵为\n");for(i=1;i<=n;i++)printf("%3c",G.vex[i]);\\这里动脑筋使他输出的界面看起来就像是一个矩阵，对位置和空格进行了调整。

printf("\n");for(i=1;i<=n;i++){ printf("%c",G.vex[i]);for(j=1;j<=n;j++)printf("%2d ",G.arcs[i][j]);printf("\n");}}void Insertmgraph(Mgraph &G,int n)\\插入函数，这里有个缺陷，只能在尾部插入，那就简单了{int i,j;printf("请输入插入的节点\n");scanf("%c",&G.vex[n+1]);printf("请输入扩建的邻接表(先行后列)\n");for(j=1;j<=(n+1);j++){scanf("%d",&G.arcs[n+1][j]);fflush(stdin);}for(i=1;i<(n+1);i++){scanf("%d",&G.arcs[i][n+1]);fflush(stdin);}printf("输出新的图\n");for(i=1;i<=(n+1);i++)printf("%3c",G.vex[i]);printf("\n");for(i=1;i<=(n+1);i++){ printf("%c",G.vex[i]);for(j=1;j<=(n+1);j++)printf("%2d ",G.arcs[i][j]);printf("\n");}}void Deleatmgraph(Mgraph &G,int n,int m)\\删除函数，这里不局限在哪一个点，删哪一个都可以，不过删最后对下面有好处。

课程名称：数据结构开课实验室：计算中心204室2011年10 月日年级、专业、班学号姓名成绩实验项目名称图的建立和遍历指导教师教师评语教师签名：年月日一、实验内容和目的目的：撑握图的建立和遍历，熟悉图的建立和输出，还有两种遍历（深度和广度优先遍历）。

内容：编出图的程序，能够体图的性质、内容和算法。

二、上机实验环境计算中心204；操作系统：Microsoft Visual C++；软件平台：Microsoft Visual C++ 三、上机操作方法、步骤打开计算机进入WindowsXP→在桌面建立自己的工作目录→进入Microsoft Visual C++ 6.0→文件/新建/文件/C++ Source File/位置/命名→输入源程序→编译/组建→运行。

四、设计分析：图是一种复杂的非线性结构。

图结构在人工智能、计算机科学等领域有着广泛的运用。

学好它就得了解结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。

在图结构中，对结点的前趋和后继个数都不加限制的，即结点之间的关系是任意的。

#include <stdio.h>#include<malloc.h>#define maxnode 30#define null 0#define m 20typedef struct st_arc{int adjvex;int weight;struct st_arc *nextarc;}arcnode;typedef struct{int vertex;struct st_arc *firstarc;}vernode;typedef vernode adjlist[maxnode];int queue[maxnode];void dfs(adjlist g,int k,int visited[]) //从顶点K出发深度优先搜索{arcnode *p;int w;visited[k]=1;printf("%d ",g[k].vertex);p=g[k].firstarc;while(p!=null){w=p->adjvex;if(visited[w]==0)dfs(g,w,visited);p=p->nextarc;}}void bfs(adjlist g,int k,int visited[]) //从顶点K出发广度优先搜索{int front=0,rear=1,w;arcnode *p;visited[k]=1; //访问初始顶点printf("%d ",k);queue[rear]=k; //初始顶点入队列while(front!=rear){front=(front+1)%m;w=queue[front]; //按访问次序依次出队列p=g[w].firstarc;while(p!=null){if(visited[p->adjvex]==0){visited[p->adjvex]=1;printf("%d ",p->adjvex);rear=(rear+1)%m;queue[rear]=p->adjvex;;}p=p->nextarc;}}}void trave_bfs(adjlist g,int n) //数组visited标志图中的顶点是否已被访问{int i,visited[maxnode];for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)bfs(g,i,visited);}void trave_dfs(adjlist g,int n) //数组visited标志图中的顶点是否已被访问{int i,visited[maxnode];for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)dfs(g,i,visited);}void print(adjlist g,int n){arcnode *q;int i;printf("输出的是所建立无向图的邻接表结构:\n");for(i=1;i<=n;i++){printf("\t%d\t",i);printf("%d->",g[i].vertex);q=g[i].firstarc;while(q!=null){printf("%d,",q->adjvex);printf("%d->",q->weight);q=q->nextarc;}printf("Null");printf("\n");}}void main(){arcnode *p,*q;adjlist g;int i,j,n,k,w,e;printf("请输入建立的无向图所包含的顶点总个数和总边数(用逗号隔开):");scanf("%d,%d",&n,&e);for(k=1;k<=n;k++){getchar();printf("\t输入每个顶点的信息，必须输入整数值:",k);scanf("%d",&g[k].vertex);g[k].firstarc=null; //对顺序存储部分初始化}for(k=1;k<=e;k++){printf("输入所有边的信息,（起始顶点,终止顶点和该边的权值 %d 如1,2,3）:",k);scanf("%d,%d,%d",&i,&j,&w);q=(arcnode *)malloc(sizeof(arcnode));q->adjvex=j;q->weight=w;q->nextarc=g[i].firstarc;g[i].firstarc=q;p=(arcnode *)malloc(sizeof(arcnode));p->adjvex=i;p->weight=w;p->nextarc=g[j].firstarc;g[j].firstarc=p;}print(g,n);printf("\n");printf("输出深度优先搜索遍历:");trave_dfs(g,n);printf("\n");printf("输出广度优先搜索遍历:");trave_bfs(g,n);printf("\n");}五、源程序与运行结果：五、上机实践收获和体会:经过学习和上机实践，我基本了解和撑握图的基本概念和两种常用的存储结构，对图的遍历、最小生成树、最短路弃、拓扑排序等理解，撑握图的有关术语和存储表示。

实验八图的创建与遍历实验目的：掌握图的邻接矩阵、邻接表、十字链表和邻接多重表四种存储结构，能够实现在任意一种存储结构上的创建和遍历两种基本操作实验要求：1、认真阅读和掌握教材上和本实验相关内容和算法（见P161~170）。

2、上机将图的任意一种存储表示的创建和遍历（DFS和BFS至少实现一种）算法实现。

3、实现下面实验内容要求的功能，并能够进行简单的输入输出验证。

实验内容：1、图的创建部分编程实现图的任意一种存储表示的创建算法，要求能够进行简单的输入输出验证。

#include <iostream.h>typedef struct Graph{char vexs[10];int arc[10][10];int vexnum;int arcnum;}Graph;int locatevex(Graph G,char x){int i=0;while(G.vexs[i]!=x)i++;return i;}void creatgraph(Graph &G){int i,j,k;char v1,v2;cin>>G.vexnum>>G.arcnum;for(i=0;i<G.vexnum;i++)cin>>G.vexs[i];for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arc[i][j]=0;for(k=0;k<G.arcnum;k++){cin>>v1>>v2;i=locatevex(G,v1);j=locatevex(G,v2);G.arc[i][j]=1;G.arc[j][i]=1;}}void printgraph(Graph G){for(int i=0;i<G.vexnum;i++)cout<<G.vexs[i]<<" ";cout<<endl;for(i=0;i<G.vexnum;i++)for(int j=0;j<G.vexnum;j++){if(G.arc[i][j]==1)cout<<G.vexs[i]<<" ->"<<G.vexs[j]<<" ";}}int FirstAdjVex(Graph G,char v){ /* 初始条件: 图G存在,v是G中某个顶点*//* 操作结果: 返回v的第一个邻接顶点的序号。

《数据构造》上机试验汇报—有向图旳邻接表旳建立及遍历福州大学数计学院《数据构造》上机试验汇报专业和班级:信息计算科学与应用数学6班学号姓名成绩试验名称图旳有关操作试验内容有向图旳邻接表旳建立及遍历实【试验目旳】验 ,(掌握图旳存储思想及其存储实现。

目 ,(掌握图旳深度、广度优先遍历算法思想及其程序实现。

旳 ,(掌握图旳常见应用算法旳思想及其程序实现。

和要求【试验内容】1. 键盘输入数据，建立一种有向图旳邻接表。

2(在有向图旳邻接表旳基础上计算各顶点旳度。

3(采用邻接表存储实既有向图旳深度优先遍历。

4(采用邻接表存储实既有向图旳广度优先遍历。

【重要程序】#include<stdio.h>#include<stdlib.h>#include<conio.h>#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define OVERFLOW 0int visited[MAX_VERTEX_NUM];typedef struct ArcNode //表结点问 { 题 int adjvex; //该弧所指向旳顶点旳位置描 struct ArcNode *nextarc;//指向下一条弧旳指针char *info; //该弧有关信息旳指针述 }ArcNode; 和主 typedef struct VNode //头结点{ 要 char data; //顶点信息步 ArcNode *firstarc; //第一种表结点旳地址，指向第一条依附顶骤点旳弧旳指针}VNode,AdjList[MAX_VERTEX_NUM]; //头结点，头结点旳次序表AdjList[]类型typedef struct //图构造{AdjList vertices;int vexnum,arcnum; //图旳目前顶点数与弧数}ALGraph;typedef struct QNode //用于BFS遍历旳附设链队列结点构造{int data;struct QNode *next;}QNode,*QueuePtr;typedef struct //链队列{QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q) //初始化链队{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front) exit(OVERFLOW);Q.front->next=NULL;return OK;}int EnQueue(LinkQueue &Q,int e) //元素e入队 {QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p) exit(OVERFLOW);p->next=NULL;p->data=e;Q.rear->next=p;Q.rear=p;return OK;}int DeQueue(LinkQueue &Q,int &e)//队首元素出队,由e返回其值{QueuePtr p;if(Q.front==Q.rear) exit(OVERFLOW);e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return OK;}int EmptyQueue(LinkQueue Q) //判断队列Q与否为空{if(Q.front==Q.rear)return 1;return 0;}int LocateVex(ALGraph G,char v) //查找值为v旳顶点在顶点向量G.vexs[]中旳位置{int i;for(i=0;i<G.vexnum;i++)if(v==G.vertices[i].data)return i;return -1;}int FirstAdjVex(ALGraph G,char v)//返回v旳第一种邻接顶点旳序号{int i;ArcNode *p;i=LocateVex(G,v); //i为顶点v在图G中旳序号if(i==-1)return -1;p=G.vertices[i].firstarc;if(p)return p->adjvex;elsereturn -1;}int NextAdjVex(ALGraph G,char v,char w)//返回v旳(相对于w)旳下一种邻接顶点旳序号{int i,j;ArcNode *p,*q;i=LocateVex(G,v);j=LocateVex(G,w);if(i==-1||j==-1||i==j)return -1;p=G.vertices[i].firstarc; //p指向v旳邻接顶点链表中旳第一种邻接顶点while(p->nextarc&&p->adjvex!=j) //找到邻接顶点wp=p->nextarc;if(p->nextarc) //找到邻接顶点w，且w非v旳最后一种邻接顶点{q=p->nextarc;return q->adjvex; //返回v旳(相对于w)旳下一种邻接顶点旳序号}elsereturn -1; //没有找到w或w是v旳最终一种邻接顶点}int Visit(char v){printf("%c ",v);return OK;}int CreateDG(ALGraph &G) //采用邻接表表达，构造有向图G {int v,e,i,j,t;ArcNode *p,*q;char tail,head;printf("输入顶点个数:");scanf("%d",&v);if(v<0)return ERROR;G.vexnum=v;printf("输入弧旳条数:");scanf("%d",&e);if(e<0)return ERROR;G.arcnum=e;printf("建立DG:\n");for(t=0;t<G.vexnum;t++) //建立头结点次序表{fflush(stdin);printf("输入%d旳信息:",t+1);scanf("%c",&G.vertices[t].data);G.vertices[t].firstarc=NULL; //初始化该头结点指针域}for(t=0;t<G.arcnum;t++) //建立表结点链表(每个顶点旳邻接顶点链表){fflush(stdin);printf("输入弧旳信息(弧尾-弧头)");scanf("%c%*c%c",&tail,&head);i=LocateVex(G,tail);j=LocateVex(G,head);if(i==-1||j==-1||i==j)return ERROR;p=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex=j;p->info=NULL;p->nextarc=NULL;if(!G.vertices[i].firstarc)G.vertices[i].firstarc=p;else{//找尾结点for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);q->nextarc=p; //插入到链表尾}}}int DFS(ALGraph G,int v) //从第v个顶点出发，递归旳深度优先遍历有向图G{int w;visited[v]=-1;printf("%c ",G.vertices[v].data);w=FirstAdjVex(G,G.vertices[v].data);for(;w>=0;w=NextAdjVex(G,G.vertices[v].data,G.vertices[w].data)) if(!visited[w])DFS(G,w); //对v旳尚未访问旳邻接顶点w递归调用DFS()return OK;}int DFSTraverse(ALGraph G) //深度优先搜索遍历图G { int i;for(i=0;i<G.vexnum;i++)visited[i]=0;for(i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);return OK;}int BFSTraverse(ALGraph G,int(*visit)(char v)) { LinkQueue Q;int v,w,u;for(v=0;v<G.vexnum;v++)visited[v]=0;InitQueue(Q);for(v=0;v<G.vexnum;v++){if(!visited[v]){visited[v]=1;Visit(G.vertices[v].data);}EnQueue(Q,v);while(!EmptyQueue(Q)){DeQueue(Q,u);for(w=FirstAdjVex(G,G.vertices[u].data);w>0;w=NextAdjVex (G,G.vertices[u].data,G.vertices[w].data))if(!visited[w]){visited[w]=1;Visit(G.vertices[w].data);EnQueue(Q,w);}}}return OK;}void main(){ALGraph G;printf("建立有向图G\n");if(CreateDG(G)){printf("深度优先搜索旳次序:"); DFSTraverse(G);printf("\n");printf("广度优先搜索旳次序:"); BFSTraverse(G,Visit);}printf("\n");}【成果截图】。

摘要图(Gｒaph)是一种复杂的非线性结构。

图可以分为无向图、有向图。

若将图的每条边都赋上一个权，则称这种带权图网络。

在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。

在图结构中，对结点（图中常称为顶点)的前趋和后继个数都是不加以限制的,即结点之间的关系是任意的。

图中任意两个结点之间都可能相关。

图有两种常用的存储表示方法:邻接矩阵表示法和邻接表表示法。

在一个图中，邻接矩阵表示是唯一的，但邻接表表示不唯一。

在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍历）及求图中顶点的度。

当然对于图的广度优先遍历还利用了队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)来实现。

这不仅让我们巩固了之前学的队列的基本操作，还懂得了将算法相互融合和运用。

目录第一章课程设计目的..................................................................................... 错误!未定义书签。

第二章课程设计内容和要求....................................................................... 错误!未定义书签。

2．1课程设计内容.................................................................................. 错误!未定义书签。

2.1.1图的邻接矩阵的建立与输出ﻩ错误!未定义书签。

2．１.２图的邻接表的建立与输出............................................... 错误!未定义书签。

2.1.3图的遍历的实现.................................................................... 错误!未定义书签。

数据结构实验报告图的遍历数据结构实验报告：图的遍历引言在计算机科学中，图是一种重要的数据结构，它由节点和边组成，用于表示不同实体之间的关系。

图的遍历是一种重要的操作，它可以帮助我们了解图中节点之间的连接关系，以及找到特定节点的路径。

在本实验中，我们将讨论图的遍历算法，并通过实验验证其正确性和效率。

深度优先搜索（DFS）深度优先搜索是一种常用的图遍历算法，它通过递归或栈的方式来遍历图中的节点。

在实验中，我们实现了深度优先搜索算法，并对其进行了测试。

实验结果表明，深度优先搜索算法能够正确地遍历图中的所有节点，并找到指定节点的路径。

此外，我们还对算法的时间复杂度进行了分析，验证了其在不同规模图上的性能表现。

广度优先搜索（BFS）广度优先搜索是另一种常用的图遍历算法，它通过队列的方式来遍历图中的节点。

在实验中，我们也实现了广度优先搜索算法，并对其进行了测试。

实验结果显示，广度优先搜索算法同样能够正确地遍历图中的所有节点，并找到指定节点的路径。

我们还对算法的时间复杂度进行了分析，发现其在不同规模图上的性能表现与深度优先搜索算法相近。

实验结论通过本次实验，我们深入了解了图的遍历算法，并验证了其在不同规模图上的正确性和效率。

我们发现深度优先搜索和广度优先搜索算法都能够很好地应用于图的遍历操作，且在不同情况下都有良好的性能表现。

这些算法的实现和测试为我们进一步深入研究图的相关问题提供了重要的基础。

总结图的遍历是图算法中的重要操作，它为我们提供了了解图结构和节点之间关系的重要手段。

本次实验中，我们实现并测试了深度优先搜索和广度优先搜索算法，验证了它们的正确性和效率。

我们相信这些算法的研究和应用将为我们在图相关问题的研究中提供重要的帮助。

实验四数据结构图的建立与遍历实验类型：综合性实验时数： 2 学时一、实验目的1. 掌握图的基本存储方法；2. 掌握有关图的操作算法并用高级语言实现；3. 熟练掌握图的两种搜索路径的遍历方法。

二、实验设备Windows 计算机（含Visual C++ 6.0）。

三、实验原理1. 图是由若干个顶点和若干条边构成的结构，每个顶点具有任意多个前驱和后继。

顶点是一些具体对象的抽象，而边是对象间关系的抽象。

图是一种复杂的数据结构，其信息包括两部分：图中数据元素即顶点的信息，元素间的关系（顶点之间的关系）——边或者弧的信息。

2. 图的常用存储结构包括邻接矩阵存储、邻接表存储、十字链表存储以及邻接多重表存储。

3. 邻接表存储法类似于树的孩子链表表示法。

它对图中的每个顶点建立一个带头节点的线性链表，用于存储图中与顶点相邻接的边或弧的信息。

头节点中存放该顶点的信息。

所有头节点用一个顺序表存放。

4. 邻接表存储图很容易找到任一顶点的邻接点，但是要判定任意两个顶点之间是否有边或弧相连，则需搜索第i 个或第j 个链表，不及邻接矩阵方便。

四、实验内容及步骤（一）实验内容假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。

(二)实验步骤1. 定义结点结构，定义图结构。

2. 存储图信息；3. 定义求任意两点最短路径函数；4. 写出主函数。

(三)实验提示typedef struct node{ int no;float wgt;struct node *next;}edgenode;typedef struct{ char vtx;edgenode *link;}vexnode;typedef vexnode Graph[n];void Floyd(Graph G, float A[n][n], int p[n][n]) {int i, j, k;for (i=0; i<n; i++)for(j=0;j<n;j++){A[i][j]=G[i][j];P[i][j]=-1;}for (k=0; k<n; k++)for (i=0; i<n; i++)for (j=0; j<n; j++) if(A[i][k] +A[k][j]<A[i][j]){P[i][j]=k;A[i][j]=A[i][k]+A[k][j]; }}五、思考题1. 判断两点是否可达。

图的建立与遍历实验报告------------图的建立与遍历姓名:曹庆松班级:1104学号:1111611512实验日期:2012.10.15报告撰写日期:2012.10.16一、实验目的:1、熟悉图的概念、存储结构和遍历方法。

2、以邻接表为存储结构，掌握无向图的基本操作和实现方法。

3、以邻接表为存储结构，掌握无向图的深度优先遍历的算法实现。

二、实验内容:以邻接表为存储结构，编写程序实现。

1、要求通过键盘输入图的顶点，以及每一条边的两个顶点从而建立无向。

为了简化实验，顶点用数字表示。

2、在以上实验的基础上，实现无向图的深度优先遍历算法。

要求以用户给定的顶点为起始点，显示深度优先遍历的次序。

三、程序代码及结果展示:#include "stdafx.h"#include<stdio.h>#include<stdlib.h>#include <malloc.h>#define MAX_VERTER_NUM 20typedef struct ArcNode{ //表节点int adjvex; //邻接点struct ArcNode *nextarc; //指向下一条弧的指针}ArcNode;typedef struct VNode{ //头结点int data; //定点信息ArcNode * firstarc; //指向第一个依附该顶点的弧的指针}VNode,AdjList[MAX_VERTER_NUM];typedef struct{ //图AdjList vertices; //顶int vexnum,arcnum;//图的顶点数和弧数int Kind;// 图的种类标志}ALGraph;// 对图 G 作深度优先遍历int LocateVex(ALGraph * G,int v) //寻找节点V的位置 { int k,n;for(k=0;k<G->vexnum;k++){ if(G->vertices[k].data==v){n=k;break;}}return n;}int n=1;int visited[MAX_VERTER_NUM]; void DFS(ALGraph *G,int v)//递归调用{ArcNode *p;>vertices[v].firstarc; p=G-if(n<G->vexnum+1){printf(" V%d ",G->vertices[v].data);n++;}visited[v]=1;while(p){if(!visited[p->adjvex])DFS(G,p->adjvex);p=p->nextarc;}}void DFSVisited(ALGraph * G)//深度遍历{int v;int n;printf("请输入遍历的起始的顶点:");scanf("%d",&n);n"); printf("递归深度优先遍历点顺序: \DFS(G,n-1);for(v=0;v<G->vexnum;v++)visited[v]=0;for(v=0;v<G->vexnum;v++)if(!visited[v])DFS(G,v);}void Insertadj(ALGraph * G,int i,int j) //插入邻接点的下标 { ArcNode *a1,*a2;a1=(ArcNode *)malloc(sizeof(ArcNode));a1->adjvex=j;a1->nextarc=NULL;if(G->vertices[i].firstarc==NULL){G->vertices[i].firstarc=a1;}else{a2=G->vertices[i].firstarc;while(a2->nextarc){a2=a2->nextarc;}a2->nextarc=a1;}}void Init_ALGraph(ALGraph * G) //初始化图并建图 { int v,v1,v2,i,j,q,p;int m=0;printf("请输入顶点数:");scanf("%d",&G->vexnum);printf("请输入边数:");scanf("%d",&G->arcnum);for(v=0;v<G->vexnum;v++){printf("顶点 V%d:",(v+1));scanf("%d",&(G->vertices[v].data));>vertices[v].firstarc=NULL; G-}for(v=0;v<G->arcnum;v++) {printf("请输入点点: ");scanf("%d%d",&v1,&v2);i=LocateVex(G,v1); //v1的位置j=LocateVex(G,v2); //v2的位置Insertadj(G,i,j);Insertadj(G,j,i);}}int main(int argc,char **argv) {ALGraph G;Init_ALGraph(&G);//初始化图并建图DFSVisited(&G);//深度优先遍历printf("\n");return 0;}四、实验总结:通过本实验，我对图的存储结构、图的遍历等有了比较深的理解与运用，图的遍历和树的遍历很类似，但是却比树的遍历复杂很多。

实验图的建立与遍历姓名：曹国君梁辰唐琪皓黄悦班级：信息1班学号:09125676 09125675 09125672 09125673 实验时间：第9周1.问题描述输入图的顶点和边的信息建立图,并对其进行深度和广度遍历,输出遍历结果。

2.数据结构设计template <class ElemType>void AdjMatrixUndirGraph<ElemType>::InsertArc(int v1, int v2)// 操作结果：插入依附顶点v1和v2的边{if (v1 < 0 || v1 >= vexNum)throw Error("v1不合法!"); // 抛出异常if (v2 < 0 || v2 >= vexNum)throw Error("v2不合法!"); // 抛出异常if (v1 == v2)throw Error("v1不能等于v2!");// 抛出异常if (Matrix[v1][v2] == 0) { // 原无向图中没有边(v1, v2)arcNum++;Matrix[v1][v2] = 1;Matrix[v2][v1] = 1;}}template <class ElemType>void BFS(const AdjMatrixUndirGraph<ElemType> &g, int v, void (*Visit)(constElemType &))// 初始条件：存在图g// 操作结果：从顶点v出发进行广度优先搜索{LinkQueue<int> q;int u, w;ElemType e;g.SetTag(v, VISITED); // 作访问标志g.GetElem(v, e); // 取顶点v的数据元素值Visit(e); // 访问顶点vq.EnQueue(v); // 顶点v入队while (!q.Empty()) {q.DelQueue(u);for (w = g.FirstAdjVex(u); w != -1; w = g.NextAdjVex(u, w))if (g.GetTag(w) == UNVISITED){ // 对u尚未访问过的邻接顶点w 进行访问g.SetTag(w, VISITED);g.GetElem(w, e);Visit(e);q.EnQueue(w);}}}template <class ElemType>void DFS(const AdjMatrixUndirGraph<ElemType> &g, int v, void (*Visit)(const ElemType &))// 初始条件：存在图g// 操作结果：从顶点v出发进行深度优先搜索{ElemType e;g.SetTag(v, VISITED); // 设置顶点v已访问标志g.GetElem(v, e); // 取顶点v的数据元素值Visit(e); // 访问顶点vfor (int w = g.FirstAdjVex(v); w != -1; w = g.NextAdjVex(v, w)) if (g.GetTag(w) == UNVISITED)DFS(g, w , Visit); // 从v的尚未访问过的邻接顶点w开始进行深度优先搜索}3.算法设计#include "assistance.h" // 实用程序软件包#include "adj_matrix_undir_graph.h" // 无向图邻接矩阵#include "dfs.h" // 图的深度优先遍历#include "bfs.h" // 图的广度优先遍历int main(void){try // 用try封装可能出现异常的代码{int n=0, i, j, k, l;cout<<"请输入图的顶点个数：";cin>>n;if (n<=0||n>=26)throw Error("节点输入错误！");char a='A' ;char vexs[26];int m[26][26] ;for (i=0; i<n; i++){for (j=0; j<n; j++){m[i][j]=0;}}for(i=0; i<n; i++){vexs[i]=a;a++;}cout<<"输入边的两个顶点:（输入-1 -1结束）" ;cin>>k;cin>>l;if (k>=n||l>=n)throw Error("节点输入错误！");m[k][l]=1;m[l][k]=1;while (k!=-1||l!=-1){cout<<"输入边的两个顶点:（输入-1 -1结束）" ;cin>>k;cin>>l;if (k>=n||l>=n)throw Error("节点输入错误！");m[k][l]=1;m[l][k]=1;}AdjMatrixUndirGraph<char> g(vexs, n);AdjMatrixUndirGraph<char> g1(vexs, n);for(int u=0; u<n; u++){for(int v=0; v<n; v++){if( m[u][v]==1){ g.InsertArc(u,v);g1.InsertArc(u,v);} }}cout << "原有图:" << endl;g.Display(); // 显示图gcout << endl;system("PAUSE"); // 调用库函数system()int v=0;cout<<"请输入开始遍历的顶点"<<endl;cin>>v;if (v>=n)throw Error("节点输入错误！");cout << "深度优先遍历:";DFS<char>(g, v, Write<char>);// <char>用于确定函数模板参数cout << endl;system("PAUSE");cout << "广度优先遍历:";BFS(g1, v, Write<char>); // 对图g进行广度优先遍历cout << endl;}catch (Error err) // 捕捉并处理异常{err.Show(); // 显示异常信息}system("PAUSE"); // 调用库函数system()return 0; // 返回值0, 返回操作系统}4.测试与运行图的建立与遍历数据测试实验序号输入输出节点数相连的边开始遍历的点深度遍历广度遍历备注1 -1 / / / / 报错2 2 <1,3> / / / 报错3 3 <1,0>4 / / 报错4 2 <0.1> 0 A B A B /5 3 <0,1> <1,2> 0 A B C A B C /6 3 <0,2> <2,1> 2 C A B C A B /7 5 <0,2> <0,1><2,3> <1,4>2 C A B E D C A D B E /8 5 <0,1> <1,2><1,3> <1,4>0 A B C D E A B C D E /9 5 <0,1> <1,2><1,3> <1,4>3 D B A C E D B A C E /10 9 <0,1> <1,2><2,3> <3,7><3,4> <4,5><4,6> <7,8>A B C D EF G H IA B C D EH F G I/5.测试记录及收获给出测试中遇到的问题及解决的方法和过程。