algorithm - Efficiently find the depth of a graph from every node -

-

i have problem find minimum possible depth of graph implies have find maximum depth each node , return least of them all. simple dfs each node trick when things crazy extremely large input, dfs becomes inefficient (time limit). tried keeping distance of each leaf node being explored in memory didn't much.

how efficiently find minimum depth of large graph. worthy of note graph in question has no cycle.

to find graph centre/center of undirected tree graph could:

  1. do dfs find list of leaf nodes o(n)
  2. remove these leaf nodes graph , note during deletion new nodes become leaf nodes
  3. repeat step 2 until graph deleted

the node/nodes deleted in last stage of algorithm graph centres of tree.

each node deleted once, whole process can done in o(n).


Comments

Post a Comment

Popular posts from this blog

Detect support for Shoutcast ICY MP3 without navigator.userAgent in Firefox? -

-
the current version of mozilla firefox 23.0.1, version not support play mp3 shoutcast streams tcp port different 80 (most common 8000 shoutcast 1.9.8). i use flash when mp3 support not available in html5 audio, way detect is: try{ var = document.createelement('audio'); r = !!(a.canplaytype && !!a.canplaytype("audio/mpeg; codecs=mp3").replace(/^no$/,'')) }catch(e){ r = false; } the support mp3 shoutcast streams in firefox added in version 24 . a.canplaytype("audio/mpeg; codecs=mp3") = in chrome , firefox, chrome support, firefox not support, due current code detect not work firefox. the current version of jquery support ie 6 1.10.2, version not has .browser i think "stylized" way testing features , not querying browsers / versions, notwithstanding here see hard not violate "principle". what "stylized" way of detect mp3 icy support without navigator.useragent in firefox? ther...
Read more

web - SVG not rendering properly in Firefox -

-
i have problem svg renderring in firefox. whilst works in safari, chrome or in ie, doesn't work in firefox. inspecting element seems layers there, background visible if it's z-index higher z-index of others. rendered in firefox: svg logo in firefox link original source file: svg file thanks help. ps: used sketch 3 export svg. if helps somehow. you're experiencing bug 995813 . i fixed bug time ago change still making way through release process example display correctly firefox 31 onwards released on 22 july 2014. in meantime if move fill="white" <mask> element child <use> element work around firefox bug.
Read more

java - JavaFX 2 slider labelFormatter not being used -

-
i have following code not label slider "foo50", etc... 1 expect setlabelformatter call, instead seems have no effect (the slider labelled 50, 100, etc , println's dont run). there missing? not implemented in default 2.2 skin? using oracle java 7 package javafxbugtest; import javafx.application.application; import javafx.scene.*; import javafx.scene.control.*; import javafx.stage.*; import javafx.util.stringconverter; public class javafxbugtest extends application { @override public void start(final stage primarystage) { slider cp = new slider(); cp.setlabelformatter(new stringconverter<double>() { @override public string tostring(double t) { system.out.println("nope?"); return "foo" + t.tostring(); } @override public double fromstring(string string) { system.out.println("he...
Read more