数据结构实验五——图

数据结构实验报告

实验内容：专业班级：组 长：组 员： 实验五 图子系统

图 的 遍 历 问 题 网络工程专业 1002班 贾 鑫（2010100234） 贾鹏飞（2010100237） 邓桐桐（2010100229）

第十九小组实验报告

2012年 5月 18日

实验报告

实验类型： 综合 实验室： 软件实验室二

一、 实验名称 图子系统 二、实验目的和要求：

1.掌握图的存储思想及其存储实现

2.掌握图的深度、广度优先遍历算法思想及其程序实现 3．掌握图的常见应用算法的思想及其程序实现 三、实验内容

1．键盘输入以下结点数据：

太原、成都、北京、上海、天津、大连、河北。 建立一个有向图或无向图（自定）的邻接表并输出该邻接表

2．在图的邻接表的基础上计算各顶点的度，并输出 3．以有向图的邻接表为基础实现输出它的拓扑排序序列 4．采用邻接表存储实现无向图的深度优先遍历

第十九小组实验报告

5．采用邻接表存储实现无向图的广度优先遍历

6．采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法 7．在主函数中设计一个简单的菜单，分别调试上述算法 四、设计思路 执行顺序：

Create1() Print1() Create2() Topo() Du() DFSTavele() BFSTravel() 调用InitQuene()\\Enter()\\Leave()函数 Create3() Print2() Prim() 调用Push（）和Pop（）函数

五、代码实现

#include #include #include

#define M 20//顶点最大个数 typedef struct node{//边表结点

int adj;//边表结点数据域 struct node *next;

}node;

typedef struct vnode{//顶点表结点

char name[20]; node *fnext;

}vnode,AList[M]; typedef struct{

AList List;//邻接表 int v,e;//顶点树和边数

}*Graph;

Graph Create1( )//建立无向邻接表

第十九小组实验报告

{ Graph G;

int i,j,k; node *s;

G=malloc(M*sizeof(vnode)); }

Graph Create2() //有向邻接图 {

Graph G; int i,j,k; node *q;

G=malloc(M*sizeof(vnode));

printf(\"◤请输入顶点数和弧数（空格隔开）：\"); scanf(\"%d%d\

for (k=0;ke;k++) //建立边表 {

printf(\"◤请输入两顶点的序号（空格隔开）：\"); scanf(\"%d%d\

for (i=0;iv;i++) //建立有n个顶点的顶点表 { }

printf(\"◤请输入图第%d个元素：\

scanf(\"%s\ //读入顶点信息 G->List[i].fnext=NULL;

printf(\"◤输入图的顶点数和边数（空格隔开）：\"); scanf(\"%d%d\读入顶点数和边数 { }

for(i=0;iv;i++)//建立顶点表 {

printf(\"◤请输入图第%d个元素：\scanf(\"%s\读入顶点信息 G->List[i].fnext=NULL;//边表置为空表 }

printf(\"◤请输入边的两顶点序号（空格隔开）：\"); scanf(\"%d%d\读入边（Vi,Vj）的顶点对序号 s=(node *)malloc(sizeof(node));//生成边表结点 s->adj=j;

s->next=G->List[i].fnext;

G->List[i].fnext=s;//将新结点*s插入顶点Vi的边表头部 s=(node *)malloc(sizeof(node)); s->adj=i;//邻接点序号为i s->next=G->List[j].fnext;

G->List[j].fnext=s;// 将新结点*s插入顶点Vj的边表头部

for(k=0;ke;k++)//建立边表——建立了2倍边的结点

return G;

第十九小组实验报告

}

}

q=(node *)malloc(sizeof(node)); //生成新边表结点s q->adj=j; //邻接点序号为j q->next=G->List[i].fnext; G->List[i].fnext=q;

return G;

void Print1(Graph G)//输出无向图的邻接表 {int i; node *p;

printf(\"\\n\\\◎邻接表◎\\n\"); }

void Du(Graph G)//输出各元素的度数 {int i,j; node *p;

printf(\"\\n\\\◎各点度数◎\\n\"); {

for(i=0;iv;i++) { }

node *p;

printf(\"%2s \ flag[i]=1;

p=G->List[i].fnext; while(p) {

if(!flag[p->adj]) DFS(G,p->adj,flag); p=G->List[i].fnext;

printf(\"\\\顶点%2s的度为：\j=0; while(p) {

j++;

p=p->next;}

for(i=0;iv;i++) { }

p=G->List[i].fnext;

printf(\"\\\%d | %3s\ while(p)

{printf(\"—>%d\p=p->next; }

printf(\"\\n\");

printf(\"%d\\n\

}void DFS(Graph G,int i,int flag[])

第十九小组实验报告

}

}

p=p->next;

void DFSTravel(Graph G)//深度优先遍历 {int i;

int flag[M];//标志数组 for(i=0;iv;i++) }

typedef struct{//建立队列

int *elem; int front, rear; flag[i]=0; if(!flag[i])

DFS(G,i,flag);

for(i=0;iv;i++)

}*Queue;

void InitQueue(Queue Q)//队列初始化 { }

void Enter(Queue Q, int e)//入队 { }

void Leave(Queue Q, int e)//出队 { }

void BFSTravel(Graph G)//广度优先遍历 {

Queue Q; node *p; int i,j=0;

int flag[M];//标志数组 if(Q->rear != Q->front)

e = Q->elem[Q->front]; printf(\"队列空!\\n\"); else

Q->front = (Q->front+1)%M; if((Q->rear + 1)%M!= Q->front)

Q->elem[Q->rear ] = e; printf(\"队列满!\\n\"); else

Q->rear = (Q->rear + 1)%M;

Q->elem = (int *)malloc(M*sizeof(int)); if(!Q->elem) exit(0); Q->front = Q->rear = 0;

第十九小组实验报告

}

Q=malloc(sizeof(M)); InitQueue(Q); for(i=0;iv;i++)

flag[i]=0;

if(flag[i]==0)//此点未被访问 {

flag[i]=1;

printf(\"%2s \ Enter(Q,i);

while(Q->front!=Q->rear) {

Leave(Q,j);//队头元素出队并置为j p=G->List[j].fnext; while(p!=NULL) {

if(flag[p->adj]==0) {

printf(\"%2s \ flag[p->adj]=1; Enter(Q,p->adj);

for(i=0;iv;i++)

}//if p=p->next;

}//while

}//while

}//if

typedef struct stack{//栈的设计

int push(stack *s,int i) { }

int pop(stack *s,int j) {

stack *p;

p=(stack *)malloc(sizeof(stack)); p->x=i;

p->next=s->next; s->next=p; return 1; int x;

struct stack *next;

}stack;

第十九小组实验报告

stack *p=s->next;//保存栈顶指针 j=p->x;

s->next=p->next; //将栈顶元素摘下 free(p);//释放栈顶空间 }

void Topo(Graph G,stack *s)//拓扑排序—用有向图的邻接表实现 {

int i,k, count; int j=0;

int indegree[M]={0}; node *p;

for(i=0;iv;i++) {

p=G->List[i].fnext;; while(p!=NULL) {

indegree[p->adj]++; p=p->next; } }

for(i=0;iv;i++)

if(indegree[i]==0) count=0;

push(s,i); while(s->next!=NULL) {

i=pop(s,j);

printf(\"%2s \->List[i].name); ++count;

for(p=G->List[i].fnext;p!=NULL;p=p->next) {

k=p->adj;

if(!(--indegree[k])) push(s,k); } }

if(countv) printf(\"有回路!\"); char vex[20]; }typedef struct name{ }name,Lists[M]; typedef struct{

return j;

第十九小组实验报告

Lists l;

int edge[M][M];//邻接矩阵 int v1,e1;//顶点数和弧数

}*AGraph; typedef struct{

char name[20]; int lowcost;

}ClosEdge[M];

AGraph Create3( )//无向矩阵图有权值 {AGraph G1; int i,j,k,w;

G1=(AGraph )malloc(M*sizeof(AGraph)); }

void Print2(AGraph G1)//邻接矩阵输出函数 {int i,j;

printf(\"\\n\\\◎邻接矩阵◎\\n\"); for(i=0;iv1;i++) }

int minimum(ClosEdge cl,int vnum)

{/* 在辅助数组cl[vnum]中选择权值最小的顶点，并返回其位置 */ int i;

{ }

printf(\"\\n\\\");

printf(\"%3d\

for(j=0;jv1;j++)

printf(\"◤输入图的顶点数和边数：\");

scanf(\"%d%d\读入顶点数和边数 { }

for(i=0;iv1;i++)//建立顶点表 { }

for(j=0;jv1;j++)

G1->edge[i][j] = 9;//9仅表示此处无权值 printf(\"◤输入图第%d个元素：\scanf(\"%s\读入顶点信息

for(i=0;iv1;i++)//初始化邻接矩阵

for(k=0;ke1;k++)//构造邻接矩阵

printf(\"◤输入两顶点及边的权值：\"); scanf(\"%d%d%d\; fflush(stdin);//刷新缓冲区 G1->edge[i][j]=w; G1->edge[j][i]=w;

return G1;

第十九小组实验报告

int w,p; w=1000;

for(i=0;iif(cl[i].lowcost!=0&&cl[i].lowcostvoid Prim(AGraph G1) {

ClosEdge closedge; char A[20]; int i,j,p,u;

int w=100;//辅助权值 }

int main() {Graph G; AGraph G1; int i,t;

stack *s=(stack *)malloc(sizeof(stack));

s->next =NULL;

printf(\"\\\ *******图******* \\n\"); printf(\"\\\ ~~~~~~~~~~~~~~~~ \\n\"); printf(\"◤请输入起点元素：\");

scanf(\"%s\ printf(\"\\Prim算法:\\n\"); for(i=0;iv1;i++)

if(strcmp(G1->l[i].vex,A)==0)

u=i;

for(j=0;jv1;j++)

if(j!=u) { }

strcpy(closedge[j].name,G1->l[u].vex); closedge[j].lowcost=G1->edge[u][j];

closedge[u].lowcost=0; for(i=1;iv1;i++) {

p=minimum(closedge,G1->v1);

printf(\"\\%s---%s\\n\->l[p].vex); closedge[p].lowcost=0;//第p顶点并入U集 for(j=0;jv1;j++)

if(G1->edge[p][j]l[p].vex);

closedge[j].lowcost=G1->edge[p][j];}}

第十九小组实验报告

{

printf(\"\\\# 1.建无向邻接图 #\\n\"); printf(\"\\\# 2.建有向邻接图 #\\n\"); printf(\"\\\# 3.建无向矩阵图 #\\n\"); printf(\"\\\# 4. 各点度数 #\\n\"); printf(\"\\\# 5. DFS遍历 #\\n\"); printf(\"\\\# 6. BFS遍历 #\\n\"); printf(\"\\\# 7.拓扑排序---2 #\\n\"); printf(\"\\\# 8.Prim算法---3 #\\n\"); printf(\"\\\# 0. 退出程序 #\\n\"); printf(\"\\\ ~~~~~~~~~~~~~~~~\\n\"); printf(\"◤请您选择(0-8):\"); scanf(\"%d\ if(t<0||t>8)

printf(\"※输入出错!!!请重输：\\n\"); else {switch(t)

{ case 1: G=Create1();Print1(G);printf(\"\\n\"); break;

case 2: G=Create2();Print1(G);printf(\"\\n\"); break; case 3: G1=Create3(G1);Print2(G1);printf(\"\\n\");break;

for(i=0;;i++)

case 4: Du(G);printf(\"\\n\"); break;

case 5: printf(\"\\n\DFS遍历:\");DFSTravel(G); printf(\"\\n\"); break; case 6: printf(\"\\n\BFS遍历:\");BFSTravel(G); printf(\"\\n\"); break; case 7: printf(\"\拓扑排序:\");Topo(G,s); printf(\"\\n\"); break; case 8: Prim(G1);printf(\"\\n\"); break; case break; }}}}

0:printf(\"\\\**谢

谢

使

用

,再

见

!**\\n\");return

0;

六、实验结果 1.输入无向图的数据

第十九小组实验报告

2.显示各个结果

3.输入有向图数据

第十九小组实验报告

4.显示结果：

5.输入建邻接矩阵无向图数据

第十九小组实验报告

6.prim算法显示结果

七、实验小结

本次试验，综合了多种算法，并用到了栈和队列等数据结构，在经过努力后能够编写、调试、运行，实现了题目的要求。同时也对其

第十九小组实验报告

思想也有了深入了解。 八、试验分工

贾鑫：Create1()函数、FSTravel()函数、FSTravel()函数、

Prim()函数、Topo()函数、Print1()函数

贾鹏飞：Create2()函数、InitQuene()函数、Enter()函数、

邓桐桐：Leave()函数、Print2()函数

Create3()函数、Push()函数、Pop()函数