algorithm - Complexity of non-recursiveDFS code -

-

i think complexity of code is: time : o (v) : v vertex space: o (v) : v vertex 

public void dfs() {         stack<integer> stack = new stack<integer>();         stack.add(source);          while (!stack.empty()) {             int vertex = stack.pop();             system.out.println(" print v: " + vertex);             (int v : graph.adj(vertex)) {                 if (!visited[v]) {                     visited[v] = true;                     stack.add(v);                     edgeto[v] = vertex;                }             }         }     }

please correct me if wrong

assuming graph.adj() produce bounded number of vertices (maybe one), right.

however, if depends in way on total number of vertices present in system, not. if dependency linear, algorithm o(n^2).

generalizing, if f(n) average number of graph.adj() per vertex, answer o(n*f(n)).


Comments

Post a Comment

Popular posts from this blog

java - How to Configure JAXRS and Spring With Annotations -

-
i working on little spring web service project. here example route: package com.example.api; import javax.ws.rs.get; import javax.ws.rs.path; import javax.ws.rs.produces; import javax.ws.rs.pathparam; import javax.ws.rs.ext.provider; import javax.ws.rs.core.mediatype; @provider public class webserviceroutes { @get @path("/hello") public string health() { return "hello"; } } then in spring configuration class: package com.example.api; import org.springframework.context.annotation.bean; import org.springframework.context.annotation.configuration; @configuration public class springcontextconfiguration { @bean( destroymethod = "shutdown" ) public springbus cxf() { return new springbus(); } @bean public webserviceroutes webserviceroutes() { return new webserviceroutes(); } } and in web.xml: <?xml version="1.0" encoding="utf-8"?> <web-app version=...
Read more

visual studio - TFS will not accept changes I've made to a Java project -

-
i using tfs's team explorer manage visual studio projects. recently, i've created new java project (not in visual studio) manually added tfs using source control control explorer in visual studio. after added java project tfs, made changes , bug fixes. then, went visual studio , opened source control explorer check in changes, tfs thinks no changes made. it seems needed check out project before making changes. guess erroneously expected tfs track automatically, okay. so, using source control explorer in tfs, checked out project, , tried check in pending changes. when tried check in, got following message: all of changes either unmodified files or locks. changes have been undone server. is there way convince server indeed project has changed? how can check in changes have made? thank help.
Read more

php - Create image in codeigniter on the fly -

-
i want create image in codeigniter in simple php using gd functions. have tried following method in controller function image(){ $my_img = imagecreate( 200, 80 ); $background = imagecolorallocate( $my_img, 0, 0, 255 ); $text_colour = imagecolorallocate( $my_img, 255, 255, 0 ); $line_colour = imagecolorallocate( $my_img, 128, 255, 0 ); imagestring( $my_img, 4, 30, 25, "thesitewizard.com", $text_colour ); imagesetthickness ( $my_img, 5 ); imageline( $my_img, 30, 45, 165, 45, $line_colour ); //$this->output->set_content_type('image/png'); header( "content-type: image/png" ); imagepng( $my_img ); imagecolordeallocate( $line_color ); imagecolordeallocate( $text_color ); imagecolordeallocate( $background ); imagedestroy( $my_img ); } if write code in simple php can see in url http://www.domain.com/image.php if run in codeignite...
Read more