文档介绍:实验目的
熟悉图的存储结构,掌握用单链表存储数据元素信息和数据元素之间的 关系的信息的方法,并能运用图的深度优先搜索遍历一个图, 对其输出。
实验原理
深度优先搜索遍历是树的先根遍历的推广。 假设初始状态时图中所有顶
点未曾访问,则深度优先搜索可从图中某个顶点 v出发,访问此顶点,
然后依次从v的未被访问的邻接点出发深度优先遍历图, 直至图中所有
与v有路径相通的顶点都被访问到; 若此时图有顶点未被访问,贝U另选
图中一个未曾访问的顶点作起始点, 重复上述过程,直至图中所有顶点
都被访问到为止。
图的邻接表的存储表示:
#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函数,输入要构
造的图的相关信息,得到其邻接表并输出显示。
四。实验步骤
结构体定义,预定义,全局变量定义。
#include"”
#include"”
#include"”
#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<;n++)
(
if(strcmp(v,[n].data)==0)
i=n;
}
return i;
}
编写Create函数,采用邻接表构造图 G,返回结构体变量 G的值, 并统计每一个顶点的总度数或出度。
ALGraph Create(ALGraph G)
(
int i,j,k;VertexType v1,v2;ArcNode *p;
printf("请输入要构造的图的顶点数和弧数: \n");
scanf("%d%d",&,&);
printf("请输入每一个顶点的名字:\n");
for(i=0;i<;i++)
(
scanf("%s",&[i].data);
[i].firstarc=NULL;
printf("各顶点的位置以及名称为:\n");
for(i=0;i<;i++)
printf("%6d%6s\n",i,[i].data);
printf("请输入要构造的是无向图还是有向图:无向用 0表示,有向
用1表示:\n");
scanf("%d",&);
for(i=0;i<;i++)
degree[i]=0;
printf("请输入每条弧的始点和终点:\n");
if(