/** * Title: 图的遍历、最小生成树、最短路径 * * * Description: * * 采用邻接矩阵做为图存储结构,有权无向图,不相连的值为 -1 * * 图的遍历中深度遍历采用递归方法,广度遍历使用辅助队列 * * 最小生成树采用克鲁斯卡尔(Kruskal)算法,使用一数组记录节点的连通情况 * * 图的最短路径采用迪杰斯特拉(Dijkstra)算法,使用队列记录依次途经的路径 * * 修改: * 深度、广度遍历中 在列出第n节点相邻的节点并一一入栈/队时,相邻最近的优先入栈/队 * * * * Website: www.hartech.cn * Page: http://www.hartech.cn/blog/blogview.asp?logID=88 * * Date: 2006-09-08 */public class Graph { // 图邻接矩阵 private static int[][] arcs; // 节点数 private static int num; // 记录是否访问过 private static boolean[] hasVisit; // 记录访问过的前一个节点,用于统计线路总长度 static int pre; // 深度优先遍历,给出图邻接矩阵和开始遍历的节点 public static void traverse_DFS(int[][] arcs_in, int begin) { pre = begin; if (arcs_in == null || arcs_in.length == 0 || arcs_in.length != arcs_in[0].length || begin <0) { System.err.println("wrong arcs[][] or begin!"); return; } arcs = arcs_in; num = arcs.length; hasVisit = new boolean[num]; DFS(begin); } private static void DFS(int begin) { hasVisit[begin] = true; Main.Q_DFS.enQueue(begin); Main.length_DFS += Main.arcs[pre][begin]; pre = begin; int min, n = 0; for (int i = 1; i
Title: 图的遍历、最小生成树、最短路径
Description: * * 采用邻接矩阵做为图存储结构,有权无向图,不相连的值为 -1 * * 图的遍历中深度遍历采用递归方法,广度遍历使用辅助队列 * * 最小生成树采用克鲁斯卡尔(Kruskal)算法,使用一数组记录节点的连通情况 * * 图的最短路径采用迪杰斯特拉(Dijkstra)算法,使用队列记录依次途经的路径 * * 修改: * 深度、广度遍历中 在列出第n节点相邻的节点并一一入栈/队时,相邻最近的优先入栈/队 * *
Website: www.hartech.cn
Page: http://www.hartech.cn/blog/blogview.asp?logID=88
Date: 2006-09-08