中南大学

算法分析与设计

实验报告

学生姓名 学 号

涂茂麟

专业班级 计算机科学与技术1303 指导老师

学 院 信息科学与工程学院

目录

实验一 DFS与BFS ........................................................................................................................... 3 实验二 最近点对问题 ..................................................................................................................... 7 实验三 拓扑排序 ........................................................................................................................... 10 实验四 N皇后问题 ....................................................................................................................... 12 实验五 0-1背包问题 .................................................................................................................... 16 实验六 最短路径 ........................................................................................................................... 20

实验一 DFS与BFS

实验目的：实现深度优先算法、宽度优先算法 实现原理： 深度优先搜索： 从图中某顶点v出发： （1）访问顶点v；

（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

广度优先搜索：

已知图G=(V,E)和一个源顶点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。

具体设计： 1. 数据结构

采用邻接链表作为图的数据结构。 public class Graph {//图

public VNode[] arrVnode=new VNode[100] ;//头结点数组 public int vexmun,arcmun;//节点总数、边界总数 public int time;//记录打开、关闭节点的时间 }

public class VNode {//节点类