图的建立与遍历实验报告
------------图的建立与遍历
姓名:曹庆松
班级:1104
学号:1111611512
实验日期:2012.10.15
报告撰写日期:2012.10.16
一、 实验目的:
1、 熟悉图的概念、存储结构和遍历方法。
2、 以邻接表为存储结构，掌握无向图的基本操作和实现方法。 3、 以邻接表为存储结构，掌握无向图的深度优先遍历的算法实
现。
二、 实验内容:
以邻接表为存储结构，编写程序实现。
1、 要求通过键盘输入图的顶点，以及每一条边的两个顶点从而建
立无向。为了简化实验，顶点用数字表示。
2、 在以上实验的基础上，实现无向图的深度优先遍历算法。要求
以用户给定的顶点为起始点，显示深度优先遍历的次序。 三、 程序代码及结果展示:
#include "stdafx.h"
#include
#include
#include
#define MAX_VERTER_NUM 20
typedef struct ArcNode
{ //表节点
int adjvex; //邻接点
struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode;
typedef struct VNode
{ //头结点
int data; //定点信息
ArcNode * firstarc; //指向第一个依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTER_NUM];
typedef struct
{ //图
AdjList vertices; //顶
int vexnum,arcnum;//图的顶点数和弧数
int Kind;// 图的种类标志
}ALGraph;// 对图 G 作深度优先遍历
int LocateVex(ALGraph * G,int v) //寻找节点V的位置 {
int k,n;
for(k=0;kvexnum;k++)
{ if(G->vertices[k].data==v)
{
n=k;
break;
}
}
return n;
}
int n=1;
int visited[MAX_VERTER_NUM]; void DFS(ALGraph *G,int v)//递归调用
{
ArcNode *p;
>vertices[v].firstarc; p=G-
if(nvexnum+1)
{
printf(" V%d ",G->vertices[v].data);
n++;
}
visited[v]=1;
while(p)
{
if(!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->nextarc;
}
}
void DFSVisited(ALGraph * G)//深度遍历
{
int v;
int n;
printf("请输入遍历的起始的顶点:");
scanf("%d",&n);
n"); printf("递归深度优先遍历点顺序: \
DFS(G,n-1);
for(v=0;vvexnum;v++)
visited[v]=0;
for(v=0;vvexnum;v++)
if(!visited[v])
DFS(G,v);
}
void Insertadj(ALGraph * G,int i,int j) //插入邻接点的下标 {
ArcNode *a1,*a2;
a1=(ArcNode *)malloc(sizeof(ArcNode));
a1->adjvex=j;a1->nextarc=NULL;
if(G->vertices[i].firstarc==NULL)
{
G->vertices[i].firstarc=a1;
}
else
{
a2=G->vertices[i].firstarc;
while(a2->nextarc)
{
a2=a2->nextarc;
}
a2->nextarc=a1;
}
}
void Init_ALGraph(ALGraph * G) //初始化图并建图 {
int v,v1,v2,i,j,q,p;
int m=0;
printf("请输入顶点数:");
scanf("%d",&G->vexnum);
printf("请输入边数:");
scanf("%d",&G->arcnum);
for(v=0;vvexnum;v++)
{
printf("顶点 V%d:",(v+1));
scanf("%d",&(G->vertices[v].data));
>vertices[v].firstarc=NULL; G-
}
for(v=0;varcnum;v++) {
printf("请输入点 点: ");
scanf("%d%d",&v1,&v2);
i=LocateVex(G,v1); //v1的位置
j=LocateVex(G,v2); //v2的位置
Insertadj(G,i,j);
Insertadj(G,j,i);
}
}
int main(int argc,char **argv) {
ALGraph G;
Init_ALGraph(&G);//初始化图并建图
DFSVisited(&G);//深度优先遍历
printf("\n");
return 0;
}
四、 实验总结:
通过本实验，我对图的存储结构、图的遍历等有了比较深的理解与运用，图的遍历和树的遍历很类似，但是却比树的遍历复杂很多。因为图具有结点与结点之间的关系可以是任意的，任意两个数据元素时间都可能相关等特点，所以图的应用很广泛。本实验用邻接表形式存储图是比较普遍的，而对图的遍历有两种本实验旨在深度优先遍历，深度优先遍历很多时候我们会用递归方法解决，要把所有的结点都被访问为止。
本文档为【图的建立与遍历实验报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483