建立图的邻接矩阵或邻接表存储并在此基础知识上实现图的深度和广度优先遍历

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

三、调试和运行程序过程中产生的问题及采取的措施：（略）四、源程序及注释[ 源程序] 程序名：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++)<>。

题目：以实验3.1所示邻接矩阵为存储结构，编写程序，实现图的深度、宽度优先遍历。

部分代码：邻接矩阵的单一顶点DFS：//邻接矩阵的单一顶点DFSvoid DFS(int v,int visited[],mGraph g){int j;printf("%d ",v); //访问顶点vvisited[v] = 1; //为顶点v打上访问标记for(j = 0;j < g.n; j++){ //遍历v的邻接点if(!visited[j] && g.a[v][j] > 0){ //当未被访问且有权值DFS(j,visited,g);}}}邻接矩阵的全图DFS：//邻接矩阵的全图DFSvoid DFSGraph(mGraph g){int i;int *visited = (int*)malloc(g.n * sizeof(int)); //动态生成标记数组vistedfor(i = 0;i < g.n;i ++){visited[i] = 0; //visted数组初始化} //visted数组初始化for(i = 0;i < g.n;i ++){ //逐一检查每个顶点,若未被访问,则调用DFS if(!visited[i]){ //当未被访问且有权值DFS(i,visited,g);}}free(visited); //释放visted数组}邻接矩阵的单一顶点BFS：//邻接矩阵的单一顶点BFSvoid BFS(int v,int visited[],mGraph g){Queue q;Create(&q,g.n); //初始化队列visited[v] = 1; //为顶点v打上访问标记printf("%d ",v); //访问顶点vEnQueue(&q,v); //将顶点v放入队列while(!IsEmpty(&q)){Front(&q,&v);DeQueue(&q); //队首顶点出队列for(int i = 0;i < g.n;i ++){ //遍历v的每一项if(!visited[i] && g.a[v][i] > 0){ //若未被访问且有权值,则将其访问并放入队列,注意这里判断的是g.a[v][i]二维数组visited[i] = 1;printf("%d ",i);EnQueue(&q,i);}}}}邻接矩阵的全图BFS：//邻接矩阵的全图BFSvoid BFSGraph(mGraph g){int i;int *visited = (int*)malloc(g.n * sizeof(int)); //动态生成visited数组for(i = 0;i < g.n;i ++){ //初始化visited数组visited[i] = 0;}for(i = 0 ;i < g.n;i ++){ //逐一检查每个顶点,若未被访问,则调用BFSif(!visited[i]){BFS(i,visited,g);}}free(visited);}完整程序：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<windows.h>#include<queue>#define ERROR 0#define OK 1#define Overflow 2 //表示上溢#define Underflow 3 //表示下溢#define NotPresent 4 //表示元素不存在#define Duplicate 5 //表示有重复元素typedef int ElemType;typedef int Status;//邻接矩阵的结构体定义typedef struct{ElemType **a; //邻接矩阵int n; //图的当前顶点数int e; //图的当前边数ElemType noEdge; //两顶点间无边时的值}mGraph;//循环队列的结构体定义typedef struct{int front;int rear;int maxSize; //最大容量ElemType *element;}Queue;//创建一个能容纳mSize个单元的空队列void Create(Queue *Q,int mSize){Q->maxSize=mSize;Q->element=(ElemType*)malloc(sizeof(ElemType)*mSize);Q->front=Q->rear=0;}//判断队列是否为空,若是,则返回TRUE;否则返回FALSEBOOL IsEmpty(Queue *Q){return Q->front==Q->rear;}//判断队列是否已满,若是,则返回TRUE,否则返回FALSEBOOL IsFULL(Queue *Q){return (Q->rear+1)%Q->maxSize==Q->front;}//获取队头元素,并通过x返回.若操作成功,则返回TRUE,否则返回FALSE BOOL Front(Queue *Q,ElemType *x){if(IsEmpty(Q)) //空队列处理return FALSE;*x=Q->element[(Q->front+1)%Q->maxSize];return TRUE;}//入队.在队列Q的队尾插入元素x(入队操作)。

实现图的邻接矩阵和邻接表存储1．需求分析对于下图所示的有向图G，编写一个程序完成如下功能：1．建立G的邻接矩阵并输出之2．由G的邻接矩阵产生邻接表并输出之3．再由2的邻接表产生对应的邻接矩阵并输出之2．系统设计1．图的抽象数据类型定义：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：CreatGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图GDestroyGraph(&G)初始条件：图G存在操作结果：销毁图GInsertVex(&G,v)初始条件：图G存在，v和图中顶点有相同特征操作结果：在图G中增添新顶点v……InsertArc(&G,v,w)初始条件：图G存在，v和w是G中两个顶点操作结果：在G中增添弧<v,w>，若G是无向的则还增添对称弧<w,v>……DFSTraverse(G,Visit())初始条件：图G存在，Visit是顶点的应用函数操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。

一旦Visit()失败，则操作失败BFSTraverse(G,Visit())初始条件：图G存在，Visit是顶点的应用函数操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。

一旦Visit()失败，则操作失败}ADT Graph2．主程序的流程：调用CreateMG函数创建邻接矩阵M；调用PrintMatrix函数输出邻接矩阵M调用CreateMGtoDN函数，由邻接矩阵M创建邻接表G调用PrintDN函数输出邻接表G调用CreateDNtoMG函数，由邻接表M创建邻接矩阵N调用PrintMatrix函数输出邻接矩阵N3．函数关系调用图：3．调试分析（1）在MGraph的定义中有枚举类型typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网}赋值语句G.kind(int)=M.kind(GraphKind);是正确的，而反过来M.kind=G.kind则是错误的，要加上那个强制转换M.kind=GraphKind(G.kind);枚举类型enum{DG,DN,UDG,UDN}会自动赋值DG=0；DN=1，UDG=2，UDN=3；可以自动从GraphKind类型转换到int型，但不会自动从int型转换到GraphKind类型（2）算法的时间复杂度分析：CreateMG、CreateMGtoDN、CreateDNtoMG、PrintMatrix、PrintDN的时间复杂度均为O(n2) n为图的顶点数，所以main：T(n)= O(n2)4．测试结果用需求分析中的测试数据输入：输出：5、用户手册（1）输入顶点数和弧数；（2）输入顶点内容；（3）按行序输入邻接矩阵，输入各弧相应权值（4）回车输出邻接矩阵M、邻接表G和邻接矩阵N6、附录源程序：#include <stdio.h>#include <stdlib.h>#define MAX_VERTEX_NUM 20typedef int VRType;typedef int InfoType;typedef int VertexType;typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网} typedef struct ArcCell{VRType adj;//VRType是顶点关系类型，对无权图用1或0表示是否相邻；//对带权图则为权值类型InfoType *info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{VertexType vexs[MAX_VERTEX_NUM];//顶点向量AdjMatrix arcs;//邻接矩阵int vexnum,arcnum;//图的当前顶点数和弧数GraphKind kind;//图的种类标志}MGraph;void CreateMG(MGraph &M){int i,j;M.kind=DN;printf("输入顶点数:");scanf("%d",&M.vexnum);printf("输入弧数:");scanf("%d",&M.arcnum);printf("输入顶点:\n");for(i=0;i<M.vexnum;i++)scanf("%d",&M.vexs[i]);printf("建立邻接矩阵:\n");for(i=0;i<M.vexnum;i++)for(j=0;j<M.vexnum;j++)scanf("%d",&M.arcs[i][j].adj);printf("输入相应权值:\n");for(i=0;i<M.vexnum;i++)for(j=0;j<M.vexnum;j++)if(M.arcs[i][j].adj){scanf("%d",&M.arcs[i][j].info);}}typedef struct ArcNode{int adjvex;//该弧所指向的顶点在数组中的下标struct ArcNode *nextarc;InfoType *info;//该弧相关信息的指针}ArcNode;typedef struct VNode{VertexType data;//顶点信息ArcNode *firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;int vexnum,arcnum;//图的当前顶点数和弧数int kind;//图的种类标志}ALGraph;void PrintDN(ALGraph G){int i;ArcNode *p;printf("顶点:\n");for(i=0;i<G.vexnum;++i)printf("%2d",G.vertices[i].data);printf("\n弧:\n");for(i=0;i<G.vexnum;++i){p=G.vertices[i].firstarc;while(p){printf("%d→%d(%d)\t",i,p->adjvex,p->info);p=p->nextarc;}printf("\n");}//for}void CreateMGtoDN(ALGraph &G,MGraph M){//采用邻接表存储表示,构造有向图G(G.kind=DN)int i,j;ArcNode *p;G.kind=M.kind;G.vexnum=M.vexnum;G.arcnum=M.arcnum;for(i=0;i<G.vexnum;++i){//构造表头向量G.vertices[i].data=M.vexs[i];G.vertices[i].firstarc=NULL;//初始化指针}for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)if(M.arcs[i][j].adj==1){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.vertices[i].firstarc;p->info=M.arcs[i][j].info;G.vertices[i].firstarc=p;}}void CreateDNtoMG(MGraph &M,ALGraph G){int i,j;ArcNode *p;M.kind=GraphKind(G.kind);M.vexnum=G.vexnum;M.arcnum=G.arcnum;for(i=0;i<M.vexnum;++i)M.vexs[i]=G.vertices[i].data;for(i=0;i<M.vexnum;++i){p=G.vertices[i].firstarc;while(p){M.arcs[i][p->adjvex].adj=1;p=p->nextarc;}//whilefor(j=0;j<M.vexnum;++j)if(M.arcs[i][j].adj!=1)M.arcs[i][j].adj=0;}//for}void PrintMatrix(MGraph M){ int i,j;for(i=0;i<M.vexnum;++i){for(j=0;j<M.vexnum;++j) printf("%2d",M.arcs[i][j].adj); printf("\n");}}void main(){MGraph M,N;ALGraph G; CreateMG(M);PrintMatrix(M); CreateMGtoDN(G,M); PrintDN(G); CreateDNtoMG(N,G); PrintMatrix(N);}。

实验四图的深度优先与广度优先遍历实验时间：2011年5月12日，12:50 -15:50（地点：7-215）实验目的：理解图的逻辑特点；掌握理解图的两种主要存储结构（邻接矩阵和邻接表），掌握图的构造、深度优先遍历、广度优先遍历算法。

具体实验题目：（任课教师根据实验大纲自己指定）每位同学按下述要求实现相应算法：根据从键盘输入的数据创建图（图的存储结构可采用邻接矩阵或邻接表），并对图进行深度优先搜索和广度优先搜索1）问题描述：在主程序中提供下列菜单：1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束2）实验要求：图的存储可采用邻接表或邻接矩阵；定义下列过程：CreateGraph(): 按从键盘的数据建立图DFSGrahp()：深度优先遍历图BFSGrahp()：广度优先遍历图算法设计思路简介：图的深度优先搜索是个回溯过程，采用递归遍历，用数组visit来记录邻接点是否被访问过，遍历算法是通过DFSTraverse函数对所有点循环，防止图是非连通的（或非强连通）；图的广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，故可用队列来储存顶点。

算法描述：S1：自定义图的类型AG,AN,DG,DN，以及邻接表的存储结构类型ArcNode；S2：创建图graph，其中包含头节点数组vertex[],邻接点个数vexnum,边（弧）的个数arcnum,以及图的类型kind;S3:为图的广度优先搜索建立队列，并对队列进行必要的操作（入队，出队，队空，队满）；S4：创建图函数CreateGraph(Graph &G,int n,int e,string kind),建立需要的图或者网络，期中创建过程中是利用头结点插入法；S5：visit(Graph G,int u)函数用来访问图的邻接点，输出节点信息；S6：FirstAdjVex(Graph G,int v)函数用来返回头节点的第一个边节点，NextAdjV ex(Graph G,int v,int w)用来返回头节点的v节点后的节点；S7：深度优先搜索函数DFSGraph(Graph G,int v)递归搜索图，在函数DFSTraverse(Graph G)中循环调用深度优先搜索函数，实现图的深度优先搜索函数；S8：BFSGraph(Graph G)广度优先搜索图，搜索过程中将未被访问的点一次入队，在节点出队过程中将与该节点的邻接点依次入队；S9：在主函数中调用以上函数创建图，深度、广度优先搜索图，记录结果；源代码：#include<iostream>#include<cstdlib>#include<string>using namespace std;#define MAX_VERTEX_NUM 20#define MaxSize 100enum GraphKind {AG,AN,DG,DN};bool visited[MAX_VERTEX_NUM];struct ArcNode{ int adjvex;int weight;ArcNode* nextarc;};struct VNode{ int data;ArcNode* firstarc;};struct Graph{ VNode vertex[MAX_VERTEX_NUM];int vexnum,arcnum;GraphKind kind;};struct SeqQueue{int *base;int front,rear;};SeqQueue InitQueue(){SeqQueue Q;Q.base = new int;if(!Q.base){cout<<"内存申请失败，退出程序！"<<endl;exit(0);}Q.front=Q.rear=0;return Q;}int QueueEmpty(SeqQueue Q){return (Q.front==Q.rear)?1:0;}int QueueFull(SeqQueue Q){return (Q.front==(Q.rear+1)%MaxSize)?1:0;}void EnQueue(SeqQueue &Q,int x){if(QueueFull(Q)){cout<<"队满，入队操作失败！"<<endl;exit(0);}*(Q.base+Q.rear) = x;Q.rear = (Q.rear+1)%MaxSize;}void DeQueue(SeqQueue &Q,int &u){if(QueueEmpty(Q)){cout<<"队空，出队操作失败！"<<endl; exit(0);}u = *(Q.base+Q.front);Q.front = (Q.front+1)%MaxSize;}void CreateGraph(Graph &G,int n,int e,string kind){ int t;int i ,j;int weight;G.vexnum = n;G.arcnum = e;ArcNode* s;for(t=0;t<n;t++){ G.vertex[t].data = t+1;G.vertex[t].firstarc = NULL;}if(kind == "DG"){for(t=0;t<e;t++){//采用头入插入法cin>>i>>j;s= new ArcNode;s->adjvex = j;s->nextarc = G.vertex[i].firstarc;G.vertex[i].firstarc = s;}G.kind = DG;}if(kind == "AG"){for(t=0;t<e;t++){ cin>>i>>j;s= new ArcNode;s->adjvex = j;s->nextarc = G.vertex[i].firstarc;G.vertex[i].firstarc = s;s->adjvex = i;s->nextarc = G.vertex[j].firstarc;G.vertex[j].firstarc = s;}G.kind = AG;}if(kind == "DN"){for(t=0;t<e;t++){ cin>>i>>j>>weight;s= new ArcNode;s->adjvex = j;s->weight = weight;s->nextarc = G.vertex[i].firstarc;G.vertex[i].firstarc = s;}G.kind = DN;}if(kind == "AN"){for(t=0;t<e;t++){ cin>>i>>j>>weight;s= new ArcNode;s->adjvex = j;s->weight = weight;s->nextarc = G.vertex[i].firstarc;G.vertex[i].firstarc = s;s->adjvex = i;s->weight = weight;s->nextarc = G.vertex[j].firstarc;G.vertex[j].firstarc = s;}G.kind = AN;}}int FirstAdjVex(Graph G,int v){if(G.vertex[v].firstarc)return G.vertex[v].firstarc->adjvex;else return -1;}int NextAdjVex(Graph G,int v,int w){ArcNode* p = G.vertex[v].firstarc;while(p->adjvex!=w)p = p->nextarc;if(p->nextarc)return p->nextarc->adjvex;else return -1;}void visit(Graph G,int u){if(G.kind==AG || G.kind==DG)cout<<G.vertex[u].data<<" ";else if(G.kind==AN || G.kind==DN)if(G.vertex[u].firstarc)cout<<G.vertex[u].data<<" "<<G.vertex[u].firstarc->weight<<" ";else cout<<G.vertex[u].data<<" ";}void DFSGraph(Graph G,int v){visited[v] = true;visit(G,v);for(int w=FirstAdjVex(G,v); w!=-1;w=NextAdjVex(G,v,w))if(!visited[w])DFSGraph(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])DFSGraph(G,v);}void BFSGraph(Graph G){SeqQueue Q;Q = InitQueue();int v,u;for(v=0;v<G.vexnum;v++)visited[v] = false;for(v=0;v<G.vexnum;v++)if(!visited[v]){EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u);if(!visited[u]){visited[u]=true;visit(G,u);for(int w=FirstAdjVex(G,u);w!=-1;w=NextAdjVex(G,u,w))if(!visited[w])EnQueue(Q,w);}}}}int main(){Graph G;int v,e;string kind;cout<<"请输入图的顶点个数、边数以及类型:"<<endl;cin>>v>>e>>kind;cout<<"请输入创建图:"<<endl;CreateGraph(G,v,e,kind);cout<<"深度优先搜索图的结果为:"<<endl;DFSTraverse(G);cout<<endl<<"广度优先搜索图的结果为:"<<endl;BFSGraph(G);cout<<endl;return 0;}运行结果：。

#include ""#include ""#include ""#include ""typedef enum {FALSE, TRUE} BOOLEAN;#define OVERFLOW -1#define OK 1#define ERROR 0#define INFINITY INT_MAX /* 最大值∞ *//* 根据图的权值类型，分别定义为最大整数或实数 */ #define MAX_VERTEX_NUM 20 /* 最大顶点数目 */ typedef enum {DG, DN, UDG,UDN} GraphKind ;/* {有向图，有向网，无向图，无向网} */BOOLEAN Visited[MAX_VERTEX_NUM];BOOLEAN visited[MAX_VERTEX_NUM];#define VEX_NUM 20#define MAXSIZE 50typedef char Vextype;typedef int ElemType;typedef int Status;irstedge) return -1;else return[v].firstedge->adjvex);}int NextAdjVex(ALGraph G,int v,int w){irstedge;if(!p) return -1;while(p->adjvex!=w) p=p->nextarc; ertex=vi;G->adjlist[i].firstedge=NULL;}printf("顶点:");for (i=0;i<G->n;i++)printf("%c(%d)-",G->adjlist[i].vertex,i+1);printf("\n请输入边的信息(vi,vj)\n例如:1,2:\n");for (k=0;k<G->e;k++) { /*建立边表*/scanf("%d,%d",&i,&j); irstedge;G->adjlist[i-1].firstedge=s;s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=i-1;s->nextarc=G->adjlist[j-1].firstedge;G->adjlist[j-1].firstedge=s;}.}/*CreateALGraph*/void DFS(ALGraph *G, int v) {EdgeNode *p ;Visited[v]=TRUE ;printf("%c->",G->adjlist[v].vertex); /* 置访问标志，访问顶点v */p=G->adjlist[v].firstedge; /* 链表的第一个结点 */while (p!=NULL){if(!Visited[p->adjvex])DFS(G, p->adjvex);/* 从v的未访问过的邻接顶点出发深度优先搜索 */p=p->nextarc ;}}void DFS_traverse (ALGraph *G){int v ;EdgeNode *p ;printf("深度度优先搜索输出结点信息:");for (v=0; v<G->n; v++) Visited[v]=FALSE ; /* 访问标志初始化 */ p=G->adjlist[v].firstedge ;for (v=0; v<G->n; v++)if (!Visited[v]) DFS(G,v);}ertex);return OK;}void BFSTraverse(ALGraph G, Status (*Visit)(int v,ALGraph G)){// 连通图 G 广度优先搜索LinkQueue Q;ElemType u;// EdgeNode *p;int v;int w;printf("广度优先搜索输出结点信息:");for(v=0;v<;++v) visited[v]=FALSE;// 初始化访问标志InitQueue(Q); //置空的辅助队列for(v=0;v<;++v)if(!visited[v]){ //v 未访问visited[v]=TRUE;Visit(v,G);EnQueue(Q,v);//v 入队列while(!QueueEmpty(Q)){DeQueue(Q,&u); //队头元素出队并置为 u for(w=FirstAdjVex(G,u);w>=0; w=NextAdjVex(G,u,w)) if(!visited[w]){ //w为u尚未访问的邻接顶点 visited[w]=TRUE; Visit(w,G);EnQueue(Q,w);//访问的顶点 w入队列}//if}//while}//if}//BFSTraversevoid main(){//Mgraph Gm;//CreateMGraph(&Gm); //邻接矩阵存储ALGraph G2;//邻接表存储do{CreateALGraph(&G2);DFS_traverse(&G2);printf("\n==============\n");BFSTraverse(G2, Visit);printf("\n=====是否还继续 0-退出====\n");}while(getch()!='0');}。

数据结构课程实验报告课程名称数据结构班级计算123 实验日期2014年6月1日--3日姓名学号实验成绩实验名称实验四图的深度和广度优先遍历实验目的及要求【实验目的】熟练掌握图的邻接表存储结构及其图的建立方法和深度和广度优先遍历的方法。

【实验要求】1.图的存储可采用邻接矩阵或邻接表2.GraphCreate(): 按从键盘的数据建立图3.GraphDFS()：深度优先遍历图4.GraphBFS()：广度优先遍历图5.编写完整程序完成下面的实验内容并上机运行6.整理并上交实验报告实验环境硬件平台：普通的PC机软件平台：Windows 7 操作系统编程环境：VisualC++ 6.0实验内容1.以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。

算法描述及实验步骤算法：1)定义图的邻接表存储结构2）实现图的邻接表存储，即建立图的存储结构3）实现图的深度优先遍历4）定义队列的顺序存储结构，并实现队列的基本操作如初始化队列、入队、出对、判断队列是否为空等。

利用队列实现图的广度优先遍历。

伪代码：1）定义邻接矩阵和队列的存取结构；2）创建图L：1.置空图L->num=0；2.输入顶点数目num；3.i++,输入结点L->vexs[i]直到L->num;3）输出图L的各顶点；4）深度优先遍历图g中能访问的各个顶点1.输入起点的下标qidian；2.标志数组初始化mark[v]=0;3.for(v=qidian;v<g.num+qidian;v++) //{v1=v%g.num;if(mark[v1]==0)DFS(g,v1,mark); //从第v1个点出发深度优先遍历图g中能访问的各个顶点（算法描述里的流程图很详细）}5）广度优先周游图g中能访问的各个顶点。

1.构造空队列；2.入队a[0]；3.a[0]出队，a[0]的邻接点入队，遍历a[0]；4.队首出队，重复3直到队列为空；5.判断是否全遍历完了；6.输出广度优先遍历序列流程图：开始访问V 0,置标志求V 0邻接点有邻接点w求下一邻接点w V 0W 访问过结束NYN YDFS开始标志数组初始化V i =1Vi 访问过DFSV i =V i +1V i ==Vexnums结束NNYY调试过程及实验结果总结本次试验采用的是邻接表的方式实现图的深度优先遍历和广度优先遍历。

实验报告课程名称：数据结构与算法课程类型：必修实验项目：图型结构及应用实验题目：图的存储结构的建立与搜索一、实验目的1.了解图的两种存储方式：邻接矩阵和邻接表。

2.掌握邻接矩阵和邻接表的建立算法。

3.掌握图的深度优先搜索和广度优先搜索算法。

4.更加熟练文件的相关操作。

二、实验要求及实验环境实验要求：1．分别实现图的邻接矩阵、邻接表存储结构的建立算法，分析和比较各建立算法的时间复杂度以及存储结构的空间占用情况；2．实现图的邻接矩阵、邻接表两种存储结构的相互转换算法；3．在上述两种存储结构上，分别实现图的深度优先搜索（递归和非递归)和广度优先搜索算法。

并以适当的方式存储和显示相应的搜索结果（深度优先或广度优先生成森林（或生成树）、深度优先或广度优先序列和编号）；4．分析搜索算法的时间复杂度；5．以文件形式输入图的顶点和边，并显示相应的结果。

要求顶点不少于10个，边不少于13个；6．软件功能结构安排合理，界面友好，便于使用。

实验环境：codeblocks/Dev-C++三、设计思想（本程序中的用到的所有数据抽象数据性ADT的定义，主程序的流程图及各程序模块之间的调用关系）1. 所用的抽象数据性ADT的定义1）逻辑结构：栈：是一种特殊形式的线性表，所有的插入和删除操作都在栈顶。

栈的置空操作：void makenull(stack* s)判断栈是否为空：int empty(stack* s)返回栈顶元素：btree* top(stack* s)入栈操作：void push(btree* x, stack* s)出栈操作：void pop(stack* s)队列：是一种特殊形式的线性表，队尾入队，队首出队。

将队列置空：void makenull_q(queue* duilie)在队列后面插入T：void enqueue_q(btree* T, queue* duilie)判断队列是否为空：int empty_q(queue* duilie)返回队列的第一个元素：btree* front_q(queue* duilie)删除队列的第一个元素:void dequeue_q(queue* duilie)2) 存储结构：定义了一个邻接矩阵结构体mtgraph，一个边表节点结构体edgenode，一个顶点表结点结构体vertexnode，一个邻接表结构体adjgraph，一个栈结构体stack，一个队列节点结构体node2，一个队列结构体queue，邻接表先深递归访问标记数组visited_1[20]，邻接表先深递归顶点的先深标号数组dfn_1[20]，邻接矩阵先深递归访问标记数组visited_2[20]，邻接矩阵先深递归顶点的先深标号数组dfn_2[20]，邻接表先深非递归访问标记数组visited_5[20]，邻接表先深非递归顶点的先深标号数组dfn_5[20]，邻接矩阵先深非递归访问标记数组visited_6[20]，邻接矩阵先深非递归顶点的先深标号数组dfn_6[20]，邻接表先广访问标记数组visited_3[20]，邻接表先广顶点的先深标号数组dfn_3[20]，邻接矩阵先广访问标记数组visited_4[20]，邻接矩阵先广顶点的先深标号数组dfn_4[20]。

邻接矩阵和邻接表是图论中用于表示图结构的两种常见方式，而深度遍历和广度遍历则是图论中常用的两种图遍历算法。

本文将从简介、原理和应用三个方面探讨这四个主题。

一、邻接矩阵和邻接表1.邻接矩阵邻接矩阵是一种使用二维数组来表示图中顶点之间关系的方法。

如果图中有n个顶点，那么对应的邻接矩阵就是一个n*n的矩阵，其中元素a[i][j]表示顶点i和顶点j之间是否有边，通常用0和1表示。

邻接矩阵适用于稠密图，其存储结构简单，可以直观地展示图的结构，但对于稀疏图来说可能会造成存储空间的浪费。

2.邻接表邻接表是一种使用链表来表示图中顶点之间关系的方法。

对于图中的每一个顶点，都维护一个相邻顶点的列表，图中所有顶点的列表再组合成一个链表，用于表示整个图的结构。

邻接表适用于稀疏图，其存储结构灵活，可以有效地节省存储空间，但查找任意两个顶点之间的关系可能会比较耗时。

二、深度遍历和广度遍历原理1.深度遍历深度遍历是一种用于遍历或搜索图中节点的算法，其原理是从图的某一顶点出发，沿着一条路径不断向下遍历直到末端，然后回溯到上一个节点继续遍历。

深度遍历使用栈来实现，可以通过递归或迭代来进行。

2.广度遍历广度遍历是一种用于遍历或搜索图中节点的算法，其原理是从图的某一顶点出发，依次访问其所有相邻节点，然后再依次访问这些相邻节点的相邻节点，以此类推。

广度遍历使用队列来实现。

三、深度遍历和广度遍历的应用1.深度遍历的应用深度遍历常用于求解图的连通分量、拓扑排序、解决迷宫问题等。

在连通分量中，深度遍历可以帮助我们找到图中的所有连通分量，并对其进行标记，用于进一步的算法运算。

在拓扑排序中，深度遍历可以帮助我们找到一个合理的顺序，用以处理依赖关系问题。

在解决迷宫问题时，深度遍历可以帮助我们找到一条从起点到终点的路径。

2.广度遍历的应用广度遍历常用于求解最短路径、解决迷宫问题等。

在求解最短路径中，广度遍历可以帮助我们找到起点到终点的最短路径，从而解决了许多实际问题。