本文共 2064 字，大约阅读时间需要 6 分钟。
给定起点 找到从起点到各点的路径。
注意：此法只适用于简单路径（无环）
1 2
1 3 2 4 3 4这一组就含有环 不可以，因为 记录4号顶点父节点的时候 path[]只能记录最后访问到4的那个父节点
package Graph;import java.util.Iterator;import java.util.LinkedList;import java.util.List;import java.util.Scanner;import java.util.Stack;import javax.security.auth.x500.X500Principal;public class ShorPaths { private int []path;//记录路径 private boolean[] visit; private int s; private int v, e; List []map; public static void main(String[] args) { new ShorPaths().run(); } public void run() { Scanner in = new Scanner(System.in); v = in.nextInt(); e = in.nextInt(); map = new LinkedList[v]; for(int i = 0; i < v; i++ ) { map[i] = new LinkedList<>(); } for(int i = 0; i < e; i++) { int a = in.nextInt(); int b = in.nextInt(); map[a].add(b); map[b].add(a); } DepthFirstSearch(map, 0); printPath(); } public void printPath() { for(int i = 0; i < map.length; i++ ) { if(!visit[i])//判断是否有路径 continue; System.out.print(s+ " to " + i +": "); Stack stack = pathTo(i); boolean flag = true; while(!stack.isEmpty()) { if(flag) { System.out.print(stack.pop()); flag = false; } else System.out.print("-"+ stack.pop()); } System.out.println(); } } public void DepthFirstSearch(List[] map, int s) { path = new int[v]; visit = new boolean[v]; dfs(s); } public void dfs(int cur) { visit[cur] = true; for(int i = 0; i < map[cur].size(); i++ ) {//注意这里是map[cur].size()而不是map.length int v = map[cur].get(i); if(!visit[v]) { visit[v] = true; path[v] = cur; dfs(v); } } } public Stack pathTo(int v){ if(!visit[v]) return null; Stack stack = new Stack<>(); for(int x = v; x != s; x = path[x]) stack.push(x); stack.push(s);// Iterator it = stack.iterator();// while(it.hasNext()) {// System.out.print(it.next() + " ");// } return stack; }} 另一种递归打印 路径的方法 （数据大时候不要用）
public void print(int[]path, int v) { if(s == v) System.out.print(s); else { print(path, path[v]); System.out.print("-"+ v); } } 转载地址：http://zlimi.baihongyu.com/