In the Algorithm Design Manual (2nd ed) pp 172 - 173, Skiena writes: As algorithm design paradigms go, a depth-first search isn't  particularly intimidating. It is surprisingly subtle, however  meaning that its correctness requires getting details right...In undirected graphs, each edge (x,y) sits in the adjacency lists of  vertex x and y... The labelling of edges as tree edges or back edges  occurs during the first time the edge is explored... But when we  encounter edge (x, y) from x, how can we tell if we have previously  traversed the edge from y? The issue is easy if vertex y is  undiscovered: (x,y) becomes a tree edge so this must be the first  time. The issue is also easy if y has not been completely processed;  since we explored the edge when we explored y this must be the second  time. But what if y is an ancestor of x, and thus in a discovered  state? Careful reflection will convince you that this must be our  first traversal unless y is the immediate ancestor of x--ie, (y,x)  is a tree edge. This can be established by testing if y == parent[x].I mostly find Skiena quite a clear and understandable writer, and I'm pretty sure I understand the business with only tree edges/back edges in a DFS on an undirected graph, and I still find that last paragraph confusing as hell. So I've taken Skiena's C implementation of adjacency-list based graphs + DFS and implemented them in Python 3. I'm particularly interested in commentary that might help illuminate what's Skiena's trying to get across on pp 172 - 173, as well as Py3k feedback (I've mostly worked in Py2.7 for the past few years), or if I'm made any errors. As Skiena goes on to say: I find the subtly of depth-first search-based algorithms kicks me in the head whenever I try to implement one. The test graph I'm using is based off of Skiena's diagram from p.171, but with zero-indexing:The only 3rd party library used is attrs. (Blame glyph)from enum import Enumimport attrfrom attr.validators import instance_of@attr.sclass EdgeNode:        An Edge & a Node.    The source node is the index of the head in the Graph's edges list.        y = attr.ib(instance_of(int))    weight = attr.ib(default=1)    next = attr.ib(default=None)    def __str__(self):        return f'EdgeNode(y={self.y}, w={self.weight})'    def __iter__(self):        yield self        while self.next:            yield self.next            self = self.next    def degree(self):        out = 0        while self.next:            out += 1            self = self.next        return out@attr.sclass Graph:         Based on Skiena's Adjacency List implementation.     A graph is a list of linked lists. Each component of a linked list          is an EdgeNode instance.         nodes = attr.ib(default=attr.Factory(list))    directed = attr.ib(instance_of(bool))    nedges = attr.ib(0)    def __str__(self):        out = []        for index, edgenode in enumerate(self.nodes):            out.append(f'{index}:\n')            while edgenode:                out.append(f'  {edgenode}\n')                edgenode = edgenode.next        return ''.join(out)    @property    def nnodes(self):        return len(self.nodes)    def add_edge(self, x, y, weight=1, directed=False):        while max(x, y) + 1 > len(self.nodes):            self.nodes.append(None)        edgenode = EdgeNode(y=y, weight=weight, next=self.nodes[x])        self.nodes[x] = edgenode        if directed:            self.nedges += 1        else:            self.add_edge(y, x, weight, directed=True)graph = Graph(directed=False)graph.add_edge(0, 5)graph.add_edge(0, 1)graph.add_edge(1, 4)graph.add_edge(1, 2)graph.add_edge(2, 3)graph.add_edge(3, 4)graph.add_edge(4, 0)assert graph.nnodes == 6assert graph.nedges == 7def DFS(graph, start):    class States(Enum):        undiscovered = 0        discovered = 1        processed = 2    time = 0    node_states = [States.undiscovered] * graph.nnodes    node_parents = [None] * graph.nnodes    entry_times = [0] * graph.nnodes    exit_times = [0] * graph.nnodes    def recurse(v):        nonlocal time        time += 1        node_states[v] = States.discovered        entry_times[v] = time        print(f'Processing node #{v:02}')        adjacent_nodes = graph.nodes[v]        for node in adjacent_nodes:            if node_states[node.y] is States.undiscovered:                node_parents[node.y] = v                print(f'    Processing edge ({v:02}, {node.y:02})')                recurse(node.y)            elif node_states[node.y] is States.discovered or graph.directed:                print(f'   Processing edge ({v:02}, {node.y:02})')        print(f'Leaving node #{v:02}')        time += 1        exit_times[v] = time        node_states[v] = States.processed    recurse(start)    print(f'Parents: {node_parents}\nEntry times: {entry_times}\nExit times{exit_times}')DFS(graph, 0)Also available as a gist.
Skiena's DFS on unweighted graphs, in Python 3, with adjacency-list implementation
python;python 3.x;graph;depth first search