华为笔试5.20有向图环路—Java
有向图寻找环路(图+dfs)
如有错误,欢迎指出
edges记录邻接矩阵
使用used数组记录当前节点是否被使用过
使用instack数组记录目前节点是否在搜索路径中
stack记录搜索路径
题目描述
给定一个有向图,假定最多10个节点,节点编号依次为A~J,如果A节点到B节点之间有通路则描述为A->B,多条边的描述之间以分号隔开,给定一个有向图,求该有向图中的所有环路,环路以节点编号的最小的节点开始输出,假定一个有向图最多一个环路,如果没有环路则输出空字符串“-”。输入为连接链表。
输入描述:
输入为连接链表字符串,如 :A->B;B->D;C->B;C->E;D->C
输出描述:
环路节点组成的字符串,如:输出字符串BDC,标识B->D->C->B组成环路
示例1输入输出示例仅供调试,后台判题数据一般不包含示例
输入
A->B;B->D;C->B;C->E;D->C
输出
BDC
package test; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; import java.util.Stack; public class Two { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.next(); // 检查输入合法性 boolean matches = str.matches("[A-J]\\-\\>[A-J](\\;[A-J]\\-\\>[A-J]){0,9}"); if (matches) { String[] paths = str.split(";"); // 创建邻接矩阵 int[][] edges = new int[paths.length][paths.length]; for (String path : paths) { String[] bet = path.split("->"); int u = bet[0].charAt(0) - 'A'; int v = bet[1].charAt(0) - 'A'; edges[u][v] = 1; } // 定义数组boolean[],记录结点是否被访问 boolean[] used = new boolean[edges.length]; List<Integer> cycle = new ArrayList<Integer>(); helper(edges, cycle); if(cycle.size()==0) { System.out.println("-"); return; } for (Integer integer : cycle) { System.out.print((char)('A'+integer)); } } else { System.out.println("-"); return; } in.close(); } private static void helper(int[][] edges, List<Integer> cycle) { // TODO Auto-generated method stub boolean[] used = new boolean[edges.length]; boolean[] instack = new boolean[edges.length]; Stack<Integer> stack = new Stack<Integer>(); for (int i = 0; i < used.length; i++) { if (!used[i]) { dfs(i, used, instack, stack, cycle, edges); } } } private static void dfs(int i, boolean[] used, boolean[] instack, Stack<Integer> stack, List<Integer> cycle, int[][] edges) { // TODO Auto-generated method stub used[i] = true; if (instack[i]) { int count = stack.indexOf(i); Stack<Integer> tem = new Stack<Integer>(); tem.addAll(stack); while (tem.size() > count) { cycle.add(tem.pop()); } Collections.reverse(cycle); return; } instack[i] = true; stack.push(i); for (int j = 0; j < edges[i].length; j++) { if(edges[i][j]!=1) continue; dfs(j, used, instack, stack, cycle, edges); } // 回溯 stack.pop(); instack[i] = false; } }