I read and read articles on this issue, and in no way can I understand what the result should be.
I thought that this algorithm should produce a sequence of vertices starting from a given one, such as to go around the entire graph (to visit each vertex once). And, actually, the teacher wants the same from me.
But apparently this is something else?
For example, here in the article ( Search in width ), with the input data "2" we get the result "2 3 4 1" (while on the graph there is no path from 4 to 1).
In general, please explain?

2 answers 2

We did something like this on the discrete: In the queue we wrote down the first point, then went in alphabetical order to all available sides and wrote down the points in the queue. When the paths from this point came to an end, we crossed it out and went on to the one that is next in line.
In this case (see figure), we write "a", then we write "b", "d" "l", the paths from "a" are over, we cross out "a". We turn to "b", there are no paths from it - we delete it, go to "d", from it we get into "f", "g" - we write it down. From the "d" the path is over - we delete, go to l, etc.
Note to the picture:
In the drawing error, when I did this task, I forgot the English alphabet and found that k comes earlier than j. In fact, they just need to swap. Dashed lines marked paths that we do not pass because they will lead to the point we have already passed.
The bold line indicates the path traveled during the walk.
Bold, dashed lines and crossed out letters appeared in the process of a detour, they were not in the initial task.

alt text

    In width:

    1. Choose the starting point.
    2. Then by turns you check all vertices (descendants) connected to it.
    3. When they are finished, you take one of the tested peaks (descendants) for the initial one.

    In depth:

    1. Choose the starting point.

    2. Then you check the top (descendant) connected to it and immediately make it a new main top.

    3. If a verified vertex does not have one more connection (with a descendant), return to the previous vertex (ancestor) and look for an unchecked connection with its descendants, if there is no such connection, then back again (to the ancestor).