Space complexity of undirected graph

Question

I still continue to work on complexity, for the following algorithm I would like to know:

The space complexity
How can we show that $G$ contains a cycle if and only if there is a point $u$ and an edge $(u,v)$ around $u$ such that the explorer leaving $u$ by the edge $(u,v)$ does not return to $u$ by $(u,v)$.

Algorithm to detect if an undirected graph $G = (V, E)$ has a cycle :

Imagine that $V = \{1 ...|V|\}$ (in other words that the vertices are numbered from $1$ to $|V|$ ). An explorer plants a flag on point $1$ and then moves on the graph according to the following principle.

For each vertex $u \in V$ the different edges $(u,v)$ around the point $u$ can be ordered according to the size of $v$. So we can talk about the ith edge around $u$. . Note that if $(u,v)$ is the ith edge around $u$ it is possible that $(v,u)$ is not the ith edge around from $v$.
If the explorer reaches the point $u$ of degree $k$ using the ith edge around $u$ then it starts from $u$ using the $(i + 1)$ th edge around from $u$. If $i = k$ then the explorer starts from the first edge around $u$.

As a first attempt, the explorer leaves point $1$ using the first edge around $1$. If it returns to point $1$ by a different edge then he concludes that $G$ contains a cycle.

If on the other hand it returns to point $1$ to across the same edge, then it begins its exploration again, starting by the second edge of point $1$, then the third edge and so on.

If he has exhausted all edges around $1$ and has always returned to $1$ by the same edge, so he plants his flag on point $2$ and so on.

The space complexity of the algorithm described (more or less explicitly) here — jenny forock, Apr 11 '20 at 13:53
In my opinion we are not limited to the notation of the size of $v$. We can call the size of $v$ for example $|v|$. I do not know if I have answered your question. — jenny forock, Apr 11 '20 at 15:15
Sorry if I didn't understand your question. Here the size of $v$ does not indicate so we can choose it arbitrarily — jenny forock, Apr 11 '20 at 15:48
This should be said. Usually you speak of a weight, not a size. — , Apr 11 '20 at 16:25

score 0 · Accepted Answer · answered Apr 11 '20 at 16:29

If I am right, the algorithm is made of straight loops, and requires sorting around every vertex. But nothing mandates to store the sorting order, so the whole algorithm can be implemented in constant space $O(1)$.

Space complexity of undirected graph

1 Answers1