掌握图的结构特征,掌握图的建立及遍历运算的实现。.doc

洛阳理工学院实验报告 系部 计算机系 班级 B110505 学号 姓名 李满意 课程名称 数据结构 实验日期 2013.05.01 实验名称 图的遍历 成绩 实验目的： 掌握的结构特征，掌握运算。 电脑一台，VC++6.0软件。 实验内容与算法思想： 内容： 矩阵和邻接表实现图的深度优先遍历和广度优先遍历。 算法思想： 该程序中的深度优先有哪些信誉好的足球投注网站的基本过程是这样的：1，访问第一个出发点；2，依次以第一个出发点的未被访问的邻接点为出发点，深度优先有哪些信誉好的足球投注网站图，直至图中所有与第一个出发点有路径相通的顶点都被访问。若是非连通图，则图中一定还有顶点未被访问，需要从图中另选一个未被访问的顶点作为起始点，重复上述深度优先有哪些信誉好的足球投注网站过程，直至图中所有顶点均被访问过为止； 广度优先有哪些信誉好的足球投注网站的基本过程是：1；从图中某个顶点v出发，首先访问v；2，依次访问v的各个未被访问的邻接点。3，分别从这些邻接点出发，依次访问它们的各个未被访问的邻接点。访问时应为：如果第i个结点和第k个结点为当前端接点，且第i个结点和第k个结点之前被被访问，则第i个结点的所有未被访问的邻接点应在第k个结点的所有未被访问的邻接点之前访问。重复3，直到所有端接点均没有未被访问的邻接点为止。若此时还有顶点未被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止。 运行结果： 实验总结： 经过这次实验对图的基本知识很熟悉了，通过对深度优先遍历及广度优先遍历，对邻接矩阵及邻接表的使用也更加熟练了，所以以后还是要多加上机啊，复习以往的知识，巩固已学习的知识，还可以增强实际操作能力，提高实战能力。 另外，在这次实验中感受到图这一章还是很有难度的，以后应该多加练习。学好数据结构这门课程。 附：源程序： #include stdio.h #include malloc.h #define MAX_VERTEX_NUM 20 #define INFINITY 32768 #define True 1 #define False 0 #define Error -1 #define OK 1 typedef enum{DG,DN,UDG,UDN}GraphKind; typedef char VertexData; typedef int AdjType; typedef int OtherInfo; typedef struct ArcNode { AdjType adj; OtherInfo info; }ArcNode; typedef struct { VertexData vertex[MAX_VERTEX_NUM]; ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum; int arcnum; GraphKind kind; }AdjMatrix; typedef struct ArcNode2 { int adjvex; struct ArcNode2 *nextarc; OtherInfo info; }ArcNode2; typedef struct VertexNode { VertexData data; ArcNode2 *firstarc; }VertexNode; typedef struct { VertexNode vertex[MAX_VERTEX_NUM]; int vernum2,arcnum2; GraphKind kind2; }AdjList; typedef struct Node { int data; struct Node *next; }QueueNode; typedef struct { QueueNode *front; QueueNode *rear; }LinkQueue; int visited[MAX_VERTEX_NUM]; VertexData a[MAX_VERTEX_NUM]; VertexData b[MAX_VERTEX_NUM]; int InitQueue(LinkQueue *Q) { Q-front=(QueueNode *)malloc(sizeof(QueueNode)); if(Q-front!=NULL) { Q-front-next=NULL; Q-rear=Q-front; return True; } else return False; } int EnterQueue(LinkQueue *Q,int x) { QueueNode *p; p=(QueueNode *)malloc(sizeof(Queue