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

}
// 给邻接矩阵赋值 // 输出邻接矩阵的函数
5
// 给大的邻接表中所有头结点的指针域副初值
G->adjlist[i].firstarc=NULL;
for(i=0;i<n;i++)
// 检查邻接矩阵的每个元素
for(j=0;j<n;j++)
if(g.edges[i][j]!=0)
{
p=(ArcNode *)malloc(sizeof(ArcNode));
printf("\n");
}
}
void MatToList(MGraph g,ALGraph *&G)
// 将邻接矩阵 g 转换为邻接表 G
{
int i,j;
int n=g.n;
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for(i=0;i<n;i++)
{
ArcNode *p;
int queue[max],front=0,rear=0;
// 定义循环队列并初始化
int visited[max];
int w,i;
for(i=0;i<G->n;i++)
visited[i]=0;
printf(" %d ",v); visited[v]=1;
// 把输入的第 v 个作为第一个广度遍历的节点，一直这样进行下去
图的深度优先与广度优先遍历
实验题目：
从键盘输入的数据创建图（图的存储结构可采用邻接矩阵或邻接表）
，并对图进行深度优先搜索和广度优先

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

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

A[i,j]={ 0，反之
图 5-2 中有向图 G1 的邻接矩阵为 M1 M1=┌ 0 1 0 1 ┐
│1010│ │1001│ └0000┘
用邻接矩阵表示法来表示一个具有 n 个顶点的图时，除了用邻接矩阵中的 n*n 个元素存储顶点间相邻关系外，往往还需要另设一个向量存储 n 个顶点的 信息。因此其类型定义如下： VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量
易求得各个顶点的度。
对于有向图，顶点 Vi 的出度 OD(Vi)为邻接矩阵第 i 行元素之和，顶点 Vi 的入度 ID(Vi)为第 i 列元素之和。即 n n OD(Vi)＝∑A[i,j]， OD(Vi)＝∑A[j,i]） j=1 j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若<Vi,Vj>或(Vi,Vj) A[i,j]＝{ ∞ , 否则。 其中 Wij 为<Vi,Vj>或(Vi,Vj)上的权值。相应地，网的邻接矩阵表示的类型 定义应作如下的修改： adj:weightype ; {weightype 为权类型}
2、图的遍历： *深度优先搜索
深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初 始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点 V 出 发，访问此顶点，然后依次从 V 的未被访问的邻接点出发深度优先遍历图，直 至图中所有和 V 有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问， 则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访 问到为止。
以图中无向图 G4 为例，深度优先遍历图的过程如图所示。假设从顶点 V1 出 发进行搜索，在访问了顶点 V1 后，选择邻接点 V2。因为 V2 未曾访问，则从 V2 出发进行搜索。依次类推，接着从 V4,V8,V5 出发进行搜索。在访问了 V5 之后， 由于 V5 的邻接点已都被访问，则搜索回到 V8。由于同样的理由，搜索继续回到 V4，V2 直至 V1，此时由于 V1 的另一个邻接点为被访问，则搜索又从 V1 到 V3，再

实验四图的深度优先与广度优先遍历实验时间：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.广度遍历的应用广度遍历常用于求解最短路径、解决迷宫问题等。

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

东华理工大学长江学院信息工程系数据结构课题设计专业：计算机科学与技术姓名：赵进城学号：20173031308 日期：2018/05/24采用邻接矩阵表示法创建图，并进行深度优先搜索遍历1、代码运行截图2、附源代码：// data.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <iostream>using namespace std;#define MVNum 100//最大顶点数typedef char VerTexType;//假设顶点的数据类型为字符型typedef int ArcType; //假设边的权值类型为整型//------------图的邻接矩阵------------------typedef struct{VerTexType vexs[MVNum]; //顶点表ArcType arcs[MVNum][MVNum]; //邻接矩阵int vexnum,arcnum; //图的当前点数和边数}Graph;bool visited[MVNum]; //访问标志数组，其初值为"false"int FirstAdjVex(Graph G , int v);//返回v的第一个邻接点int NextAdjVex(Graph G , int v , int w);//返回v相对于w的下一个邻接点int LocateVex(Graph G , VerTexType v){//确定点v在G中的位置for(int i = 0; i <G.vexnum; ++i)if(G.vexs[i] == v)return i;return -1;}//LocateVexvoid CreateUDN(Graph&G){//采用邻接矩阵表示法，创建无向网Gint i , j , k;cout<<"请输入总顶点数，总边数，以空格隔开:";cin>>G.vexnum>>G.arcnum;//输入总顶点数，总边数cout<<endl;cout<< "输入点的名称，如a" <<endl;for(i = 0; i <G.vexnum; ++i){cout<< "请输入第" << (i+1) << "个点的名称:";cin>>G.vexs[i]; //依次输入点的信息}cout<<endl;for(i = 0; i <G.vexnum; ++i) //初始化邻接矩阵，边的权值均置为极大值MaxIntfor(j = 0; j <G.vexnum; ++j)G.arcs[i][j] = 0;cout<< "输入边依附的顶点，如a b" <<endl;for(k = 0; k <G.arcnum;++k){//构造邻接矩阵VerTexType v1 , v2;cout<< "请输入第" << (k + 1) << "条边依附的顶点:";cin>> v1 >> v2;//输入一条边依附的顶点及权值i = LocateVex(G, v1); j = LocateVex(G, v2);//确定v1和v2在G中数组的下标G.arcs[j][i] = G.arcs[i][j] = 1;//置<v1, v2>的对称边<v2, v1>的权值为w}//for}//CreateUDNvoid DFS(Graph G, int v){//图G为邻接矩阵类型int w;cout<<G.vexs[v]<<" ";visited[v]=true;for (w=0;w<G.vexnum;w++)if((G.arcs[v][w]!=0)&&(!visited[w]))DFS(G,w);}//DFSint FirstAdjVex(Graph G , int v){//返回v的第一个邻接点int i;for(i = 0 ; i <G.vexnum ; ++i){if(G.arcs[v][i] == 1 && visited[i] == false) return i;}return -1;}//FirstAdjVexint NextAdjVex(Graph G , int v , int w){//返回v相对于w的下一个邻接点int i;for(i = w ; i <G.vexnum ; ++i){if(G.arcs[v][i] == 1 && visited[i] == false)return i;}return -1;}//NextAdjVexint main(){cout<< "******采用邻接矩阵表示图的深度优先搜索遍历********" <<endl<<endl;Graph G;CreateUDN(G);cout<<endl;cout<< "无向图G创建完成！" <<endl<<endl;cout<< "请输入遍历无向图G的起始点："; VerTexType c;cin>> c;int i;for(i = 0 ; i <G.vexnum ; ++i){if(c == G.vexs[i])break;}cout<<endl;while(i >= G.vexnum){cout<< "该点不存在，请重新输入！" <<endl;cout<< "请输入遍历连通图的起始点：";cin>> c;for(i = 0 ; i <G.vexnum ; ++i){if(c == G.vexs[i])break;}}cout<< "深度优先搜索遍历无向图G结果：" <<endl;DFS(G , i);cout<<endl;return 0;}//main。

遍历规则 从图中某结点v0出发，深度优先遍历（DFS: Depth First Search）图的规则为： 访问v0； 对v0的各个出点v01，v02，…，v0m，每次从它们中按一定方式（也可任选）选取一个未被访问过的结点，从该结点出发按深度优先遍历方式遍历。 然，因为我们没有规定对出点的遍历次序，所以，图的深度优先遍历结果一般不唯一。
20.2 深度优先遍历
例如，对图 20‑1给出的有向图与无向图，一些遍历结果（结点访问次序）为： 左图：从1出发：1，2，4，5；或1，5，2，4 从2出发：2，1，5，4；或2，4，1，5 右图：从a出发：a，b，c，d；或a，b，d，c; … …
A 如果不想让visited或top做为函数参数，也可以在函数中将其定义为static型量。但是，这样的程序是不可再入的，即函数再次被调用时，static型的量也不重新初始化，造成错误！
上面函数中的参数visited和top实质上是中间变量，只是为了避免在递归调用时重新初始化而放在参数表中，造成使用的不方便，为此，做个包装程序： long DFS1(int g[][CNST_NumNodes], long n, long v0, long *resu ) { char *visited; long top=0; visited = new char[n]; for (long i=0; i<n; i++) visited[i]=0; long num=DFS1( g, n, v0, visited, resu, top ); delete visited; return num; }
深度优先遍历非递归算法的一般性描述。
long DFS_NR(图g，结点v0)
单击此处可添加副标题

基于邻接矩阵存储的图的深度优先遍历和⼴度优先遍历图的存储结构相⽐较线性表与树来说就复杂很多，对于线性表来说，是⼀对⼀的关系，所以⽤数组或者链表均可简单存放。

树结构是⼀对多的关系，所以我们要将数组和链表的特性结合在⼀起才能更好的存放。

那么我们的图，是多对多的情况，另外图上的任何⼀个顶点都可以被看作是第⼀个顶点，任⼀顶点的邻接点之间也不存在次序关系。

仔细观察以下⼏张图，然后深刻领悟⼀下：因为任意两个顶点之间都可能存在联系，因此⽆法以数据元素在内存中的物理位置来表⽰元素之间的关系（内存物理位置是线性的，图的元素关系是平⾯的）。

如果⽤多重链表来描述倒是可以做到，但在⼏节课前的树章节我们已经讨论过，纯粹⽤多重链表导致的浪费是⽆法想像的（如果各个顶点的度数相差太⼤，就会造成巨⼤的浪费）。

邻接矩阵（⽆向图）考虑到图是由顶点和边或弧两部分组成，合在⼀起⽐较困难，那就很⾃然地考虑到分为两个结构来分别存储。

顶点因为不区分⼤⼩、主次，所以⽤⼀个⼀维数组来存储是狠不错的选择。

⽽边或弧由于是顶点与顶点之间的关系，⼀维数组肯定就搞不定了，那我们不妨考虑⽤⼀个⼆维数组来存储。

图的邻接矩阵(Adjacency Matrix)存储⽅式是⽤两个数组来表⽰图。

⼀个⼀维数组存储图中顶点信息，⼀个⼆维数组(称为邻接矩阵)存储图中的边或弧的信息。

我们可以设置两个数组，顶点数组为vertex[4]={V0,V1,V2,V3}，边数组arc[4][4]为对称矩阵(0表⽰不存在顶点间的边，1表⽰顶点间存在边)。

对称矩阵：所谓对称矩阵就是n阶矩阵的元满⾜a[i][j]=a[j][i](0<=i,j<=n)。

即从矩阵的左上⾓到右下⾓的主对⾓线为轴，右上⾓的元与左下⾓相对应的元全都是相等的。

有了这个⼆维数组组成的对称矩阵，我们就可以很容易地知道图中的信息：1. 要判定任意两顶点是否有边⽆边就⾮常容易了；2. 要知道某个顶点的度，其实就是这个顶点Vi在邻接矩阵中第i⾏(或第i列)的元素之和；3. 求顶点Vi的所有邻接点就是将矩阵中第i⾏元素扫描⼀遍，arc[i][j]为1就是邻接点咯。

邻接矩阵的深度优先遍历算法简介邻接矩阵是一种常见的图存储结构，它使用二维数组来表示图中各个顶点之间的关系。

而深度优先遍历算法是一种常用的图遍历算法，用于遍历和搜索图的各个顶点。

本文将介绍邻接矩阵的深度优先遍历算法，包括其基本思想、实现步骤以及应用场景等内容。

基本思想深度优先遍历算法（Depth-First Search，DFS）是一种针对图和树的遍历算法，它通过从起始顶点开始，逐个探索图中的顶点，并沿着某一条路径一直深入，直到无法继续为止，然后回溯到前一顶点继续探索其它路径，直到所有顶点都被访问过为止。

邻接矩阵是一种常见的图表示方法，它通过一个二维数组来表示图中各个顶点之间的关系。

邻接矩阵中的每个元素表示两个顶点之间是否存在一条边，具体而言，如果顶点i和顶点j之间存在一条边，则邻接矩阵中下标为(i, j)和(j, i)的元素值为1；否则，它们的元素值为0。

邻接矩阵的深度优先遍历算法是通过对邻接矩阵进行遍历，找出与起始顶点相连接的顶点，并依次对这些顶点进行深度优先遍历。

实现步骤邻接矩阵的深度优先遍历算法可以使用递归或迭代的方式来实现。

下面分别介绍这两种实现方法的具体步骤。

递归实现1.创建一个数组visited，用来记录每个顶点是否已被访问过，初始时所有元素都设为0。

2.选择一个起始顶点v，并将visited[v]设置为1，表示该顶点已被访问过。

3.遍历邻接矩阵中与v相连的所有顶点w，如果visited[w]为0，则递归调用深度优先遍历函数，将w作为新的起始顶点。

4.重复步骤3，直到所有顶点都被访问过为止。

迭代实现1.创建一个数组visited，用来记录每个顶点是否已被访问过，初始时所有元素都设为0。

2.创建一个栈，用来存储待访问的顶点。

3.选择一个起始顶点v，并将visited[v]设置为1，表示该顶点已被访问过。

4.将v入栈。

5.当栈不为空时，执行以下操作：–出栈一个顶点u，访问它。

–遍历邻接矩阵中与u相连的所有顶点w，如果visited[w]为0，则将w入栈，并将visited[w]设置为1。

第四次实验报告图的邻接表存储实现及深度优先遍历学号0708140119 电子072 姓名陆萍萍一、问题描述1、程序所能达到的基本功能构建以邻接表形式存储的表及实现深度优先遍历并输出结果。

2、输入的形式和输入值的范围：根据提示进行输入：先输入要构建的表的结点数和边数，要求是整型；输入各结点的代号，这里用char型，也可在源程序中改变其它形式；输入各边的头结点和尾结点的代号；3、输出的形式若正常输入，则输出深度优先遍历的最后结果。

用各结点的代码表示。

测试数据要求第一组数据：结点数和边数：4 4结点名称：a b c d边：a-b a-c b-c c-d 输出a-b-c-d-over!第二组数据：图如下：输出a-b-c-d-e-f-g-over! 4、概要设计1、抽象数据类型，它们的作用//图的结点类template<class T>class TVex{};//图类template<class T>class Graph{}//链表存储2主程序流程及模块调用关系(1)主程序模块：void main{构造一个图，对T实例化（char）。

调用Graph中的Create函数；调用Graph中的DFS函数；}（22、核心算法的粗线条伪码5、详细设计（要求主要变量和语句加注释）1、抽象数据类型的实现：包括类型定义和各个操作的实现。

1)TVex的详细设计（1）私有数据类型的定义private：T m_elem;TLinklist<int> m_arcs;2)Graph的详细设计（1）私有数据类型的定义private：TVex<T> Vextex[maxnum];int vexnum;int arcnum;int kind;int symbol[maxnum];（2）公有函数成员的定义Graph()；void Create();int LocateVex(T v);void DFS();void DFS_IN(int i);(3)具体实现★template<class T>void Graph<T>::Create(){T v1,v2;int i,j;cout<<"*********************基本信息*****************************"<<endl;cout<<"请分别输入结点数和边数: ";cin>>vexnum>>arcnum;cout<<"***********************结点***************************"<<endl;for(int l=0;l<vexnum;l++){cout<<"请输入第"<<l+1<<"个结点的代号 ";cin>>Vextex[l].m_elem;}cout<<"***********************边数***************************"<<endl;for(int k=0;k<arcnum;k++){cout<<"请输入第"<<k+1<<"边的头结点和尾结点 ";cin>>v1>>v2;i=LocateVex(v1);j=LocateVex(v2);Vextex[i].m_arcs.InsertLate(j);Vextex[j].m_arcs.InsertLate(i);}cout<<"************************结果**************************"<<endl; }★template<class T>int Graph<T>::LocateVex(T v){for(int i=0;i<vexnum&&Vextex[i].m_elem!=v;i++); if(i==vexnum)return -1;elsereturn i;}★template<class T>void Graph<T>::DFS(){DFS_IN(0);cout<<"over!"<<endl;}★template<class T>void Graph<T>::DFS_IN(int i){int index;symbol[i]=1;cout<<Vextex[i].m_elem<<"-->";for(int j=0;;j++){index=Vextex[i].m_arcs.GetElem(j+1);if(index!=-1){if(symbol[index]!=1)DFS_IN(index);}elsebreak;}}2、其他主要算法的实现将次要算法均设为Graph的公有函数成员3、主程序的实现Void main(){huffmanTree<char> h;int *ww,n;char *cc;cout<<"请输入叶子节点的个数：";cin>>n;ww=new int[n];cc=new char[n];cout<<"请依次输入节点名称和权重："<<endl;for(int i=1;i<=n;i++){cout<<"第"<<i<<"个"<<endl;cout<<" 名称：";cin>>cc[i-1];cout<<" 权重: ";cin>>ww[i-1];}h.CreatehuffmanTree(cc,ww,n);h.huffmanTreecoding();}四 .调试分析1、设计与调试过程中遇到的问题及分析、体会（1）这个实验较简单，经过对书本上已经给出的c版程序的分析，很容易就写出了对整个实验的大体思路。

基于邻接表：基于基于邻接矩阵：实验总结（结论或问题分析）：通过这次实验，我掌握了无向图的建立，一种基于邻接表，一种基于邻接矩阵，然后分别实现深度广度优先遍历。

广度优先遍历类似于数的层序遍历，它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域。

深度优先遍历是从图的某个顶点出发，访问这个顶点，然后从v的没访问过的邻接点出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到。

实验成绩任课教师签名附：源程序：参考：基于邻接表的深度广度遍历package graph;import java.util.*;public class ALgraph{static class Vertex<T> {private T date;private Edge frist;public T getDate() {return date;}public void setDate(T date) {this.date = date;}public Edge getFrist() {return frist;}public void setFrist(Edge frist) {this.frist = frist;}}static class Edge {private int vertexIndex;private Edge next;public int getVertexIndex() {return vertexIndex;}public void setVertexIndex(int vertexIndex) {this.vertexIndex = vertexIndex;}public Edge getNext() {//System.out.println(next);if(next==null){return null;}return next;}public void setNext(Edge next) {this.next = next;}}public static Vertex[] set(int x,int y){//参考输入数据 1 2 3 4 5//1 3 1 2 1 4 1 5 2 5 2 4Scanner sc=new Scanner(System.in);Vertex[]arr=new Vertex[x];Vertex<String> v=null;System.out.println("请依次输入顶点的信息空格分开");for(int i=0;i<x;i++){String str=sc.next();v=new Vertex<String>();v.setDate(str);v.setFrist(null);arr[i]=v;}System.out.println("请依次输入边的信息空格分开 (根据你输入的顶点信息来)");Edge e=null;int str1,str2;//System.out.println(y);for(int j=0;j<y;j++){str1=sc.nextInt();str2=sc.nextInt();//System.out.println("str1:"+str1+"str2:"+str2);e=new Edge();e.setVertexIndex(str2-1);if(arr[str1-1].getFrist()==null){arr[str1-1].setFrist(e);}else{Edge e2=arr[str1-1].getFrist();while(e2.getNext()!=null){e2=e2.getNext();}//System.out.println(e.getVertexIndex());e2.setNext(e);}}return arr;}public static void dfs(Vertex[] arr) {boolean[] b = new boolean[arr.length];System.out.println();for (int j = 0, len = arr.length; j < len; j++) { //如果这个顶点没有被访问过;if (!b[j]) {fun(arr, j, b);}}System.out.println();}private static void fun(Vertex[] arr,int i,boolean[] b){ b[i]=true;//System.out.println(i);System.out.print(arr[i].getDate()+"\t");Edge e=arr[i].getFrist();while(e!=null){//对i的第一条边的顶点进行访问if(!b[e.getVertexIndex()]){fun(arr, e.getVertexIndex(), b);}e=arr[e.getVertexIndex()].getFrist();// if(b[e.getVertexIndex()]){// break;// }}e=arr[i].getFrist();if(e!=null&&e.getNext()!=null){ //对i坐标的顶点剩下的顶点进行访问e=e.getNext();}//1 2 1 3 2 4 3 5 5 4 4 6 6 7 7 5while(e!=null){if(!b[e.getVertexIndex()]){fun(arr, e.getVertexIndex(), b);}e=e.getNext();if(e==null||b[e.getVertexIndex()]){break;}}return;}public static void bfs(Vertex[] arr) {Queue<Vertex<String>> q = new LinkedList<Vertex<String>>();boolean[] b = new boolean[arr.length];for (int i = 0, len = arr.length; i < len; i++) {//如果该顶点没被访问过if (!b[i]) {System.out.print(arr[i].getDate()+"\t");b[i] = true;//将该顶点入队列q.add(arr[i]);//如果队列不是空while (!q.isEmpty()) {//v等于出队的顶点Vertex<String>v= q.poll();//e等于v的第一条连接的边Edge e = v.getFrist();//如果e不是空while (e != null) {//如果e所连接的顶点没被访问过if(!b[e.getVertexIndex()]){//该顶点入队q.add(arr[e.getVertexIndex()]);//输出该顶点的值System.out.print(arr[e.getVertexIndex()].getDate()+"\t");b[e.getVertexIndex()]=true;}//寻找改顶点的下一条边e=e.getNext();}}}}System.out.println();}public static void main(String[] args) {Vertex<Integer>[]arr=set(6, 6);System.out.println();System.out.println("深度优先遍历");dfs(arr);System.out.println("宽度优先遍历");bfs(arr);}}基于邻接矩阵：package graph;import java.util.*;public class Matrixgraph {private int[][] edges;private int num;//图的结点数量private boolean[] visited ;//结点是否被访问过private Vertex[] vertex ;private int pre;//用来记录前一个public void createGraph(){Scanner in = new Scanner(System.in);System.out.print("please input the info:");String str = in.next();String[] temp = str.split(",");System.out.print(temp.length);this.num = temp.length;System.out.print(num);visited = new boolean[num];vertex = new Vertex[num];for(int i=0;i<num;i++){Vertex v = new Vertex(i,temp[i]);vertex[i]=v;visit(vertex[i]);System.out.println();}edges = new int[num][num];for(int i=0;i<num;i++){for(int j=0;j<num;j++){Scanner in1 = new Scanner(System.in);System.out.print("input the value:");int k = in1.nextInt();/* System.out.print(k);*/edges[i][j] =k;}}}public void visit(Vertex v){if(v!=null){System.out.print( v.no+" "+);System.out.println();}}public void dFS(int i){visit(vertex[i]);visited[i]=true;for(int j=i+1;j<num;j++){if(!visited[j]&&edges[i][j]!=0){dFS(j);} } }public void dFSTrave(){//深度遍历是在邻接矩阵的基础上进行的for(int i=0;i<num;i++){visited[i]=false;//默认情况下所有顶点是没有被访问过的}for(int i=0;i<num;i++){if(!visited[i]){//还需要考虑一个条件就是必须可达dFS(i);}}}public void bFSTrave(){for(int i=0;i<num;i++){visited[i]=false;//默认情况下所有顶点是没有被访问过的}Vertex v=null;Queue queue = new LinkedList();for(int i=0;i<num;i++){if(!visited[i]){visit(vertex[i]);visited[i]=true;//访问完成后入队queue.add( vertex[i]);while(!queue.isEmpty()){v = (Vertex) queue.poll();if(v!=null){int k = v.no;for(int j=k+1;j<num;j++){if(!visited[j]&&edges[k][j]!=0){visit(vertex[j]);visited[j]=true;queue.add( vertex[j]);}}}}}}}public static void main(String[] args) {Matrixgraph graph = new Matrixgraph();graph.createGraph();graph.dFSTrave();// graph.bFSTrave();}class Vertex {//图的顶点信息public int no;//顶点的标号public String info;//顶点的信息public Vertex(int i,String info){this.no = i; = info;}}}参考程序1：public class Graph {private int[] vertexs;private int vertexsize;private int[][] matrix;private boolean[] isvisited;private static final int MAX_WEIGHT=1000;public Graph(int vertexsize){this.vertexsize=vertexsize;matrix=new int[vertexsize][vertexsize];vertexs=new int[vertexsize];for(int i=0;i<vertexsize;i++){vertexs[i]=i;}isvisited=new boolean[vertexsize];}public int[] getVertexs() {return vertexs;}public void setVertexs(int[] vertexs) {this.vertexs = vertexs;}public int getweight(int v1,int v2){return matrix[v1][v2]==0?0:(matrix[v1][v2]==MAX_WEIGHT?-1:matrix[v1][v2]); }public int getdegree(int index){int degree=0;for(int j=0;j<matrix[index].length;j++){int weight=matrix[index][j];if(weight!=0&&weight!=MAX_WEIGHT){degree++;}}return degree;}//找某个顶点的第一个邻接点public int getfirstadj(int index){for(int j=0;j<vertexsize;j++){if(matrix[index][j]>0&&matrix[index][j]<MAX_WEIGHT){return j;}}return -1;}public int getnextadj(int v,int index){for(int j=index+1;j<vertexsize;j++){if(matrix[v][j]>0&&matrix[v][j]<MAX_WEIGHT){return j;}}return -1;}public void depthfirstsearch(int i){isvisited[i]=true;int w=getfirstadj(i);while(w!=-1){if(!isvisited[w]){System.out.println("访问"+w+"顶点");depthfirstsearch(w);}w=getnextadj(i,w);}}public void depthfirstsearch(){}public static void main(String[] args) {Graph graph=new Graph(5);int [] a1=new int[]{0,45,28,10,MAX_WEIGHT};int [] a2=new int[]{45,0,12,MAX_WEIGHT,21};int [] a3=new int[]{28,12,0,17,26};int [] a4=new int[]{10,MAX_WEIGHT,17,0,15};int [] a5=new int[]{MAX_WEIGHT,21,26,15,0};graph.matrix[0]=a1;graph.matrix[1]=a2;graph.matrix[2]=a3;graph.matrix[3]=a4;graph.matrix[4]=a5;//System.out.println("权值"+graph.getweight(0, 3));//System.out.println("v0的度："+graph.getdegree(2));graph.depthfirstsearch();}}。

为一个图建立一个邻接表、编写深度遍历和广度遍历算法#include <stdio.h>#include<stdlib.h>#define MaxNode 40#define M 20typedef struct ArcNode{ int adjvex;struct ArcNode *nextarc;}ArcNode;typedef struct{ int vertex;struct ArcNode *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){int i,visited[MaxNode]; //数组visited标志图中的顶点是否已被访问for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)bfs(g,i,visited);printf("\b\b \n");}void trave_dfs(adjlist g,int n){int i,visited[MaxNode]; //数组visited标志图中的顶点是否已被访问for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)dfs(g,i,visited);printf("\b\b \n");}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);q=q->nextarc;}printf("\b\b \n");}}void main(){ArcNode *p,*q;adjlist g;int i,j,n,k,e;printf("输入图中顶点的个数,边数:");scanf("%d%d",&n,&e);for(k=1;k<=n;k++){getchar();printf("\t第%d个顶点信息:",k);scanf("%d",&g[k].vertex);g[k].firstarc=NULL; //对顺序存储部分初始化}for(k=1;k<=e;k++){printf("第%d条边的起点,终点:",k);scanf("%d%d",&i,&j);q=(ArcNode *)malloc(sizeof(ArcNode));q->adjvex=j;q->nextarc=g[i].firstarc;g[i].firstarc=q;p=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex=i;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");。