华北水利水电学院数据结构实验报告
20 10 ～20 11 学年第一学期2008级计算机专业
实验四图的应用
一、实验目的：
1．掌握图的存储结构及其构造方法
2．掌握图的两种遍历算法及其执行过程
二、实验内容：
以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。
提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。
三、实验要求：
1．各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。
2．C/ C++完成算法设计和程序设计并上机调试通过。
3．撰写实验报告，提供实验结果和数据。
4．写出算法设计小结和心得。
四、程序源代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
typedef 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;
}//while
for(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);
}
有向图
五、程序运行情况（写出输入数据及运行结果）
六、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）
注：内容一律使用宋体五号字，单倍行间距
对图进行深度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次一旦Visit()失败，则操作失
败。