图的算法演示.doc

图的算法演示
演示了四种图的算法：深度优先遍历、广度优先遍历、最小生成树、图的最短路径
界面上的节点可以任意拖动，节点间距离为两点间实测直线距离，单位为象素
运行与下载:
进入演示页面(applet)点击运行该程序(jar)若图的算法演示
演示了四种图的算法：深度优先遍历、广度优先遍历、最小生成树、图的最短路径
界面上的节点可以任意拖动，节点间距离为两点间实测直线距离，单位为象素
运行与下载:
进入演示页面(applet)点击运行该程序(jar)若不能正常运行请先安装 Java运行环境(JRE)
可执行文件、文档、源代码下载：
File: Click to Download
图的结构有两种可选：
一，完全无向图：任意两个节点间都有一无向路径，距离为两节点间实际距离
二，无向图：任意一节点仅和其相邻的最近两个节点有连通，该路径用灰色虚线表示（下图）
（点击“设置”－“使用路线图”来切换以上两种模式）
      深度优先遍历：
蓝色
采用递归的方法，使用邻接矩阵
在列出第n节点相邻的节点并一一入栈时，相邻最近的优先入栈
可以看出深度优先遍历的顺序是一直深入探索下去
可选起点，可选显示序号，右下角为其总路程长度
      广度优先遍历：
绿色
使用辅助队列、邻接矩阵
在列出第n节点相邻的节点并一一入队时，相邻最近的优先入队
可以看出广度优先遍历的顺序是按距离一层层探索出去
可选起点，可选显示序号，右下角为其总路程长度
      最小生成树：
红色
最小生成树：使用线把所有节点连接起来，且要求线段的总长度最短
采用克鲁斯卡尔（Kruskal）算法，邻接矩阵
使用一辅助数组记录节点的连通情况（记录连通图组，具体见源码中注释）
可选显示序号，右下角为其总路程长度
图的最短路径：
紫色
采用迪杰斯特拉（Dijkstra）算法，邻接矩阵
使用队列记录依次途经的路径
在这里要打开“使用路线图”，因若不打开，则为完全图，两点间直线距离最短，没意思
可选起点、终点，可选显示序号，右下角为其总路程长度