1
$\begingroup$

question is: given an unwighted nondirected graph G=(V,E) portrayed as an adjacency list, a special arc is defined as an arc (u,v) where both u and v has the same distance from source vertex s.

i need to give an algorithm to find all of the special arcs for a given s node.

the teacher's solution is: run BFS from s and save distances from s in every node. then, go over all of the nodes and for every node, check if 1 of the neighbors has same distance.

they claim its complexity is O(|V|+|E|) .. i think it is not.. if all nodes are connected to all nodes then for every node we check we go through all of the nodes so isn't it O(|V|^2)?

$\endgroup$

2 Answers 2

2
$\begingroup$

Run BFS from source vertex $s$ to find length of shortest path from $s$ to all other vertices in $O(V+E)$.

After than, traverse all edges $(u,v)$, let $d[u]$ be shortest distance of vertex $u$ from $s$, if $d[u]=d[v]$ then report that edge as a special arc. We traverse each edge one time and checking whether end points of edge $(u,v)$ have the same distance from source or not, it's obvious that can be done in $O(1)$.

So the total running time will be $O(V+E)$.

$\endgroup$
0
$\begingroup$

If you have a clique then the complexity is $O(|V|^2)$ as you claim, but $|E| \in \Theta(|V|^2)$ so $O(|V|^2) = O(|E|)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.