Is something missing in this EXPLORE algorithm?

Question

It took me about a week to understand how does it works, but still, I'm wondering if it actually works!

I. The algorithm EXPLORE

EXPLORE (S:sommet, D:following vertices of vertex X, visited:TAB)
var LIST;
i,j:vertices
visited[S] ←true;
LIST ←{S};
WHILE LIST ≠ 0
    selectionner i ∈ LIST
    IF ∃ j ∈ D[i] , not visited[j]
      visited[j]←true;
    ELSE LIST←LIST - {i}

II. running the algorithm

Then I tried on this Graph:

array of the following vertex of each vertex:

\begin{array}{|l|cr|} x & \Gamma^+(x)\\ \hline a & b,c,d\\ b & d,e\\ c & d,f \\ e & d,h \\ f & g,i \\ g & h, e \\ h & \emptyset\\ i & g,h \\ \end{array}

M: the visited tab L: the given list, which is empty in the beginning

Explore (a,$\Gamma$,M)

M$\leftarrow${a}

L$\leftarrow${a}

$\Gamma(a) ∩ (X \backslash M)=bcd \ne0$

list $ \ \ \ \ \ \ \ $notvisited

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b}$ why do we add b to L??

$\Gamma(b) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,d}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b,d}$ why do we add b to L??

$$...$$

$\Gamma(e) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b,d,f,g,h}$ That seems normal on the aglorithm, it corresponds to

Else LIST = LIST - i

$$...$$

Until

$\Gamma(d)$

$L\leftarrow a$

which leads to the components we didn't searched for:

$\Gamma(a) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,c,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,c}$ Still, wher the hell does this e comes in the algorithm?

$\Gamma(c) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,c,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a}$ I'm okay with its disparition

$\Gamma(a) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ L\leftarrow {\emptyset}$ I'm okay with its disparition

III. My ideas to make it works

if ever it doesn't work!

I wonder if something is not lacking in the algorithm, if we shouldn't add an Explore within the 'if' loop.

EXPLORE (S:sommet,  Γ, visited)
var LIST;
i,j:vertices
visited[S] ←true;
LIST ←{S};
WHILE LISTE ≠ 0
    selectionner i ∈ LISTE
    IF ∃ j ∈ D[i] , not visited[j]
      visited[j]←true;
      **EXPLORE(j,Γ,visited)**
    ELSE LISTE←LISTE - {i}

Answer 1

This might be a bit too much, but I tried the best I could to condense it. Unfortunately, Java doesn't allow one to write concise code... So, here's breadth-first and depth-first traversal of a graph (I used JGraphT) library for graph implementation. This should better illustrate the idea.

package tld.se.doodles;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DefaultDirectedGraph;

public class GraphSearch {

    public static void main(String ...args) {
        DefaultDirectedGraph<Integer, DefaultEdge> graph =
                new DefaultDirectedGraph<>(DefaultEdge.class);
        int[][] vertices = {
            {1, 2}, {1, 3}, {2, 1}, {2, 3},
            {3, 5}, {3, 6}, {3, 4}, {4, 7},
            {5, 2}, {5, 6}, {6, 3}, {6, 7}
        };
        Arrays.stream(vertices)
                .forEach(pair -> {
                        graph.addVertex(pair[0]);
                        graph.addVertex(pair[1]);
                        graph.addEdge(pair[0], pair[1]);
                    });
        depthFirstTraversal(graph);
        breadthFirstTraversal(graph);
    }

    private static void depthFirstTraversal(
        DefaultDirectedGraph<Integer, DefaultEdge> graph) {
        System.out.println("Depth-first traversal");
        HashSet<Integer> cache = new HashSet<>();
        Integer start = graph.vertexSet().stream().findFirst().get();
        dftHashed(start, graph, cache);
    }

    private static void dftHashed(
        Integer from, DefaultDirectedGraph graph, HashSet cache) {
        if (!cache.contains(from)) {
            cache.add(from);
            System.out.format("Visiting: %d%n", from);
            graph.<DefaultEdge>edgesOf(from).stream()
                    .forEach(edge ->
                             dftHashed((Integer)graph.getEdgeTarget(edge),
                                       graph, cache));
        }
    }

    private static void breadthFirstTraversal(
        DefaultDirectedGraph<Integer, DefaultEdge> graph) {
        System.out.println("Breadth-first traversal");
        HashSet<Integer> cache = new HashSet<>();
        Integer start = graph.vertexSet().stream().findFirst().get();
        HashSet<Integer> firstGen = new HashSet<>();
        firstGen.add(start);
        bftHashed(firstGen, graph, cache);
    }

    private static void bftHashed(
        HashSet previous, DefaultDirectedGraph graph, HashSet cache) {
        cache.addAll(previous);
        HashSet<Integer> next = (HashSet<Integer>)previous.stream()
                .flatMap(vertex -> {
                        System.out.format("Visiting: %d%n", vertex);
                        return graph.<DefaultEdge>edgesOf(vertex)
                            .stream().map(graph::getEdgeTarget);
                    })
                 .collect(Collectors.toCollection(HashSet::new));
        next.removeAll(cache);
        if (!next.isEmpty()) bftHashed(next, graph, cache);
    }
}