有向图判断同层次问题
/** * 算法核心思想： * a的数据流必经过b的深刻含义为，a的数据流无论从哪条路走都必须经过b，这就要求a的相邻节点也具有该特性； * 同理将有向图反向，b的数据流也必经过a */public class SameLevel { //n为节点个数，e为有向边个数 private static int n,e; //有向图正向临接表 private static Map<Character,LinkedList<Character>> adjacencyMap = new HashMap<Character,LinkedList<Character>>(); //有向图反向临接表 private static Map<Character,LinkedList<Character>> adjacencyReverseMap = new HashMap<Character,LinkedList<Character>>(); /* * 创建正向与反向临接表 * 输入格式参考如下： * 4 4 //输入节点个数与有向边数 * a b c d //输入各个节点 * a b // 以下四行有输入的有向边 * a c * b d * c d * a d //输入需要判断层次的任意两个节点 */ public static boolean createGraph(Scanner sc){ n = sc.nextInt(); e = sc.nextInt(); if(n == 0 || e == 0) return false; for(int i=0;i<n;i++){ char c = sc.next().toCharArray()[0]; adjacencyMap.put(c,new LinkedList<Character>()); adjacencyReverseMap.put(c,new LinkedList<Character>()); } for(int i=0;i<e;i++){ char c = sc.next().toCharArray()[0],d = sc.next().toCharArray()[0]; LinkedList<Character> list = adjacencyMap.get(c), rlist = adjacencyReverseMap.get(d); list.addFirst(d); rlist.addFirst(c); } return true; } /* * 判断a是否从任意路径可达b */ public static boolean DFSTraverseAtoB(char a ,char b , boolean []visited){ if(a == b) return true; boolean ret = true; LinkedList<Character> adjacentList = adjacencyMap.get(a); for(char c : adjacentList){ Arrays.fill(visited,false); if(!DFS(c,b,visited) || !DFSTraverseAtoB(c,b,visited)){ ret = false; break; } } return ret; } /* * 深度优先遍历算法 */ public static boolean DFS(char a , char b , boolean[] visited){ if(a == b){ return true; } visited[a] = true; LinkedList<Character> adjacentList = adjacencyMap.get(a); for(char c : adjacentList){ if(!visited[c]){ if(DFS(c,b,visited)){ return true; } } } return false; } /* * 判断两个节点是否是同一层次 */ public static boolean isSameLevel(char a ,char b){ boolean ret = false,ret1 = false; if(!adjacencyMap.containsKey(a) || !adjacencyMap.containsKey(b)){ throw new RuntimeException("Node Doesn't exist!"); } boolean[] visited = new boolean[256]; ret = DFSTraverseAtoB(a ,b ,visited); adjacencyMap = adjacencyReverseMap; //有向图反向再判断一次 ret1 = DFSTraverseAtoB(b,a ,visited); return ret && ret1; } public static void main(String[]args){ Scanner sc = new Scanner(System.in); boolean created = createGraph(sc); if(!created){ throw new RuntimeException("Create graph failed!"); } Character a = sc.next().toCharArray()[0],b = sc.next().toCharArray()[0]; boolean ret = isSameLevel(a,b); System.out.println(ret); }}
?
?
?
?
?
