图的建立与遍历实验报告

1、图的建立与遍历实验报告 图的建立与遍历姓名: 曹庆松班级:1104 学号:1111611512实验日期 :2012.10.15报告撰写日期 :2012.10.16一、 实验目的 :1、 熟悉图的概念、存储结构和遍历方法。3 、 以邻接2、 以邻接表为存储结构，掌握无向图的基本操作和实现方法。表为存储结构，掌握无向图的深度优先遍历的算法实现。二、 实验内容 : 以邻接表为存储结构，编写程序实现。1、 要求通过键盘输入图的顶点，以及每一条边的两个顶点从而建 立无向。为了简化实验，顶点用数字表示。程序代码及结2、 在以上实验的基础上，实现无向图的深度优先遍历算法。要求 以用户给定的顶点为起始点，显示

2、深度优先遍历的次序。 三、 果展示:#include "stdafx.h"#include<stdio.h>#include<stdlib.h>#include <malloc.h>#define MAX_VERTER_NUM 20 typedef struct ArcNode / 表节点 int adjvex; / 邻接点 struct ArcNode *nextarc; /指向下一条弧的指针ArcNode;typedef struct VNode / 头结点int data; / 定点信息ArcNode * firstarc; /指向

3、第一个依附该顶点的弧的指针VNode,AdjListMAX_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;k<G->vexnum;k+) if(G->verticesk.data=v)n=k;break; return n;int n=1;递归调用int visited

4、MAX_VERTER_NUM; void DFS(ALGraph *G,int v)/ ArcNode *p;>verticesv.firstarc; p=G-if(n<G->vexnum+1)printf(" V%d ",G->verticesv.data);n+;visitedv=1;while(p) if(!visitedp->adjvex)DFS(G,p->adjvex);p=p->nextarc;void DFSVisited(ALGraph * G)/ 深度遍历int v;int n;printf(" 请输入遍

5、历的起始的顶点 :"); scanf("%d",&n);n"); printf(" 递归深度优先遍历点顺序 : DFS(G,n-1);for(v=0;v<G->vexnum;v+)visitedv=0;for(v=0;v<G->vexnum;v+)if(!visitedv)DFS(G,v);插入邻接点的下标 void Insertadj(ALGraph * G,int i,int j) /ArcNode *a1,*a2;a1=(ArcNode *)malloc(sizeof(ArcNode); a1->ad

6、jvex=j;a1->nextarc=NULL;if(G->verticesi.firstarc=NULL)G->verticesi.firstarc=a1;elsea2=G->verticesi.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",&a

7、mp;G->vexnum);printf(" 请输入边数 :"); scanf("%d",&G->arcnum);for(v=0;v<G->vexnum;v+)printf(" 顶点 V%d:",(v+1); scanf("%d",&(G->verticesv.data);>verticesv.firstarc=NULL; G-for(v=0;v<G->arcnum;v+) printf(" 请输入点 点: "); scanf(&q

8、uot;%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;四、 实验总结 :通过本实验，我对图的存储结构、图的遍历等有了比较深的理解与运用，图的遍历和树的遍历很类似，但是却比树的遍历复杂很多。因为