实现图的遍历算法实验报告
一实验题目: 实现图的遍历算法
二 实验要求:
2.1:（1）建立如图（p126 8.1）所示的有向图 G 的邻接矩阵，并输出之
（2）由有向图G的邻接矩阵产生邻接表，并输出之
（3）再由（2）的邻接表产生对应的邻接矩阵，并输出之
2.2 （1）输出如图8.1所示的有向图G从顶点0开始的深度优先遍历序 列（递归算法）
（2）输出如图8.1所示的有向图G从顶点0开始的深度优先遍历序 列（非递归算法）
（3）输出如图8.1所示的有向图G从顶点0开始的广度优先遍历序 列
三 实验内容:
3.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>的意义或信息}
基本操作：
CreateGraph( &G, V, VR )
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
DestroyGraph( &G )
初始条件：图G存在。
操作结果：销毁图G。
LocateVex( G, u )
初始条件：图G存在，u和G中顶点有相同特征。
操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。
GetVex( G, v )
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的值。
PutVex( &G, v, value )
初始条件：图G存在，v是G中某个顶点。
操作结果：对v赋值value。
FirstAdjVex( G, v )
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”。
NextAdjVex( G, v, w )
初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。
操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。
InsertVex( &G, v )
初始条件：图G存在，v和图中顶点有相同特征。
操作结果：在图G中增添新顶点v。
DeleteVex( &G, v )
初始条件：图G存在，v是G中某个顶点。
操作结果：删除G中顶点v及其相关的弧。
InsertArc( &G, v, w )
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中增添弧<v,w>，若G是无向的，则还增添对称弧<v,w>。
DeleteArc( &G, v, w )
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中删除弧<v,w>，若G是无向的，则还删除对称弧<v,w>。
DFSTraverse( G, Visit() )
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。
BFSTraverse( G, Visit() )
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。
}ADT Graph
3.2存储结构的定义;
#define maxx 100
#define inf 32767
int vis[maxx]={0};
/// 邻接矩阵
typedef struct
{
int no; ///顶点编号
int info;
} VertexType; ///顶点类型
typedef struct
{
int edges[maxx][maxx];
int n, e;
VertexType vexs[maxx];
} MGraph;
/// 邻接表
typedef struct ANode /// 边的结构定义
{
int adjvex; /// 边的终点位置
struct ANode *nextarc; ///指向下一条边的指针
int info; ///权值
} ArcNode;
typedef struct Vnode /// 表头定义
{
int data; ///顶点信息
ArcNode *firstarc; ///指向第一条边
}VNode;
typedef VNode AdjList[maxx];
typedef struct
{
AdjList adjlist; /// 邻接表
int n, e; /// 顶点数 n ， 边数 e
}ALGraph;
3.3基本操作实现:
void DispMat1( MGraph g)
{
int i, j;
for(i = 0;i < g.n; ++i)
{
for(j = 0;j < g.n; ++j)
{
if(g.edges[i][j] == inf)
{
printf("%3s","∞");
}
else
{
printf("%3d",g.edges[i][j]);
}
}
printf("\n");
}
}
void MatTolist(MGraph g, ALGraph *&G)
{
int i, j;
ArcNode *p;
G = (ALGraph *)malloc(sizeof(ALGraph));
for(i = 0;i < g.n; ++i)
G->adjlist[i].firstarc = NULL;
for(i = 0;i < g.n; ++i)
for(j = g.n - 1; j >= 0; --j)
if(g.edges[i][j] != 0&&g.edges[i][j] != inf)
{
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->info = g.edges[i][j];
p->nextarc = G->adjlist[i].firstarc;
G->adjlist[i].firstarc = p;
}
G->n = g.n;
G->e = g.e;
}
void DispAdj1(ALGraph *G)
{
int i;
ArcNode *p;
for(i = 0;i < G->n; ++i)
{
p = G->adjlist[i].firstarc;
printf("%3d:", i);
while(p!=NULL)
{
printf("%3d(%d)",p->adjvex,p->info);
p=p->nextarc;
}
printf("\n");
}
}
3.4解题思路：
1.深度优先遍历（递归）：用标记的方法，记录被访问过的节点，查找未访问点，并从未访问点开始进行递归。
2.深度优先遍历（非递归）：用栈模拟递归算法
3.广度优先遍历：用循环队列储存当前节点可访问点，并进行标记。再从队列中取出所有节点进行搜索未访问节点，如是循环，直到队列为空。
3.5解题过程：
实验源代码如下：
3.5.1图的遍历的算法
#include <stdio.h>
#include <malloc.h>
#define maxx 100
#define inf 32767
int vis[maxx]={0};
/// 邻接矩阵
typedef struct
{
int no; ///顶点编号
int info;
} VertexType; ///顶点类型
typedef struct
{
int edges[maxx][maxx];
int n, e;
VertexType vexs[maxx];
} MGraph;
/// 邻接表
typedef struct ANode /// 边的结构定义
{
int adjvex; /// 边的终点位置
struct ANode *nextarc; ///指向下一条边的指针
int info; ///权值
} ArcNode;
typedef struct Vnode /// 表头定义
{
int data; ///顶点信息
ArcNode *firstarc; ///指向第一条边
}VNode;
typedef VNode AdjList[maxx];
typedef struct
{
AdjList adjlist; /// 邻接表
int n, e; /// 顶点数 n ， 边数 e
}ALGraph;
void DispMat1( MGraph g)
{
int i, j;
for(i = 0;i < g.n; ++i)
{
for(j = 0;j < g.n; ++j)
{
if(g.edges[i][j] == inf)
{
printf("%3s","∞");
}
else
{
printf("%3d",g.edges[i][j]);
}
}
printf("\n");
}
}
void MatTolist(MGraph g, ALGraph *&G)
{
int i, j;
ArcNode *p;
G = (ALGraph *)malloc(sizeof(ALGraph));
for(i = 0;i < g.n; ++i)
G->adjlist[i].firstarc = NULL;
for(i = 0;i < g.n; ++i)
for(j = g.n - 1; j >= 0; --j)
if(g.edges[i][j] != 0&&g.edges[i][j] != inf)
{
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->info = g.edges[i][j];
p->nextarc = G->adjlist[i].firstarc;
G->adjlist[i].firstarc = p;
}
G->n = g.n;
G->e = g.e;
}
void DispAdj1(ALGraph *G)
{
int i;
ArcNode *p;
for(i = 0;i < G->n; ++i)
{
p = G->adjlist[i].firstarc;
printf("%3d:", i);
while(p!=NULL)
{
printf("%3d(%d)",p->adjvex,p->info);
p=p->nextarc;
}
printf("\n");
}
}
void DFS(ALGraph *G, int v)
{
ArcNode *p;
vis[v] = 1;
printf("%3d",v);
p = G->adjlist[v].firstarc;
while(p!=NULL)
{
if(vis[p->adjvex] == 0)
DFS(G,p->adjvex);
p = p->nextarc;
}
}
void DFS1(ALGraph *G, int v)
{
ArcNode *p;
ArcNode *st[maxx];
int top = -1, w, i;
for(i = 0;i < G->n; ++i)
{
vis[i] = 0;
}
printf("%3d",v);
vis[v] = 1;
top++;
st[top] = G->adjlist[v].firstarc;
while(top>-1)
{
p=st[top--];
while(p!=NULL)
{
w = p->adjvex;
if(vis[w] == 0)
{
printf("%3d",w);
vis[w] = 1;
top++;
st[top] = G->adjlist[w].firstarc;
break;
}
p = p->nextarc;
}
}
printf("\n");
}
void BFS(ALGraph *G, int v)
{
int i, w;
ArcNode *p;
int queue[maxx],front = 0,rear = 0;
for(i = 0;i < G->n; ++i)
vis[i] = 0;
printf("%3d",v);
vis[v] = 1;
rear = (rear + 1)%maxx;
queue[rear] = v;
while(front != rear)
{
front = (front + 1) % maxx;
w = queue[front];
p = G->adjlist[w].firstarc;
while(p != NULL)
{
if(vis[p->adjvex] == 0)
{
printf("%3d",p->adjvex);
vis[p->adjvex] = 1;
rear = (rear + 1)%maxx;
queue[rear] = p->adjvex;
}
p=p->nextarc;
}
}
printf("\n");
}
int main()
{
int i, j;
int A[maxx][6] =
{
{0,5,inf,7,inf,inf},
{inf,0,4,inf,inf,inf},
{8,inf,0,inf,inf,9},
{inf,inf,5,0,inf,6},
{inf,inf,inf,5,0,inf},
{3,inf,inf,inf,1,0}
};
MGraph g, g1;
ALGraph *G;
g.n = 6; g.e = 10;
for(i = 0;i < g.n; ++i)
for(j = 0;j < g.n ; ++j)
g.edges[i][j] = A[i][j];
printf("有向图 G 邻接矩阵：\n");
DispMat1(g);
G = (ALGraph *)malloc(sizeof(ALGraph));
printf("图 G 的邻接矩阵转换成邻接表：\n");
MatTolist(g,G);
DispAdj1(G);
printf("从顶点 0 开始的DFS（递归算法）：\n");
DFS(G,0);
printf("\n");
printf("从顶点 0 开始的DFS（非递归算法）：\n");
DFS1(G,0);
printf("从顶点 0 开始的BFS（非递归算法）：\n");
BFS(G,0);
printf("\n");
return 0;
}
四 实验结果:
