一．实验目的
熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的
关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。
二．实验原理
深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶
点未曾访问，则深度优先搜索可从图中某个顶点 v 出发，访问此顶点，然后依次从 v 的未被访问的邻接点出发深度优先遍历图，直至图中所有
与 v 有路径相通的顶点都被访问到；若此时图有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
图的邻接表的存储表示：
#define MAX_VERTEX_NUM 20
#define MAXNAME 10
typedef char VertexType[MAXNAME];
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
三．实验容
编写 LocateVex 函数， Create 函数， print 函数， main 函数，输入要构造的图的相关信息，得到其邻接表并输出显示。
四。实验步骤
1）结构体定义,预定义，全局变量定义。
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define FALSE 0
#define TRUE 1
#define MAX 20
typedef int Boolean;
#define MAX_VERTEX_NUM 20
#define MAXNAME 10
typedef char VertexType[MAXNAME];
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
ALGraph G;
Boolean visited[MAX];
int degree[MAX_VERTEX_NUM];// 定义一个数组求每一个顶点的总度数（无向图）或出度（有向图）。
2）编写LocateVex函数，确定所输入的边在G 中的位置，返回该边所在的行数或或列数。
int LocateVex(ALGraph G,VertexType v)
{
int i,n;
for(n=0;n { if(strcmp(v,G.vertices[n].data)==0) i=n; } return i; } 3）编写 Create 函数，采用邻接表构造图G，返回结构体变量G的值，并统计每一个顶点的总度数或出度。 ALGraph Create(ALGraph G) { int i,j,k;VertexType v1,v2;ArcNode *p; printf(" 请输入要构造的图的顶点数和弧数：\n"); scanf("%d%d",&G.vexnum,&G.arcnum); printf(" 请输入每一个顶点的名字： \n"); for(i=0;i { scanf("%s",&G.vertices[i].data); G.vertices[i].firstarc=NULL; } printf(" 各顶点的位置以及名称为：\n"); for(i=0;i printf("%6d%6s\n",i,G.vertices[i].data); printf(" 请输入要构造的是无向图还是有向图：无向用0 表示，有向用 1 表示： \n"); scanf("%d",&G.kind); for(i=0;i degree[i]=0; printf(" 请输入每条弧的始点和终点：\n"); if(G.kind==1) { for(k=0;k { scanf("%s%s",&v1,&v2); i=LocateVex(G,v1);j=LocateVex(G,v2); p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; degree[i]++; } } if(G.kind==0) { for(k=0;k { scanf("%s%s",&v1,&v2); i=LocateVex(G,v1);j=LocateVex(G,v2); p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; degree[i]++; p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=i; p->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p; degree[j]++; } } return G; } 4）编写 print函数，实现对所构建的图的邻接表的输出。void print(ALGraph G) { int i; ArcNode *p; for(i=0;i { printf("%6d%6s",i,G.vertices[i].data); for(p=G.vertices[i].firstarc;p;p=p->nextarc) printf("%6d",p->adjvex); printf("\n"); if(G.kind==1) printf(" 出度为： %6d\n",degree[i]); if(G.kind==0) printf(" 总度数为： %6d\n",degree[i]); } } 5）编写 FirstAdjVex函数，返回v 的第一个邻接点的编号。int FirstAdjVex(ALGraph G,int v) { ArcNode *p; p=G.vertices[v].firstarc; if(p) return(p->adjvex); else return -1; } 6）编写 NextAdjVex 函数，返回 v 第一个之后未被访问过的下一个邻接点。 int NextAdjVex(ALGraph G,int v,int w) { ArcNode *p;int i; for(p=G.vertices[v].firstarc;p;p=p->nextarc) { if(w!=p->adjvex) i=0; else i=1; if(i&&p) return p->nextarc->adjvex; else return -1; } } 7）编写 DFS函数，从第i 个顶点出发递归地深度优先遍历图G。void DFS(ALGraph G,int v) { int w; visited[v]=TRUE; printf("%s\n",G.vertices[v].data); for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(!visited[w]) DFS(G,w); } 8）编写 DFSTraverse 函数，对图G作深度优先遍历。 void DFSTraverse(ALGraph G) { int v; for(v=0;v visited[v]=FALSE; for(v=0;v if(!visited[v]) DFS(G,v); } 9）编写 main 函数，把以上几个函数结合到一起，用邻接表实现对一个图的构造，输入要构造的边的相关信息（总弧数，顶点数，边的两个顶 点的名称，有向图还是无向图），对其进行输出显示，并用深度优先搜 索的方法遍历所构建的图。 main() { ALGraph G; G=Create(G); printf(" 邻接表为： \n"); print(G); printf(" 深度遍历的结果为：\n"); DFSTraverse(G); } 五．实验结果 源程序代码： #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; ALGraph G; Boolean visited[MAX]; int degree[MAX_VERTEX_NUM]; int LocateVex(ALGraph G,VertexType v) { int i,n; for(n=0;n { if(strcmp(v,G.vertices[n].data)==0) i=n; } return i; } ALGraph Create(ALGraph G) { int i,j,k;VertexType v1,v2;ArcNode *p; printf(" 请输入要构造的图的顶点数和弧数： \n"); scanf("%d%d",&G.vexnum,&G.arcnum); printf(" 请输入每一个顶点的名字： \n"); for(i=0;i { scanf("%s",&G.vertices[i].data); G.vertices[i].firstarc=NULL; } printf(" 各顶点的位置以及名称为： \n"); for(i=0;i printf("%6d%6s\n",i,G.vertices[i].data); printf(" 请输入要构造的是无向图还是有向图：无向用0 表示，有向用 1 表示： \n"); scanf("%d",&G.kind); for(i=0;i degree[i]=0; printf(" 请输入每条弧的始点和终点：\n"); if(G.kind==1) { for(k=0;k { scanf("%s%s",&v1,&v2); i=LocateVex(G,v1);j=LocateVex(G,v2); p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; degree[i]++; } } if(G.kind==0) { for(k=0;k { scanf("%s%s",&v1,&v2); i=LocateVex(G,v1);j=LocateVex(G,v2); p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; degree[i]++; p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=i; p->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p; degree[j]++; } } return G; } void print(ALGraph G) { int i; ArcNode *p; for(i=0;i { printf("%6d%6s",i,G.vertices[i].data); for(p=G.vertices[i].firstarc;p;p=p->nextarc) printf("%6d",p->adjvex); printf("\n"); if(G.kind==1) printf(" 出度为： %6d\n",degree[i]); if(G.kind==0) printf(" 总度数为： %6d\n",degree[i]); } } int FirstAdjVex(ALGraph G,int v) { ArcNode *p; p=G.vertices[v].firstarc; if(p) return(p->adjvex); else return -1; } int NextAdjVex(ALGraph G,int v,int w) { ArcNode *p;int i; for(p=G.vertices[v].firstarc;p;p=p->nextarc) { if(w!=p->adjvex) i=0; else i=1; if(i&&p) return p->nextarc->adjvex; else return -1; } } void DFS(ALGraph G,int v) { int w; visited[v]=TRUE; printf("%s\n",G.vertices[v].data); for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(!visited[w]) DFS(G,w); } void DFSTraverse(ALGraph G) { int v; for(v=0;v visited[v]=FALSE; for(v=0;v if(!visited[v]) DFS(G,v); } main() { ALGraph G; G=Create(G); printf(" 邻接表为： \n"); print(G); printf(" 深度遍历的结果为：\n"); DFSTraverse(G); } 构造一个无向图G，如图所示。 V1 V2 V3 V5V6V7 V4 V8 图 G 运行结果截图： 实验结果显示：遍历的结果为：v1-v3-v7-v6-v2-v5-v8-v4。运行成功。六．实验结论 可以运用深度优先搜索的方法遍历一个用邻接表构建的图。
相关主题
文本预览