Depth first search code in java

depth first search binary tree and depth first search definition
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 4.2 DIRECTED GRAPHS introduction ‣ digraph API ‣ digraph search ‣ Algorithms FOUR TH EDITION topological sort ‣ strong components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu4.2 DIRECTED GRAPHS introduction ‣ digraph API ‣ digraph search ‣ Algorithms topological sort ‣ strong components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduDirected graphs Digraph. Set of vertices connected pairwise by directed edges. outdegree = 4 indegree = 2 0 0 6 8 7 directed path 2 2 1 1 from 0 to 2 3 3 9 9 10 10 directed cycle 4 4 5 5 11 11 12 12 3Road network To see all the details that are visible on the screen,use the Address Holland Tunnel "Print" link next to the map. New York, NY 10013 Vertex = intersection; edge = one-way street. ©2008 Google - Map data ©2008 Sanborn, NAVTEQ™ - Terms of Use 4Political blogosphere graph Vertex = political blog; edge = link. The Political Blogosphere and the 2004 U.S. Election: Divided They Blog, Adamic and Glance, 2005 Figure 1: Community structure of political blogs (expanded set), shown using utilizing a GEM layout 11 in the GUESS3 visualization and analysis tool. The colors reflect political orientation, 5 red for conservative, and blue for liberal. Orange links go from liberal to conservative, and purple ones from conservative to liberal. The size of each blog reflects the number of other blogs that link to it. longer existed, or had moved to a different location. When looking at the front page of a blog we did not make a distinction between blog references made in blogrolls (blogroll links) from those made in posts (post citations). This had the disadvantage of not differentiating between blogs that were actively mentioned inapostonthatday, fromblogrolllinksthatremainstaticovermanyweeks10. Since posts usually contain sparse references to other blogs, and blogrolls usually contain dozens of blogs, we assumed that the network obtained by crawling the front page of each blog would strongly reflect blogroll links. 479 blogs had blogrolls through blogrolling.com, while many others simply maintained a list of links to their favorite blogs. We did not include blogrolls placed on a secondary page. We constructed a citation network by identifying whether a URL present on the page of one blog references another political blog. We called a link found anywhere on a blog’s page, a “page link” to distinguishitfroma“postcitation”,alinktoanotherblogthatoccursstrictlywithinapost. Figure1 shows the unmistakable division between the liberal and conservative political (blogo)spheres. In fact, 91% of the links originating within either the conservative or liberal communities stay within that community. An effect that may not be as apparent from the visualization is that even though we started with a balanced set of blogs, conservative blogs show a greater tendency to link. 84% of conservative blogs link to at least one other blog, and 82% receive a link. In contrast, 74% of liberal blogs link to another blog, while only 67% are linked to by another blog. So overall, we see a slightly higher tendency for conservative blogs to link. Liberal blogs linked to 13.6 blogs on average, while conservative blogs linked to an average of 15.1, and this difference is almost entirely due to the higher proportion of liberal blogs with no links at all. Although liberal blogs may not link as generously on average, the most popular liberal blogs, Daily Kos and Eschaton (atrios.blogspot.com), had 338 and 264 links from our single-day snapshot 4Overnight interbank loan graph Vertex = bank; edge = overnight loan. GSCC GWCC GIN GOUT DC Tendril "%& '( &)&%+ ,-). -&/01%2 ,1% 3&4/&56&% 7'8 799:; = ? "-/ 0&2+ A1&A/&) A1541-&-/8 The Topology of the Federal Funds Market, Bech and Atalay, 2008 B ? )".A1&A/&) A1541-&-/8 3 ? "-/ ./%1-+ A1&A/&) A1541-&-/8 CD ? "-/ "-EA1541-&-/8 FGH ? "-/ 1/E A1541-&-/; F- /I". ) /I&%& 0&%& JK -1)&. "- /I& 38 L9L -1)&. "- /I& CD8 :K 6 -1)&. "- FGH8 J9 -1)&. "- /I& /&-)%"+. -) 7 -1)&. "- )".A1&A/&) A1541-&-/; "%&%'( HI&-1)&.1,-&/01%2A-6&4%/"/"1-&)"-/1A1++&A/"1-1,)".M1"-/.&/.A++&))".A1&A/&) A1541-&-/.8"" "; HI& -1)&. 0"/I"- &AI )".A1&A/&) A1541-&-/ )1 -1/ IN& +"-2. /1 1% ,%15 -1)&. "- - 1/I&% A1541-&-/8 ";&;8 """" " "% "& ' ", % ( % ; HI& A1541-&-/ 0"/I /I& +%&./ -56&% 1, -1)&. ". %&,&%%&) /1 . /I& )%& +",-. /'"/&"0 /'12'"& O=P; C- 1/I&% 01%).8 /I& = ". /I& +%&./ A1541-&-/ 1, /I& -&/01%2 "- 0I"AI ++ -1)&. A1&A/ /1 &AI 1/I&% N" -)"%&A/&) 4/I.; HI& %&5"-"- )".A1&A/&) A1541-&-/. OB.P %& .5++&% A1541-&-/. ,1% 0I"AI /I& .5& ". /%&; C- &54"%"A+ ./)"&. /I& = ". 1,/&- ,1-) /1 6& .&N&%+ 1%)&%. 1, 5-"/)& +%&% /I- - 1, /I& B. O.&& Q%1)&% "& -3 O7999PP; HI& = A1-."./. 1, )%& 4&5')-. /'"/&"0 /'12'"& O3P8 )%& '6&7/'12'"& OFGHP8 )%& %7/'12'"& OCDP -) &"05%-4 O.&& "%& 'P; HI& 3 A154%".&. ++ -1)&. /I/ A- %&AI &N&% 1/I&% -1)& "- /I& 3 /I%1I )"%&A/&) 4/I; R -1)& ". "- /I& FGH ", "/ I. 4/I ,%15 /I& 3 6/ -1/ /1 /I& 3; C- A1-/%./8 -1)& ". "- /I& CD ", "/ I. 4/I /1 /I& 3 6/ -1/ ,%15 "/; R S9 -1)& ". "- /&-)%"+ ", "/ )1&. -1/ %&.")& 1- )"%&A/&) 4/I /1 1% ,%15 /I& 3; %4/644%'( C-/I&-&/01%21,45&-/..&-/1N&%&)0"%&-+T&)631%5U2" "& -3 O799:P8 /I&3 ". /I& +%&./ A1541-&-/; F- N&%&8 +51./ %&' 1, /I& -1)&. "- /I/ -&/01%2 6&+1- /1 /I& 3; C- A1-/%./8 /I& 3 ". 5AI .5++&% ,1% /I& ,&)&%+ ,-). -&/01%2; C- 799:8 1-+ (&') (' 1, /I& -1)&. 6&+1- /1 /I". A1541-&-/; Q ,% /I& +%&./ A1541-&-/ ". /I& CD; C- 799:8 )%'))' 1, /I& -1)&. 0&%& "- /I". A1541-&-/; HI& FGH A1-/"-&) (') +' 1, ++ -1)&. 4&% )8 0I"+& /I&%& 0&%& (+') ,' 1, SS /I& -1)&. +1A/&) "- /I& /&-)%"+.; V&.. /I- -') (' 1, /I& -1)&. 0&%& "- /I& %&5"-"- )".A1&A/&) A1541-&-/. O.&& H6+& JP; S9 HI& /&-)%"+. 5 +.1 6& )"W&%&-/"/&) "-/1 /I%&& .6A1541-&-/.( .&/ 1, -1)&. /I/ %& 1- 4/I &5-/"- ,%15 CD8 .&/ 1, -1)&. /I/ %& 1- 4/I +&)"- /1 FGH8 -) .&/ 1, -1)&. /I/ %& 1- 4/I /I/ 6&"-. "- CD -) &-). "- FGH; SS " 1, -1)&. 0&%& "- X,%15ECDY /&-)%"+.8 % 1, -1)&. 0&%& "- /I& X/1EFGHY /&-)%"+. -) "& 1, -1)&. 0&%& "- X/6&.Y ,%15 CD /1 FGH; S7Uber taxi graph Vertex = taxi pickup; edge = taxi ride. http://blog.uber.com/2012/01/09/uberdata-san-franciscomics/ 7Implication graph Vertex = variable; edge = logical implication. if x5 is true, then x0 is true x x 2 0 x x x 6 4 3 x x x x 5 1 1 5 x x x 3 4 6 x x 0 2 8Combinational circuit Vertex = logical gate; edge = wire. 9WordNet graph Vertex = synset; edge = hypernym relationship. event happening occurrence occurrent natural_event miracle act human_ac on human_ac vity change altera on modi ca on miracle group_ac on damage harm .. impairment transi on increase forfeit forfeiture ac on resistance opposi on transgression leap jump salta on jump leap change demo on varia on mo on movement move locomo on travel descent run running jump parachu ng http://wordnet.princeton.edu dash sprint 10 Digraph applications digraph vertex directed edge street intersection one-way street transportation web page hyperlink web species predator-prey relationship food web synset hypernym WordNet task precedence constraint scheduling bank transaction financial person placed call cell phone person infection infectious disease board position legal move game journal article citation citation object pointer object graph class inherits from inheritance hierarchy code block jump control flow 11Some digraph problems problem description s→t path Is there a path from s to t ? shortest s→t path What is the shortest path from s to t ? directed cycle Is there a directed cycle in the graph ? topological sort Can the digraph be drawn so that all edges point upwards? strong connectivity Is there a directed path between all pairs of vertices ? transitive closure For which vertices v and w is there a directed path from v to w ? PageRank What is the importance of a web page ? 124.2 DIRECTED GRAPHS introduction ‣ digraph API ‣ digraph search ‣ Algorithms topological sort ‣ strong components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduDigraph API Almost identical to Graph API. public class Digraph public class Digraph Digraph(int V) Digraph(int V) create an empty digraph with V vertices Digraph(In in) Digraph(In in) create a digraph from input stream void addEdge(int v, int w) addEdge(int v, int w) add a directed edge v→w IterableInteger adj(int v) adj(int v) vertices pointing from v int V() V() number of vertices int E() E() number of edges Digraph reverse() reverse() reverse of this digraph String toString() toString() string representation 14Digraph API % java Digraph tinyDG.txt tinyDG.txt 5 1 0-5 V 13 E 0-1 22 4 2 2-0 adj 2 3 0 3 2-3 3 2 0 3-5 6 0 5 2 1 0 1 3-2 2 0 2 4-3 3 2 11 12 3 4-2 12 9 4 9 10 5-4 4 9 11 5 ⋮ 7 9 9 4 8 0 6 10 12 11-4 11 4 7 11-12 4 3 6 9 8 12-9 3 5 9 6 8 6 8 6 10 5 4 ⋮ 11 10 11 0 5 6 4 12 6 9 12 In in = new In(args0); read digraph from 7 6 input stream Digraph G = new Digraph(in); 4 12 9 for (int v = 0; v G.V(); v++) print out each for (int w : G.adj(v)) edge (once) StdOut.println(v + "-" + w); 15Digraph representation: adjacency lists Maintain vertex-indexed array of lists. tinyDG.txt 5 1 V 13 E 22 tinyDG.txt 4 2 5 1 V adj 2 3 0 3 13 E 3 2 0 22 6 0 1 5 2 0 1 4 2 2 0 2 adj 2 3 0 3 3 2 11 12 3 3 2 12 9 0 4 9 10 4 6 0 9 11 5 2 1 5 0 1 7 9 9 4 8 0 6 10 12 2 0 2 11 4 7 3 2 11 12 4 3 6 9 3 8 12 9 3 5 9 6 8 4 9 10 6 4 8 6 10 9 11 5 4 5 11 11 10 0 5 7 9 9 4 8 0 6 4 6 12 10 12 6 9 12 11 4 7 7 6 6 9 4 3 4 12 8 3 5 9 9 6 8 16 6 8 6 10 5 4 11 10 11 0 5 6 4 12 6 9 12 7 6 4 12 9Digraph representations In practice. Use adjacency-lists representation. Algorithms based on iterating over vertices pointing from v. Real-world digraphs tend to be sparse. huge number of vertices, small average vertex degree insert edge edge from iterate over vertices representation space from v to w v to w? pointing from v? list of edges E 1 E E 2 † adjacency matrix V 1 1 V adjacency lists E + V 1 outdegree(v) outdegree(v) † disallows parallel edges 17Adjacency-lists graph representation (review): Java implementation public class Graph private final int V; adjacency lists private final BagInteger adj; public Graph(int V) create empty graph with V vertices this.V = V; adj = (BagInteger) new BagV; for (int v = 0; v V; v++) adjv = new BagInteger(); add edge v–w public void addEdge(int v, int w) adjv.add(w); adjw.add(v); iterator for vertices public IterableInteger adj(int v) adjacent to v return adjv; 18Adjacency-lists digraph representation: Java implementation public class Digraph private final int V; adjacency lists private final BagInteger adj; public Digraph(int V) create empty digraph with V vertices this.V = V; adj = (BagInteger) new BagV; for (int v = 0; v V; v++) adjv = new BagInteger(); add edge v→w public void addEdge(int v, int w) adjv.add(w); iterator for vertices public IterableInteger adj(int v) pointing from v return adjv; 194.2 DIRECTED GRAPHS introduction ‣ digraph API ‣ digraph search ‣ Algorithms topological sort ‣ strong components ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu