图的建立与遍历实验报告
------------图的建立与遍历
姓名:曹庆松
班级: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的位置
