淮海工学院计算机工程学院
实验报告书
课程名： 《 数 据 结 构》 题 目： 图形数据结构实验
班 级：学 号： 姓 名：
实验3 图形数据结构实验
实验目的和要求
1．熟悉图的两种常用的存储结构，邻接矩阵和邻接表。
2．在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。 3．熟练掌握拓扑排序算法；理解求有向无环图的关键路径算法。 4．进一步掌握递归算法的设计方法。
实验环境
Turbo C 或VC++ 实验学时
4学时，必做实验 实验内容和步骤
一、要求画图并对所画的图进行DFS 和BFS 遍历。 如：
实验步骤
实验步骤： 1.输入图的顶点数目和边数.
2. 建立图的邻接表.
3. 按深度优先和广度优先遍历图. 4. 给出遍历序列.
源程序
#define N 10
#define INFINITY 32768 #define True 1 #define False 0 #define Error -1 #define Ok 1
#include "stdlib.h" #include "stdio.h"
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef char VertexData;
typedef struct ArcNode2 {
int adjvex;
struct ArcNode2 *nextarc; } ArcNode2;
typedef struct VertexNode {
VertexData data; ArcNode2 *firstarc; }VertexNode;
typedef struct {
VertexNode vertex[N]; int vexnum2,arcnum2; GraphKind kind2; }AdjList;
/*.............................*/
typedef struct Node {
int data;
struct Node *next; }LinkQueueNode;
typedef struct {
LinkQueueNode *front; LinkQueueNode *rear; }LinkQueue;
int InitQueue(LinkQueue *Q) {
Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode)); if(Q->front!=NULL) { Q->rear=Q->front; Q->front->next=NULL; return(True); }
else return(False); }
int EnterQueue(LinkQueue *Q,int x) {
LinkQueueNode *NewNode;
NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL) { NewNode->data=x; NewNode->next=NULL; Q->rear->next=NewNode; Q->rear=NewNode; return(True); } else return(False); }
int DeleteQueue(LinkQueue *Q,int *x) {
LinkQueueNode *p; if(Q->front==Q->rear) return(False); p=Q->front->next;
Q->front->next=p->next; if(Q->rear==p) Q->rear=Q->front; *x=p->data; free(p);
return(True); }
int IsEmpty(LinkQueue *Q) {
if(Q->front==Q->rear) return(True); else return(False); }
typedef struct node1 {
char data;
struct node1 *next; }Node1, *LinkList1;
typedef struct node2
char data1; char data2;
struct node2 *next; }Node2, *LinkList2;
int a[2];
int visited[N];
int LocateVertex2(AdjList *G2,VertexData v) {
int k,j=Error;
for(k=0;kvexnum2;k++) if(G2->vertex[k].data==v) { j=k; break; } return(j); }
int CreateUDG2(AdjList *G2) {
int i,j,k;
ArcNode2 *p,*r; VertexData v1,v2;
printf("\ninput G->vexnum,G->arcnum\n"); fflush(stdin);
scanf("%d,%d",&(G2->vexnum2),&(G2->arcnum2)); getchar();
printf("input G->vexs\n"); for(i=0;ivexnum2;i++) { fflush(stdin); scanf("%c",&(G2->vertex[i].data)); G2->vertex[i].firstarc=NULL; }
getchar();
printf("input G v1,v2\n"); fflush(stdin);
for(k=0;karcnum2;k++) {
fflush(stdin); scanf("%c,%c",&v1,&v2);
}
i=LocateVertex2(G2,v1); j=LocateVertex2(G2,v2);
if(G2->vertex[i].firstarc==NULL) { p=(ArcNode2*)malloc(sizeof(ArcNode2)); if(p==NULL) return(False); G2->vertex[i].firstarc=p; p->adjvex=j; p->nextarc=NULL; } else { r=G2->vertex[i].firstarc; while(r->nextarc!=NULL) r=r->nextarc; p=(ArcNode2*)malloc(sizeof(ArcNode2)); if(p==NULL) return(False); r->nextarc=p; p->adjvex=j; p->nextarc=NULL; }
if(G2->vertex[j].firstarc==NULL) { p=(ArcNode2*)malloc(sizeof(ArcNode2)); if(p==NULL) return(False); G2->vertex[j].firstarc=p; p->adjvex=i; p->nextarc=NULL; } else { r=G2->vertex[j].firstarc; while(r->nextarc!=NULL) r=r->nextarc; p=(ArcNode2*)malloc(sizeof(ArcNode2)); if(p==NULL) return(False); r->nextarc=p; p->adjvex=i; p->nextarc=NULL; }
return(Ok); }
void Breadth2(AdjList g2,int vo) {
ArcNode2 *p; int vi;
LinkQueue Q; InitQueue(&Q); visited[vo]=True; EnterQueue(&Q,vo); while(!IsEmpty(&Q)) { DeleteQueue(&Q,&vi); printf("%c",g2.vertex[vi].data); p=g2.vertex[vi].firstarc; while(p!=NULL) { if(!visited[p->adjvex]) { visited[p->adjvex]=True; EnterQueue(&Q,p->adjvex); } p=p->nextarc; } } }
void Depth2(AdjList g2,int vo) {
ArcNode2 *p;
printf("%c",g2.vertex[vo].data); visited[vo]=True;
p=g2.vertex[vo].firstarc; while(p!=NULL) { if(!visited[p->adjvex]) Depth2(g2,p->adjvex); p=p->nextarc; } }
void Traverse2(AdjList g2) { int vi;
for(vi=0;vi
printf("\nThe order of G2 Depth\n"); for(vi=0;vi
for(vi=0;vi
printf("\nThe order of G2 Breadth\n"); for(vi=0;vi
int main( ) {
AdjList g2;
CreateUDG2(&g2); Traverse2(g2); return 0; }
测试数据与实验结果（可以抓图粘贴）
实验体会
1.对于运用图表和遍历还存在很大的毛病。 二、图的应用实验——计算AOE 网的关键路径
内容：按照图的“邻接表”存储结构表示AOE 网，实现求其关键路径的算法，并验证如下图1所示AOE 网的关键路径。
实验步骤
实验步骤： 1.输入图的顶点数目
.
2. 按偏序顺序输入各边顶点及权值. 3. 输入(0,0)结束
4. 程序会自动计算出关键路径
源程序
# include # include
# define max_vertex_num 50 # define maxvalue 32760 # define NULL 0
typedef struct edgenode{ int adjvex; struct edgenode *next;
int weight; }edgenode,* pedgenode;
typedef struct vnode{
int data; struct edgenode *firstarc;
}vnode,adjlist[max_vertex_num],* pvnode;
void creatgraphadlist(pvnode &pn,int n) {
//依次输入顶点偶对，建立无向图邻接表 edgenode *p; int i,j,k,wei; i=j=1;
pn=(pvnode)malloc((n+1)*sizeof(vnode)); for(k=1;k
pn[k].firstarc=NULL;//初始化每个链表为空
for(int f=1;!(i==0&&j==0);) {
cout>i>>j;
if(i>0&&i0&&j
p=(edgenode *)malloc(sizeof(edgenode));//生成一个节点 p->adjvex=j;//为节点j 的序号附值为j
p->next=pn[i].firstarc;//将该p 节点作为第i 个链表的第一个节点插入pn[i]之后
pn[i].firstarc=p;//将接点j 作为第一个接点插入连表i 的后面 cout>wei;p->weight =wei; f++; }
else if(i==0&&j==0)
;//什么也不做
else cout
}//for
cout
}
void findindegree(pvnode pn,int n,int *deg)
{
for(int i=1;i
deg[i]=0;//对数组进行初始化，全部置0
pedgenode pk;
for(i=1;i
{
pk=pn[i].firstarc;
for(;pk;pk=pk->next)
deg[pk->adjvex]++;//数组相应元素自增
}
}
int ve[max_vertex_num];//存放各点发生的最早时刻(全局变量)
int st[max_vertex_num];//存放拓扑序列各顶点的栈(全局变量)
int top2;//(全局变量)
void topologicalorder(pvnode pn,int n,int *tt)
{
int indegree[max_vertex_num];//该数组存放各顶点的入度
int ss[max_vertex_num];//设计栈ss ，用以存放入度为0的顶点的信息
int *deg;int j;
deg=indegree;
findindegree(pn,n,deg);
for(int i=1;i
ve[i]=0;//初始化
int top1;
top1=top2=0;//top1和top2为栈顶指针，分别指向栈ss 和tt ，初始值均为0(即栈为空) for(i=1;i
if(!indegree[i])//若顶点i 入度为0，则进栈
ss[++top1]=i;
int count=0;//对输出顶点计数
cout
while(top1)//若ss 非空，进入循环
{
j=ss[top1--];//i出栈
cout
tt[++top2]=j;//将i 进入tt 栈
count++;//计数
for(pedgenode p=pn[j].firstarc ;p;p=p->next )
{
int k=p->adjvex ;
indegree[k]--;//对每一个以i 为弧尾的顶点，将他们的入度减1
if(!indegree[k])
ss[++top1]=k;//如果减为0，则入栈。因为若入度为x, 必然要自减x 次才能如栈，所以可以避免重复进栈
if((ve[j]+p->weight)>ve[k])
ve[k]=ve[j]+p->weight;//显然此时j 是k 的前驱，且ve[j]是j 发生的最早时间，若
}
}
if(count
{
cout
return;
}
cout
for(i=1;i
cout
cout
void criticalpath(pvnode pn,int n,int *tt)
{
int j,k,dut,ee,el,tag,f=1;
pedgenode p;
int vl[max_vertex_num];//存放各点发生的最迟时刻
for(int i=1;i
vl[i]=ve[n];//用顶点n 的最早时间初始化各顶点的最迟时间*/
while(top2)
{
j=tt[top2--];//出栈
for(p=pn[j].firstarc ;p;p=p->next )
{
k=p->adjvex ;
dut=p->weight;
if((vl[k]-dut)
}
}
cout
for(j=1;j
for(p=pn[j].firstarc ;p;p=p->next )
{
k=p->adjvex ;
dut=p->weight ;
ee=ve[j];el=vl[k]-dut;
if(ee==el) //ee==el,说明是关键活动
cout
}
}
int main()
{
int n,*tt;
pvnode pn;
tt=st;
cout
cin>>n;
cout
creatgraphadlist(pn,n);
topologicalorder(pn,n,tt);
criticalpath(pn,n,tt);
return 0;
}
测试数据与实验结果（可以抓图粘贴）
实验体会
做这次试验我感觉很吃力，邻接表，邻接矩阵都运用的不是很熟练，在书本上没有找到相应的算法，只能硬着头皮自己想办法，跟同学交流了很久才渐渐有了头绪，一开始做
起来还是遇到了很多的困难。之后在图书馆查阅了很多的资料，找了很多的实例才写出最终的算法，希望老师可以给我们一些算法实例，我们结合书本上的理论知识也许会有更好，更深刻的理解。
淮海工学院计算机工程学院
实验报告书
课程名： 《 数 据 结 构》 题 目： 图形数据结构实验
班 级：学 号： 姓 名：
实验3 图形数据结构实验
实验目的和要求
1．熟悉图的两种常用的存储结构，邻接矩阵和邻接表。
2．在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。 3．熟练掌握拓扑排序算法；理解求有向无环图的关键路径算法。 4．进一步掌握递归算法的设计方法。
实验环境
Turbo C 或VC++ 实验学时
4学时，必做实验 实验内容和步骤
一、要求画图并对所画的图进行DFS 和BFS 遍历。 如：
实验步骤
实验步骤： 1.输入图的顶点数目和边数.
2. 建立图的邻接表.
3. 按深度优先和广度优先遍历图. 4. 给出遍历序列.
源程序
#define N 10
#define INFINITY 32768 #define True 1 #define False 0 #define Error -1 #define Ok 1
#include "stdlib.h" #include "stdio.h"
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef char VertexData;
typedef struct ArcNode2 {
int adjvex;
struct ArcNode2 *nextarc; } ArcNode2;
typedef struct VertexNode {
VertexData data; ArcNode2 *firstarc; }VertexNode;
typedef struct {
VertexNode vertex[N]; int vexnum2,arcnum2; GraphKind kind2; }AdjList;
/*.............................*/
typedef struct Node {
int data;
struct Node *next; }LinkQueueNode;
typedef struct {
LinkQueueNode *front; LinkQueueNode *rear; }LinkQueue;
int InitQueue(LinkQueue *Q) {
Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode)); if(Q->front!=NULL) { Q->rear=Q->front; Q->front->next=NULL; return(True); }
else return(False); }
int EnterQueue(LinkQueue *Q,int x) {
LinkQueueNode *NewNode;
NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL) { NewNode->data=x; NewNode->next=NULL; Q->rear->next=NewNode; Q->rear=NewNode; return(True); } else return(False); }
int DeleteQueue(LinkQueue *Q,int *x) {
LinkQueueNode *p; if(Q->front==Q->rear) return(False); p=Q->front->next;
Q->front->next=p->next; if(Q->rear==p) Q->rear=Q->front; *x=p->data; free(p);
return(True); }
int IsEmpty(LinkQueue *Q) {
if(Q->front==Q->rear) return(True); else return(False); }
typedef struct node1 {
char data;
struct node1 *next; }Node1, *LinkList1;
typedef struct node2
char data1; char data2;
struct node2 *next; }Node2, *LinkList2;
int a[2];
int visited[N];
int LocateVertex2(AdjList *G2,VertexData v) {
int k,j=Error;
for(k=0;kvexnum2;k++) if(G2->vertex[k].data==v) { j=k; break; } return(j); }
int CreateUDG2(AdjList *G2) {
int i,j,k;
ArcNode2 *p,*r; VertexData v1,v2;
printf("\ninput G->vexnum,G->arcnum\n"); fflush(stdin);
scanf("%d,%d",&(G2->vexnum2),&(G2->arcnum2)); getchar();
printf("input G->vexs\n"); for(i=0;ivexnum2;i++) { fflush(stdin); scanf("%c",&(G2->vertex[i].data)); G2->vertex[i].firstarc=NULL; }
getchar();
printf("input G v1,v2\n"); fflush(stdin);
for(k=0;karcnum2;k++) {
fflush(stdin); scanf("%c,%c",&v1,&v2);
}
i=LocateVertex2(G2,v1); j=LocateVertex2(G2,v2);
if(G2->vertex[i].firstarc==NULL) { p=(ArcNode2*)malloc(sizeof(ArcNode2)); if(p==NULL) return(False); G2->vertex[i].firstarc=p; p->adjvex=j; p->nextarc=NULL; } else { r=G2->vertex[i].firstarc; while(r->nextarc!=NULL) r=r->nextarc; p=(ArcNode2*)malloc(sizeof(ArcNode2)); if(p==NULL) return(False); r->nextarc=p; p->adjvex=j; p->nextarc=NULL; }
if(G2->vertex[j].firstarc==NULL) { p=(ArcNode2*)malloc(sizeof(ArcNode2)); if(p==NULL) return(False); G2->vertex[j].firstarc=p; p->adjvex=i; p->nextarc=NULL; } else { r=G2->vertex[j].firstarc; while(r->nextarc!=NULL) r=r->nextarc; p=(ArcNode2*)malloc(sizeof(ArcNode2)); if(p==NULL) return(False); r->nextarc=p; p->adjvex=i; p->nextarc=NULL; }
return(Ok); }
void Breadth2(AdjList g2,int vo) {
ArcNode2 *p; int vi;
LinkQueue Q; InitQueue(&Q); visited[vo]=True; EnterQueue(&Q,vo); while(!IsEmpty(&Q)) { DeleteQueue(&Q,&vi); printf("%c",g2.vertex[vi].data); p=g2.vertex[vi].firstarc; while(p!=NULL) { if(!visited[p->adjvex]) { visited[p->adjvex]=True; EnterQueue(&Q,p->adjvex); } p=p->nextarc; } } }
void Depth2(AdjList g2,int vo) {
ArcNode2 *p;
printf("%c",g2.vertex[vo].data); visited[vo]=True;
p=g2.vertex[vo].firstarc; while(p!=NULL) { if(!visited[p->adjvex]) Depth2(g2,p->adjvex); p=p->nextarc; } }
void Traverse2(AdjList g2) { int vi;
for(vi=0;vi
printf("\nThe order of G2 Depth\n"); for(vi=0;vi
for(vi=0;vi
printf("\nThe order of G2 Breadth\n"); for(vi=0;vi
int main( ) {
AdjList g2;
CreateUDG2(&g2); Traverse2(g2); return 0; }
测试数据与实验结果（可以抓图粘贴）
实验体会
1.对于运用图表和遍历还存在很大的毛病。 二、图的应用实验——计算AOE 网的关键路径
内容：按照图的“邻接表”存储结构表示AOE 网，实现求其关键路径的算法，并验证如下图1所示AOE 网的关键路径。
实验步骤
实验步骤： 1.输入图的顶点数目
.
2. 按偏序顺序输入各边顶点及权值. 3. 输入(0,0)结束
4. 程序会自动计算出关键路径
源程序
# include # include
# define max_vertex_num 50 # define maxvalue 32760 # define NULL 0
typedef struct edgenode{ int adjvex; struct edgenode *next;
int weight; }edgenode,* pedgenode;
typedef struct vnode{
int data; struct edgenode *firstarc;
}vnode,adjlist[max_vertex_num],* pvnode;
void creatgraphadlist(pvnode &pn,int n) {
//依次输入顶点偶对，建立无向图邻接表 edgenode *p; int i,j,k,wei; i=j=1;
pn=(pvnode)malloc((n+1)*sizeof(vnode)); for(k=1;k
pn[k].firstarc=NULL;//初始化每个链表为空
for(int f=1;!(i==0&&j==0);) {
cout>i>>j;
if(i>0&&i0&&j
p=(edgenode *)malloc(sizeof(edgenode));//生成一个节点 p->adjvex=j;//为节点j 的序号附值为j
p->next=pn[i].firstarc;//将该p 节点作为第i 个链表的第一个节点插入pn[i]之后
pn[i].firstarc=p;//将接点j 作为第一个接点插入连表i 的后面 cout>wei;p->weight =wei; f++; }
else if(i==0&&j==0)
;//什么也不做
else cout
}//for
cout
}
void findindegree(pvnode pn,int n,int *deg)
{
for(int i=1;i
deg[i]=0;//对数组进行初始化，全部置0
pedgenode pk;
for(i=1;i
{
pk=pn[i].firstarc;
for(;pk;pk=pk->next)
deg[pk->adjvex]++;//数组相应元素自增
}
}
int ve[max_vertex_num];//存放各点发生的最早时刻(全局变量)
int st[max_vertex_num];//存放拓扑序列各顶点的栈(全局变量)
int top2;//(全局变量)
void topologicalorder(pvnode pn,int n,int *tt)
{
int indegree[max_vertex_num];//该数组存放各顶点的入度
int ss[max_vertex_num];//设计栈ss ，用以存放入度为0的顶点的信息
int *deg;int j;
deg=indegree;
findindegree(pn,n,deg);
for(int i=1;i
ve[i]=0;//初始化
int top1;
top1=top2=0;//top1和top2为栈顶指针，分别指向栈ss 和tt ，初始值均为0(即栈为空) for(i=1;i
if(!indegree[i])//若顶点i 入度为0，则进栈
ss[++top1]=i;
int count=0;//对输出顶点计数
cout
while(top1)//若ss 非空，进入循环
{
j=ss[top1--];//i出栈
cout
tt[++top2]=j;//将i 进入tt 栈
count++;//计数
for(pedgenode p=pn[j].firstarc ;p;p=p->next )
{
int k=p->adjvex ;
indegree[k]--;//对每一个以i 为弧尾的顶点，将他们的入度减1
if(!indegree[k])
ss[++top1]=k;//如果减为0，则入栈。因为若入度为x, 必然要自减x 次才能如栈，所以可以避免重复进栈
if((ve[j]+p->weight)>ve[k])
ve[k]=ve[j]+p->weight;//显然此时j 是k 的前驱，且ve[j]是j 发生的最早时间，若
}
}
if(count
{
cout
return;
}
cout
for(i=1;i
cout
cout
void criticalpath(pvnode pn,int n,int *tt)
{
int j,k,dut,ee,el,tag,f=1;
pedgenode p;
int vl[max_vertex_num];//存放各点发生的最迟时刻
for(int i=1;i
vl[i]=ve[n];//用顶点n 的最早时间初始化各顶点的最迟时间*/
while(top2)
{
j=tt[top2--];//出栈
for(p=pn[j].firstarc ;p;p=p->next )
{
k=p->adjvex ;
dut=p->weight;
if((vl[k]-dut)
}
}
cout
for(j=1;j
for(p=pn[j].firstarc ;p;p=p->next )
{
k=p->adjvex ;
dut=p->weight ;
ee=ve[j];el=vl[k]-dut;
if(ee==el) //ee==el,说明是关键活动
cout
}
}
int main()
{
int n,*tt;
pvnode pn;
tt=st;
cout
cin>>n;
cout
creatgraphadlist(pn,n);
topologicalorder(pn,n,tt);
criticalpath(pn,n,tt);
return 0;
}
测试数据与实验结果（可以抓图粘贴）
实验体会
做这次试验我感觉很吃力，邻接表，邻接矩阵都运用的不是很熟练，在书本上没有找到相应的算法，只能硬着头皮自己想办法，跟同学交流了很久才渐渐有了头绪，一开始做
起来还是遇到了很多的困难。之后在图书馆查阅了很多的资料，找了很多的实例才写出最终的算法，希望老师可以给我们一些算法实例，我们结合书本上的理论知识也许会有更好，更深刻的理解。