深度优先，广度优先，dijkstra最短路径问题。

注：返回相应路径代码仍未鲁邦。

讯享网

package com.interview.graph; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; //时间复杂度 // 邻接表：深度优先和广度优先 O（V+E） // 邻接矩阵：深度优先和广度优先 O（V2） // 空间复杂度 // 均为O(V) public class Graph { public static void main(String args[]) { int n=8,e=9;//分别代表结点个数和边的数目 String labels[]={"1","2","3","4","5","6","7","8"};//结点的标识 AMWGraph graph=new AMWGraph(n); for(String label:labels) { graph.insertVertex(label);//插入结点 } //插入九条边 graph.insertEdge(0, 1, 1); graph.insertEdge(0, 2, 1); graph.insertEdge(1, 3, 1); graph.insertEdge(1, 4, 1); graph.insertEdge(3, 7, 1); graph.insertEdge(4, 7, 1); graph.insertEdge(2, 5, 1); graph.insertEdge(2, 6, 1); graph.insertEdge(5, 6, 1); graph.insertEdge(1, 0, 1); graph.insertEdge(2, 0, 1); graph.insertEdge(3, 1, 1); graph.insertEdge(4, 1, 1); graph.insertEdge(7, 3, 1); graph.insertEdge(7, 4, 1); graph.insertEdge(6, 2, 1); graph.insertEdge(5, 2, 1); graph.insertEdge(6, 5, 1); System.out.println("深度优先搜索序列为："); graph.depthFirstSearch(); System.out.println(); System.out.println("广度优先搜索序列为："); graph.broadFirstSearch(); System.out.println(); MatrixUDG a = new MatrixUDG(); int[] prev = new int[3]; int[] dist = new int[3]; a.dijkstra( 2, prev, dist); } } / * @description 邻接矩阵模型类 * @author beanlam * @time 2015.4.17 */ class AMWGraph { private ArrayList vertexList;//存储点的链表 private int[][] edges;//邻接矩阵，用来存储边 private int numOfEdges;//边的数目 private boolean[] isVisited; public AMWGraph(int n) { //初始化矩阵，一维数组，和边的数目 edges=new int[n][n]; vertexList=new ArrayList(n); numOfEdges=0; isVisited = new boolean[n]; } //得到结点的个数 public int getNumOfVertex() { return vertexList.size(); } //得到边的数目 public int getNumOfEdges() { return numOfEdges; } //返回结点i的数据 public Object getValueByIndex(int i) { return vertexList.get(i); } //返回v1,v2的权值 public int getWeight(int v1,int v2) { return edges[v1][v2]; } //插入结点 public void insertVertex(Object vertex) { vertexList.add(vertexList.size(),vertex); } //插入边 public void insertEdge(int v1,int v2,int weight) { edges[v1][v2]=weight; numOfEdges++; } //删除结点 public void deleteEdge(int v1,int v2) { edges[v1][v2]=0; numOfEdges--; } //得到第一个邻接结点的下标 public int getFirstNeighbor(int index) { for(int j=0;j<vertexList.size();j++) { if (edges[index][j]>0) { return j; } } return -1; } //根据前一个邻接结点的下标来取得下一个邻接结点 public int getNextNeighbor(int v1,int v2) { for (int j=v2+1;j<vertexList.size();j++) { if (edges[v1][j]>0) { return j; } } return -1; } //私有函数，深度优先遍历 private void depthFirstSearch(boolean[] isVisited,int i) { //首先访问该结点，在控制台打印出来 System.out.print(getValueByIndex(i)+" "); //置该结点为已访问 isVisited[i]=true; int w=getFirstNeighbor(i);// while (w!=-1) { if (!isVisited[w]) { depthFirstSearch(isVisited,w); } w=getNextNeighbor(i, w); } } //对外公开函数，深度优先遍历，与其同名私有函数属于方法重载 public void depthFirstSearch() { isVisited = new boolean[getNumOfVertex()]; for(int i=0;i<getNumOfVertex();i++) { //因为对于非连通图来说，并不是通过一个结点就一定可以遍历所有结点的。 if (!isVisited[i]) { depthFirstSearch(isVisited,i); } } } //私有函数，广度优先遍历 private void broadFirstSearch(boolean[] isVisited,int i) { int u,w; Queue<Integer> queue=new LinkedList<>(); //访问结点i System.out.print(getValueByIndex(i)+" "); isVisited[i]=true; //结点入队列 queue.offer(i); while (!queue.isEmpty()) { u = queue.poll(); w=getFirstNeighbor(u); while(w!=-1) { if(!isVisited[w]) { //访问该结点 System.out.print(getValueByIndex(w)+" "); //标记已被访问 isVisited[w]=true; //入队列 queue.offer(w); } //寻找下一个邻接结点 w=getNextNeighbor(u, w); } } } //对外公开函数，广度优先遍历 public void broadFirstSearch() { isVisited = new boolean[getNumOfVertex()]; for(int i=0;i<getNumOfVertex();i++) { if(!isVisited[i]) { broadFirstSearch(isVisited, i); } } } / * dijkstra * 求解带权最短路径 * 如果有负值不适合 */ public void dijkstra(){ System.out.println(); } } class MatrixUDG { //O（v2） private int mEdgNum; // 边的数量 private char[] mVexs; // 顶点集合 private int[][] mMatrix; // 邻接矩阵 private static final int INF = Integer.MAX_VALUE; // 最大值 MatrixUDG(){ this.mEdgNum = 3; mVexs = new char[]{'0','1','2'}; mMatrix = new int[][]{ 
  
    
  {Integer.MAX_VALUE,1,3},{Integer.MAX_VALUE,Integer.MAX_VALUE,1},{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE}}; } /* * Dijkstra最短路径。 * 即，统计图中"顶点vs"到其它各个顶点的最短路径。 * * 参数说明： * vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。 * prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。 * dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。 */ public void dijkstra(int vs, int[] prev, int[] dist) { // flag[i]=true表示"顶点vs"到"顶点i"的最短路径已成功获取 boolean[] flag = new boolean[mVexs.length]; // 初始化 for (int i = 0; i < mVexs.length; i++) { flag[i] = false; // 顶点i的最短路径还没获取到。 prev[i] = 0; // 顶点i的前驱顶点为0。 dist[i] = mMatrix[vs][i]; // 顶点i的最短路径为"顶点vs"到"顶点i"的权。 } // 对"顶点vs"自身进行初始化 flag[vs] = true; dist[vs] = 0; // 遍历mVexs.length-1次；每次找出一个顶点的最短路径。 int k=0; for (int i = 1; i < mVexs.length; i++) { // 寻找当前最小的路径； // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。 int min = INF; for (int j = 0; j < mVexs.length; j++) { if (flag[j]==false && dist[j]<min) {//不存在边的话，长度为无穷 min = dist[j]; k = j; } } // 标记"顶点k"为已经获取到最短路径 if(min == INF){ break; } flag[k] = true; // 修正当前最短路径和前驱顶点 // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。 for (int j = 0; j < mVexs.length; j++) { int tmp = (mMatrix[k][j]==INF ? INF : (min + mMatrix[k][j])); if (flag[j]==false && (tmp<dist[j]) ) { dist[j] = tmp; prev[j] = k; } } } // 打印dijkstra最短路径的结果 System.out.printf("dijkstra(%c): \n", mVexs[vs]); for (int i=0; i < mVexs.length; i++) { if(dist[i]==INF){ continue; } System.out.printf(" shortest(%c, %c)=%d\n", mVexs[vs], mVexs[i], dist[i]); // int j = i; // System.out.print(j+" "); // while (j!=vs){ // System.out.print(prev[j]+ " "); // j = prev[j]; // } // System.out.println(); } } }