数据结构试验报告三图两种存储、拓扑排序.pdfVIP

西南大学 实 验 报 告 《数据结构与算法》课程 2016-2017学年度第1学期 专业年级 2015级计算机与科学学院 软件学院 姓 名 吴玉洁 学 号 任课教师 何国斌 实验教师 何国斌 上机地点 25-0913 西南大学计算机与信息科学学院 1 《数据结构与算法》课程实验报告（三） 实验题目 图 实验时间 2016-12-23 一、 实验目的及要求 1. 理解并掌握图的两种存储结构，即邻接矩阵（数组）存储、邻接表存储； 2. 掌握图的遍历方法：深度优先搜索、广度优先搜索； 3. 理解拓扑排序、关键路径、最短路径，掌握迪杰斯特拉算法。 二、实验内容、过程和结果（实验主要内容的介绍、主要的操作步骤、程序代码和测试数据及实验结果） 实现图的建立及存储（邻接矩阵、邻接表、深度优先、广度优先） 拓扑排序 #include stdio.h #include malloc.h #define MAX 100 typedef char DataType; typedef int VectorRelationType; typedef char VectorType; /*定义邻接矩阵*/ typedef struct arcell{ VectorRelationType adj; //权值 DataType * data; //数据 }arcell, adjmatrix[MAX][MAX]; typedef struct MGraph{ VectorType vexs[MAX]; //顶点向量 adjmatrix arcs; //邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和边数 }MGraph; typedef struct ArcNode{ int adjvex; //邻接点在头结点数组中的位置(下标) struct ArcNode * nextarc; //指向下一个表结点 DataType * date; }ArcNode; /*定义顶点结点*/ typedef struct VNode{ VectorType vexdata; ArcNode * firstarc; int count; }VNode, Adjlist[MAX]; /*定义邻接表*/ typedef struct ALGraph{ Adjlist vexs; int vexnum, arcnum; }ALGraph; /*确定v在邻接矩阵中位置*/ 2 int Locatevex(ALGraph * G, VectorType v){ int i; for(i = 0; i G-vexnum; i++) if(G-vexs[i].vexdata == v) return (i); return -1; } int locatevexM(MGraph * G, VectorType v) { int i; for(i = 0; i G-vexnum; i++) if(G-vexs[i] == v) return (i); return -1