数据结构_图_实验报告08

计算机科学与工程学院计算机科学与工程学院 算法与数据结构算法与数据结构 实验报告实验报告 八八 专业班级 2015 级计算机科学与 技术 1 实验地点403 机房 学生学号 1505120488 指导教师蔡琼 学生姓名杜成昊实验时间 2017 05 27 实验项目图的应用 实验类别基础性 设计性 综合性 其它 实验目的 及要求 1 熟练掌握图的基本存储方法 2 熟练掌握图的深度优先和广度优先搜索方法 3 掌握 AOV 网和拓扑排序算法 4 掌握 AOE 网和关键路径 成 绩 评 定 表 类 别评 分 标 准分值得分合 计 上机表现 积极出勤 遵守纪律 按要求完成设计任务 3030 分 程序与报告 程序代码规范 功能正确 报告详实完整 体现收获 7070 分 说明 说明 评阅教师 评阅教师 蔡琼蔡琼 日日 期 期 20172017 年年 6 6 月月 3 3 日日 计算机科学与工程学院 算法与数据结构 实验报告2 实 验 内 容 实验内容 拓扑排序 任意给定一个有向图 设计一个算法 对它进行拓扑排序 拓扑排序算法 思想 a 在有向图中任选一个没有前趋的顶点输出 b 从图中删除该顶点和所 有以它为尾的弧 c 重复上述 a b 直到全部顶点都已输出 此时 顶点输出 序列即为一个拓朴有序序列 或者直到图中没有无前趋的顶点为止 此情形表 明有向图中存在环 实验说明 拓扑排序算法伪代码如下 源代码如下 源代码如下 include include define STACK INIT SIZE 100 define STACKINCREMENT 10 define MAX 20 typedef int VertexType typedef struct ArcNode 表结点 int adjvex 弧所指向的顶点的位置 struct ArcNode nextarc ArcNode typedef struct VNode 头结点 VertexType data 顶点信息 ArcNode firstarc 指向第一条依附该弧的顶点指针 VNode AdjList typedef struct AdjList vertices int vexnum 1 栈 S 初始化 累加器 count 初始化 2 扫描顶点表 将没有前驱 即入度为 0 的顶点压栈 3 当栈 S 非空时循环 3 1 vj 退出栈顶元素 输出 vj 累加器加 1 3 2 将顶点 vj的各个邻接点的入度减 1 3 3 将新的入度为 0 的顶点入栈 4 if countbase int malloc STACK INIT SIZE sizeof int if s base exit 0 s top s base s stacksize STACK INIT SIZE void Push SqStack s int e if s top s base s stacksize s base int realloc s base STACK INIT SIZE STACKINCREMENT sizeof int if s base exit 0 s top s base s stacksize s stacksize STACKINCREMENT s top e void Pop SqStack s int e if s top s base exit 0 e s top void GetTop SqStack s int e if s top s base exit 0 e s top 1 int StackEmpty SqStack s if s base s top return 1 else return 0 void CreatAjacentMatrix int array int n 创建邻接矩矩阵 n 行 n 列 计算机科学与工程学院 算法与数据结构 实验报告4 int a int i j flag 0 printf 请输入一个 d 行 d 列的关于图的邻接矩阵 n n n for i 0 i n i for j 0 j n j scanf d array i n j a void PrintAjacentMatrix int array int n int i j for i 0 i n i for j 0 jvexnum n 初始化顶点数 G vertices VNode malloc n 1 sizeof VNode 头结点数组 开 辟 n 1 长度的数组空间 for i 1 ivertices i data i G vertices i firstarc NULL for i 0 i n i for j 0 jadjvex j 1 p nextarc G vertices i 1 firstarc G vertices i 1 firstarc p 计算机科学与工程学院 算法与数据结构 实验报告5 void FindInDegree ALGraph G int indegree 对顶点求入度 int i j ArcNode p for i 1 i G vexnum i indegree i 0 indispensable for i 1 i G vexnum i 对每个结点跑完整个邻接表 for j 1 jnextarc if G vertices i data p adjvex indegree i int TopologicalSort ALGraph G 拓扑排序算法 有向图采用邻接表存储结构 若 G 无回路 则 flag 0 输出 G 的顶点的一个拓扑序列 否则给出该有向 图有回路的提示 int i count k int indegree int malloc G vexnum 1 sizeof int SqStack S ArcNode p FindInDegree G indegree 对顶点求入度 indegree G vexnum initialStack 为避免重复检测入度为 0 的顶点 可另设一栈暂存放 所有入度为 0 的顶点 for i 1 inextarc k p adjvex 表结点的数据域 即对 i 号顶点的每个邻接点 的入度减 1 if indegree k 若入度减少为 0 则入栈 Push 计算机科学与工程学院 算法与数据结构 实验报告6 if count G vexnum 该有向图有回路 return 0 else return 1 void main int n int A ALGraph G printf 请输入你想创建的邻接矩矩阵的行列数 即顶点数 n scanf d A int malloc n n sizeof int CreatAjacentMatrix A n printf 输出该图的邻接矩阵 A n PrintAjacentMatri