数 据 结 构
实
验
指
导
书
实验四 图
实验时数:4 学时
一:实验目的:
(1)掌握图的存储思想及其存储实现。
(2)掌握图的深度、广度优先遍历算法思想及其程序实现。
(3)掌握图的常见应用算法的思想及其程序实现。
(4)理解有向无环图、最短路径等算法
二:实验内容:
以下实验内容,1 和 2 为必做内容,3 为选做内容。
1.有向图
(1)键盘输入数据,建立一个有向图的邻接表,并输出该邻接表。
(2)在有向图的邻接表的基础上计算各顶点的度,并输出。
(3)以有向图的邻接表为基础实现并输出它的拓扑排序序列。
(4)在主函数中设计一个简单的菜单,分别调试上述算法。
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 8
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define VertexType int
typedef int SElemType;
//***********************图*******************************
typedef struct ArcNode//弧结点的结构
{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
int weight; //与弧相关的权值,无权则为 0
}ArcNode;
typedef struct VNode //顶点结点的结构
{
int degree,indegree; //顶点的度,入度
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum; //顶点的实际数,边的实际数
}ALGraph;
int LocateVex(ALGraph &G,VertexType u)
{
int i;
for(i=0;i<G.vexnum;++i)
{
if(u==G.vertices[i].data)
return i;
}
return -1;
}
void CreateDG(ALGraph &G)
{
VertexType v1,v2;
int i,j;
ArcNode *p;
printf("\ninput the grah's vexnum and arcnum:");
scanf("%d %d",&G.vexnum,&G.arcnum);
printf("\ninput vertect datas:");
for(i=0;i<G.vexnum;i++)
{
scanf("%d",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
for(int k=0;k<G.arcnum;k++)
{
printf("\ninput %dth arc's firstarc nextarc:\n",k+1);
scanf("%d %d",&v1,&v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);//head
if(i<0 || j<0)
{
printf("\nERROR!\n");
exit(0);
}
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
p->weight=0;
}
for(i=0;i<G.vexnum;i++)
{
printf("%d %d",i,G.vertices[i].data);
p=G.vertices[i].firstarc;
while(p)
{
printf("-->%d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}
int GraphExit(ALGraph G,int i,int j)
{
ArcNode *p;
p=G.vertices[i].firstarc;
while(p && p->adjvex!=j)
p=p->nextarc;
if(p) return 1;
else return 0;
}
void Degree(ALGraph &G,int i)
{
int j;
ArcNode *p;
p=G.vertices[i].firstarc;
G.vertices[i].indegree=0;
G.vertices[i].degree=0;
评论1