Microsoft Word - 문서2Do not modify Graph.java Task: 1. Implement topologicalOrdering1() in the starter code (DFS.java). This is the DFSbased algorithm for finding the topological...

Hi, I need help with this assignment. I want the same expert who worked on case116795.





Microsoft Word - 문서2 Do not modify Graph.java Task: 1. Implement topologicalOrdering1() in the starter code (DFS.java). This is the DFSbased algorith m for finding the topological ordering of a directed acyclic graph. Do not modify Graph.java. Use it from package idsa. l Input graph may not be a DAG. Your program should detect and output appropriate message. Practice Task (Optional) -> You don’t have to do it! 2. Implement topologicalOrdering2(g) in the starter code. In this algorithm, we identify a node with no incoming edges, and remove it and all its edges. Repeat this until the graph is em pty. 3. Implement connectedComponents() in the starter code. In this algorithm, use DFS to find th e number of connected components of a given undirected graph. Each node gets a cno. All nodes in the same connected component receive the same cno. PowerPoint Presentation DFS Sridhar Alagar CS 6301 IDSA DFS in a directed Graph 2 Use stack for DFS dfs(v){ if v is unmarked mark v for each (v, w) in G do dfs(w) } wfs(s){ put s into bag while bag not empty take v from bag if v is unmarked mark v for each (v, w) in G do put w in bag } DFS 3 Wrapper method to visit all nodes dfs(v){ mark v pre(v) for each (v, w) in G do if w is unmarked w.parent = v dfs(w) post(v) } dfsAll(G){ initialize(G) for each v in G do unmark v for each v in G do if v is unmarked dfs(v) } Preorder and postorder traversal of DFS Forest 4 dfs(v){ mark v pre(v) for each (v, w) in G do if v is unmarked w.parent = v dfs(w) post(v) } dfsAll(G){ initialize(G) for each v in G do unmark v for each v in G d0 if v is unmarked dfs(v) } initialize(G) clock = 0 pre(v) clock++ v.start = clock post(v) clock++ v.finish = clock Record when a node entered and left stack Recursion Stack – Time diagram 5 Stack – Time diagram 6 Stack – Time diagram 7 Stack – Time diagram 8 Stack – Time diagram 9 Stack – Time diagram 10 Stack – Time diagram 11 Stack – Time diagram 12 Stack – Time diagram 13 Stack – Time diagram 14 Stack – Time diagram 15 Stack – Time diagram 16 Stack – Time diagram 17 18 Preorder postorder Preorder and postorder traversal of DFS Forest pre(v) startList.add(v) post(v) finishList.add(v) Classifying Vertices • v is new if DFS(v) is not called • clock < v.start="" •="" v="" is="" active="" if="" dfs(v)="" is="" called="" but="" not="" returned="" •="" v.start=""><= clock="">< v.finish="" •="" v="" is="" finished="" if="" dfs(v)="" has="" returned="" •="" v.finish=""><= clock="" cs="" 6301="" idsa="" 19="" 20="" classify="" edges="" •="" u.start="">< v.start="">< v.finish="">< u.finish="" •="" v="" is="" reachable="" from="" u="" •="" u="" is="" an="" ancestor="" of="" v="" in="" dfs="" tree="" 21="" classify="" edges="" •="" consider="" u-="">v and suppose v is new when DFS(u) begins • u.start < v.start="">< v.finish="">< u.finish="" •="" if="" dfs(u)="" calls="" dfs(v)="" directly,="" then="" u-="">v is a tree edge • Otherwise u->v is a forward edge 22 Classify Edges • consider u->v and v is finished when DFS(u) begins • v.start < v.finish="">< u.start="">< u.finish,="" then="" u-="">v is a cross edge 23 Classify Edges • consider u->v and v is active when DFS(u) begins • v.start < u.start="">< u.finish="">< v.finish="" ,="" •="" u-="">v is a back edge Directed Acyclic Graph • Source vertices have no incoming edges • Sink vertices have no outgoing vertices • DAG has at least one source vertex and one sink vertex • Is G a DAG? CS 6301 IDSA 24 Is G a DAG? 25 What would you change to the code below? dfs(v){ mark v pre(v) for each (v, w) in G do if w is unmarked w.parent = v dfs(w) post(v) } dfsAll(G){ initialize(G) for each v in G do unmark v for each v in G d0 if v is unmarked dfs(v) } Is G a DAG? 26 A linear time algorithm: isDAG(v){ v.status = active for each (v, w) in G do if w.status is active return false else if w.status is new if (!isDAG(w)) return false v.status = finished return true } isDAGAll(G){ for each v in G do v.status = new for each v in G d0 if v.status is new if(!isDAG(v)) return false return true } Topological Ordering 27 • Informally, place all vertices in a horizontal line such that edges go only from left to right • Topological ordering of G is a total order ‹, on vertices such that • u ‹ v for every edge u->v • Topological ordering is only possible if G is a DAG Topological Sort 28 Topological Sort 29 Topological Sort Algorithm 30 dfs(v){ mark v pre(v) for each (v, w) in G do if v is unmarked w.parent = v dfs(w) post(v) } dfsAll(G){ initialize(G) for each v in G do unmark v for each v in G d0 if v is unmarked dfs(v) } initialize(G) pre(v) post(v) topList.addFirst(v) Reverse of post order traversal Problem of the day 31 Slide 1: DFS Slide 2: DFS in a directed Graph Slide 3: DFS Slide 4: Preorder and postorder traversal of DFS Forest Slide 5: Recursion Stack – Time diagram Slide 6: Stack – Time diagram Slide 7: Stack – Time diagram Slide 8: Stack – Time diagram Slide 9: Stack – Time diagram Slide 10: Stack – Time diagram Slide 11: Stack – Time diagram Slide 12: Stack – Time diagram Slide 13: Stack – Time diagram Slide 14: Stack – Time diagram Slide 15: Stack – Time diagram Slide 16: Stack – Time diagram Slide 17: Stack – Time diagram Slide 18 Slide 19: Classifying Vertices Slide 20 Slide 21 Slide 22 Slide 23 Slide 24: Directed Acyclic Graph Slide 25: Is G a DAG? Slide 26: Is G a DAG? Slide 27: Topological Ordering Slide 28: Topological Sort Slide 29: Topological Sort Slide 30: Topological Sort Algorithm Slide 31: Problem of the day PowerPoint Presentation DFS Sridhar Alagar CS 6301 IDSA DFS in a directed Graph 2 Use stack for DFS dfs(v){ if v is unmarked mark v for each (v, w) in G do dfs(w) } wfs(s){ put s into bag while bag not empty take v from bag if v is unmarked mark v for each (v, w) in G do put w in bag } DFS 3 Wrapper method to visit all nodes dfs(v){ mark v pre(v) for each (v, w) in G do if w is unmarked w.parent = v dfs(w) post(v) } dfsAll(G){ initialize(G) for each v in G do unmark v for each v in G do if v is unmarked dfs(v) } Preorder and postorder traversal of DFS Forest 4 dfs(v){ mark v pre(v) for each (v, w) in G do if v is unmarked w.parent = v dfs(w) post(v) } dfsAll(G){ initialize(G) for each v in G do unmark v for each v in G d0 if v is unmarked dfs(v) } initialize(G) clock = 0 pre(v) clock++ v.start = clock post(v) clock++ v.finish = clock Record when a node entered and left stack Recursion Stack – Time diagram 5 Stack – Time diagram 6 Stack – Time diagram 7 Stack – Time diagram 8 Stack – Time diagram 9 Stack – Time diagram 10 Stack – Time diagram 11 Stack – Time diagram 12 Stack – Time diagram 13 Stack – Time diagram 14 Stack – Time diagram 15 Stack – Time diagram 16 Stack – Time diagram 17 18 Preorder postorder Preorder and postorder traversal of DFS Forest pre(v) startList.add(v) post(v) finishList.add(v) Classifying Vertices • v is new if DFS(v) is not called • clock < v.start="" •="" v="" is="" active="" if="" dfs(v)="" is="" called="" but="" not="" returned="" •="" v.start=""><= clock="">< v.finish="" •="" v="" is="" finished="" if="" dfs(v)="" has="" returned="" •="" v.finish=""><= clock="" cs="" 6301="" idsa="" 19="" 20="" classify="" edges="" •="" u.start="">< v.start="">< v.finish="">< u.finish="" •="" v="" is="" reachable="" from="" u="" •="" u="" is="" an="" ancestor="" of="" v="" in="" dfs="" tree="" 21="" classify="" edges="" •="" consider="" u-="">v and suppose v is new when DFS(u) begins • u.start < v.start="">< v.finish="">< u.finish="" •="" if="" dfs(u)="" calls="" dfs(v)="" directly,="" then="" u-="">v is a tree edge • Otherwise u->v is a forward edge 22 Classify Edges • consider u->v and v is finished when DFS(u) begins • v.start < v.finish="">< u.start="">< u.finish,="" then="" u-="">v is a cross edge 23 Classify Edges • consider u->v and v is active when DFS(u) begins • v.start < u.start="">< u.finish="">< v.finish="" ,="" •="" u-="">v is a back edge Directed Acyclic Graph • Source vertices have no incoming edges • Sink vertices have no outgoing vertices • DAG has at least one source vertex and one sink vertex • Is G a DAG? CS 6301 IDSA 24 Is G a DAG? 25 What would you change to the code below? dfs(v){ mark v pre(v) for each (v, w) in G do if w is unmarked w.parent = v dfs(w) post(v) } dfsAll(G){ initialize(G) for each v in G do unmark v for each v in G d0 if v is unmarked dfs(v) } Is G a DAG? 26 A linear time algorithm: isDAG(v){ v.status = active for each (v, w) in G do if w.status is active return false else if w.status is new if (!isDAG(w)) return false v.status = finished return true } isDAGAll(G){ for each v in G do v.status = new for each v in G d0 if v.status is new if(!isDAG(v)) return false return true } Topological Ordering 27 • Informally, place all vertices in a horizontal line such that edges go only from left to right • Topological ordering of G is a total order ‹, on vertices such that • u ‹ v for every edge u->v • Topological ordering is only possible if G is a DAG Topological Sort 28 Topological Sort 29 Topological Sort Algorithm 30 dfs(v){ mark v pre(v) for each (v, w) in G do if v is unmarked w.parent = v dfs(w) post(v) } dfsAll(G){ initialize(G) for each v in G do unmark v for each v in G d0 if v is unmarked dfs(v) } initialize(G) pre(v) post(v) topList.addFirst(v) Reverse of post order traversal Problem of the day 31 Slide 1: DFS Slide 2: DFS in a directed Graph Slide 3: DFS Slide 4: Preorder and postorder traversal of DFS Forest Slide 5: Recursion Stack – Time diagram Slide 6: Stack – Time diagram Slide 7: Stack – Time diagram Slide 8: Stack – Time diagram Slide 9: Stack – Time diagram Slide 10: Stack – Time diagram Slide 11: Stack – Time diagram Slide 12: Stack – Time diagram Slide 13: Stack – Time diagram Slide 14: Stack – Time diagram Slide 15: Stack – Time diagram Slide 16: Stack – Time diagram Slide 17: Stack – Time diagram Slide 18 Slide 19: Classifying Vertices Slide 20 Slide 21 Slide 22 Slide 23 Slide 24: Directed Acyclic Graph Slide 25: Is G a DAG? Slide 26: Is G a DAG? Slide 27: Topological Ordering Slide 28: Topological Sort Slide 29: Topological Sort Slide 30: Topological Sort Algorithm Slide 31: Problem of the day