图论——单源路径问题

文章目录

图论——单源路径问题 问题分析

对于本小节，我们只讨论简单无向无权图的单源路径问题。

单源路径是指从某个给定顶点出发找到一条路径到其他顶点，其实在dfs或者bfs的过程中我们已经遍历了每个顶点，想求单源路径问题只不过要在遍历过程记录一些额外的信息，根据这些信息可以反推出路径。

我们定义一个数组pre，pre存储的就是这些额外的信息

pre[i] = j的语义是顶点i 是从 顶点 j 过来的， 比如pre[1] = 0的语义是顶点1是从顶点0过来的

有了这个数组，我们试着来模拟一遍dfs

初始化

pre初始化为-1，代表所有的顶点都未被访问，源点=0, pre[0] = 0

0——>1,pre[1] = 0

1——>3,pre[3] = 1

3——>2,pre[2] = 3

dfs回退到0，dfs完毕

pre数组如下：

pre[0] = 0
pre[1] = 0  代表0->1这条边
pre[2] = 3 代表3->2这条边
pre[3] = 1 代表1->3这条边求顶点0到顶点2的路径：
0->1
1->3
3->2
这三条路径合起来就是了

代码

graph.txt

7 6
0 1
0 2
1 3
2 6
2 3
1 4

public class SingleSourcePath {private UndirectedGraph graph;private int source;//源点private int[] dfsPre;//上一个顶点的数组private int[] bfsPre;public SingleSourcePath(UndirectedGraph graph,int source){graph.validateVertex(source);this.source = source;this.graph = graph;dfsPre = new int[graph.vertexNum()];for(int i=0;i<dfsPre.length;i++){//-1表示顶点i还未访问dfsPre[i] = -1;}bfsPre = new int[graph.vertexNum()];for(int i=0;i<bfsPre.length;i++){//-1表示顶点i还未访问bfsPre[i] = -1;}dfs(source,source);bfs(source);}private void bfs(int v){Queue<Integer> queue = new LinkedList<>();queue.offer(v);while(!queue.isEmpty()){int w = queue.poll();for(int u:graph.adj(w)){if(bfsPre[u]==-1){//代表w到u有边bfsPre[u] = w;queue.offer(u);}}}}/*** parent-> v 有路径* @param v* @param parent*/private void dfs(int v,int parent){//parent到v有边dfsPre[v] = parent;for(int w:graph.adj(v)) {if(dfsPre[w]==-1){dfs(w,v);}}}public boolean dfsIsConnectedTo(int t){graph.validateVertex(t);return dfsPre[t]!=-1;}public boolean bfsIsConnectedTo(int t){graph.validateVertex(t);return bfsPre[t]!=-1;}/*** 返回s->t的路径* @param t* @return*/public Iterable<Integer> dfsPath(int t){List<Integer> list = new ArrayList<>();if(!dfsIsConnectedTo(t)){return list;}while(t!=source){list.add(0,t);t = dfsPre[t];}list.add(0,source);return list;}public Iterable<Integer> bfsPath(int t){List<Integer> list = new ArrayList<>();if(!bfsIsConnectedTo(t)){return list;}while(t!=source){list.add(0,t);t = bfsPre[t];}list.add(0,source);return list;}public static void main(String[] args) {UndirectedGraph graph = new UndirectedGraph("graph.txt");System.out.println(graph);SingleSourcePath path = new SingleSourcePath(graph,0);System.out.println(path.dfsPath(1));System.out.println(path.dfsPath(2));System.out.println(path.dfsPath(3));System.out.println(path.dfsPath(4));System.out.println(path.dfsPath(5));System.out.println(path.dfsPath(6));System.out.println();System.out.println(path.bfsPath(1));System.out.println(path.bfsPath(2));System.out.println(path.bfsPath(3));System.out.println(path.bfsPath(4));System.out.println(path.bfsPath(5));System.out.println(path.bfsPath(6));}
}

建图类

public class UndirectedGraph {private int V;//顶点数private int E;//边数private TreeSet<Integer>[] adj;//邻接表，TreeSet数组存储public UndirectedGraph(String filename){File file = new File(filename);try(Scanner scanner = new Scanner(file)){V = scanner.nextInt();//顶点数if(V<=0) throw new RuntimeException("顶点个数必须大于0");adj = new TreeSet[V];for(int i=0;i<V;i++){adj[i] = new TreeSet<>();}E = scanner.nextInt();//边数if(E<0) throw new RuntimeException("边数不能为负数");for(int i=0;i<E;i++){int a = scanner.nextInt();validateVertex(a);int b = scanner.nextInt();validateVertex(b);//自环边检测if(a==b){throw new RuntimeException("简单图不能包含自环边");}//平行边检测if(adj[a].contains(b)){throw new RuntimeException("简单图不能包含平行边");}adj[a].add(b);adj[b].add(a);}}catch (IOException e){e.printStackTrace();}}public void validateVertex(int v){if(v<0||v>=V){throw new RuntimeException("顶点下标溢出");}}public int vertexNum(){return V;}public int edgeNum(){return E;}public boolean hasEdge(int v,int w){validateVertex(v);validateVertex(w);return adj[v].contains(w);}//邻接顶点public Iterable<Integer> adj(int v){validateVertex(v);return adj[v];}//度public int degree(int v){validateVertex(v);return adj[v].size();}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append(String.format("V = %d,E = %d\n",V,E));for(int i=0;i<adj.length;i++){sb.append(i+":");for (Iterator<Integer> it = adj[i].iterator(); it.hasNext(); ) {sb.append(it.next()+" ");}sb.append("\n");}return sb.toString();}public static void main(String[] args) {UndirectedGraph graph = new UndirectedGraph("graph.txt");System.out.println(graph);}
}

指定终点代码

public class SingleSourceTargetPath {private UndirectedGraph graph;private int source;//源点private int target;//终点private int[] dfsPre;//上一个顶点的数组private int[] bfsPre;//上一个顶点的数组public SingleSourceTargetPath(UndirectedGraph graph, int source, int target){graph.validateVertex(source);graph.validateVertex(target);this.source = source;this.target = target;this.graph = graph;dfsPre = new int[graph.vertexNum()];for(int i=0;i<dfsPre.length;i++){dfsPre[i] = -1;}dfs(source,source);bfsPre = new int[graph.vertexNum()];for(int i=0;i<bfsPre.length;i++){bfsPre[i] = -1;}bfs(source);}private void bfs(int v){Queue<Integer> queue = new LinkedList<>();queue.offer(v);while(!queue.isEmpty()){int w = queue.poll();for(int u:graph.adj(w)){if(bfsPre[u]==-1){bfsPre[u] = w;if(u==target){return;}queue.offer(u);}}}}/*** parent-> v 有路径* @param v* @param parent*/private boolean dfs(int v,int parent){dfsPre[v] = parent;//走到终点了，返回if(v==target){return true;}for(int w:graph.adj(v)) {if(dfsPre[w]==-1){if(dfs(w,v)){return true;}}}return false;}public boolean bfsIsConnected(){return bfsPre[target]!=-1;}public boolean dfsIsConnected(){return dfsPre[target]!=-1;}/*** 返回s->t的路径* @return*/public Iterable<Integer> dfsPath(){List<Integer> list = new ArrayList<>();if(!dfsIsConnected()){return list;}int cur = target;while(cur!=source){list.add(0,cur);cur = dfsPre[cur];}list.add(0,source);return list;}public Iterable<Integer> bfsPath(){List<Integer> list = new ArrayList<>();if(!bfsIsConnected()){return list;}int cur = target;while(cur!=source){list.add(0,cur);cur = bfsPre[cur];}list.add(0,source);return list;}public static void main(String[] args) {UndirectedGraph graph = new UndirectedGraph("graph.txt");System.out.println(graph);SingleSourceTargetPath path = new SingleSourceTargetPath(graph,0,6);System.out.println(path.dfsPath());System.out.println(path.bfsPath());}
}