StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POGraph data structure questions
text
Body
copied!<p>I have problem designing pseudo-code for these problems. It is not an assignment problem. All I know about them is they have something to do with GRAPH data structure.</p> <ol> <li><p>Describe an <code>O(n+m)-time</code> algorithm for computing all the connected components of an undirected graph <code>G</code> with n vertices and m edges. </p> <p>(I am guessing this has something to do with traversal Breadth First Search (BFS), but correct me if I am wrong.).</p> <pre><code>Input Graph G Output sequence of connected vertices with edges List = empty list for all u in G.vertices setLabel(u, UNEXPLORED) for all e in G.edges setLabel(e, UNEXPLORED) For all v in G.vertices if getLabel(v) = UNEXPLORED BFS (G,v,List) BFS(G,s,List) Object A = vertex1, vertex2, edge L0 = new empty sequence L0.addLast(s) setLabel(s,VISITED) i=0 while Li is not Empty L(i+1) = new empty sequence for all v in L(i).elements for all incidentEdges(v) if getLabel(e) = UNEXPLORED w = opposite(v,e) if getLabel(w) = UNEXPLORED setLabel(e,DISCOVERY) setLabel(w,VISITED) setVertex1(A,v) setVertex2(A,w) setEdge(A,e) List.addLast(A) L(i+1).addLast(w) else setLabel(e,CROSS) i = i + 1 </code></pre></li> <li><p>Say that an n-vertex directed acyclic graph G is compact.<br> If there is some way of numbering the vertices of G with integers from 0 to n-1 such that G contains the edge (i,j) if and only if i < j, for all (i , j) in [0,n-1], Give an O(n^2)-time algorithm for detecting if G is compact. </p> <p>(Again, I am guessing this has something to do with topological ordering, but I am not sure how to implement it).</p></li> <li><p>Say a connected graph G is biconnected if it contains no vertex whose removal would divide G into 2 or more connected components. </p> <p>Give an O(n+m)-time algorithm for adding at most n edges to a connected graph G, with n>= 3 vertices and m>=(n-1) edges, to guarantee that G is biconnected. (Probably spanning forest?).</p></li> </ol>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload