# Source code for tryalgo.dfs

```#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Depth-first search - DFS

jill-jênn vie et christoph durr - 2015-2019
"""

from typing import List, Optional
from . graph import Graph

# snip{ dfs-recursive

[docs]
def dfs_recursive(graph: Graph, node: int, seen: List[bool]) -> None:
"""DFS, detect connected component, recursive implementation

:param graph: directed graph in listlist or listdict format
:param int node: to start graph exploration
:param boolean-table seen: will be set true for the connected component
containing node.
:complexity: `O(|V|+|E|)`
"""
seen[node] = True
for neighbor in graph[node]:
if not seen[neighbor]:
dfs_recursive(graph, neighbor, seen)

# snip}

# snip{ dfs-iterative

[docs]
def dfs_iterative(graph: Graph, start: int, seen: List[bool]) -> None:
"""DFS, detect connected component, iterative implementation

:param graph: directed graph in listlist or listdict format
:param int node: to start graph exploration
:param boolean-table seen: will be set true for the connected component
containing node.
:complexity: `O(|V|+|E|)`
"""
to_visit = [start]
while to_visit:
node = to_visit.pop()   # exploring in top-down order of stack
if not seen[node]:      # hence the use of reversed
to_visit.extend(reversed(graph[node]))
seen[node] = True   # vertex can be multiple times on stack

# snip}

# snip{ dfs-tree

[docs]
def dfs_tree(graph: Graph, start: int=0) -> List[Optional[int]]:
"""DFS, build DFS tree in unweighted graph

:param graph: directed graph in listlist or listdict format
:param int start: source vertex
:returns: precedence table
:complexity: `O(|V|+|E|)`
"""
to_visit = [start]
prec: List[Optional[int]] = [None] * len(graph)
while to_visit:              # an empty queue equals False
node = to_visit.pop()
for neighbor in graph[node]:
if prec[neighbor] is None:
prec[neighbor] = node
to_visit.append(neighbor)
return prec

# snip}

[docs]
def dfs_grid_recursive(grid: List[List[str]], i: int, j: int, mark: str='X', free: str='.') -> None:
"""DFS on a grid, mark connected component, recursive version

:param grid: matrix, 4-neighborhood
:param i,j: cell in this matrix, start of DFS exploration
:param free: symbol for walkable cells
:param mark: symbol to overwrite visited vertices
:complexity: linear
"""
height = len(grid)
width = len(grid[0])
grid[i][j] = mark              # mark path
for ni, nj in [(i + 1, j), (i, j + 1),
(i - 1, j), (i, j - 1)]:
if 0 <= ni < height and 0 <= nj < width:
if grid[ni][nj] == free:
dfs_grid(grid, ni, nj)

# snip{ dfs-grid

[docs]
def dfs_grid(grid, i, j, mark='X', free: str='.') -> None:
"""DFS on a grid, mark connected component, iterative version

:param grid: matrix, 4-neighborhood
:param i,j: cell in this matrix, start of DFS exploration
:param free: symbol for walkable cells
:param mark: symbol to overwrite visited vertices
:complexity: linear
"""
height = len(grid)
width = len(grid[0])
to_visit = [(i, j)]
grid[i][j] = mark
while to_visit:
i1, j1 = to_visit.pop()
for i2, j2 in [(i1 + 1, j1), (i1, j1 + 1),
(i1 - 1, j1), (i1, j1 - 1)]:
if (0 <= i2 < height and 0 <= j2 < width and
grid[i2][j2] == free):
grid[i2][j2] = mark  # mark path
to_visit.append((i2, j2))

# snip}

# pylint: disable=too-many-nested-blocks, no-else-return

[docs]
def find_cycle(graph: Graph) -> Optional[List[int]]:
"""find a cycle in an undirected graph

:param graph: undirected graph in listlist or listdict format
:returns: list of vertices in a cycle or None
:complexity: `O(|V|+|E|)`
"""
n = len(graph)
prec: List[Optional[int]] = [None] * n  # ancestor marks for visited vertices
for start in range(n):         # for each connected component
if prec[start] is None:    # unvisited vertex
S: List[int] = [start]            # start new DFS
prec[start] = start       # mark root (not necessary for this algorithm)
while S:
u = S.pop()
for v in graph[u]:  # for all neighbors
if v != prec[u]:  # except arcs to father in DFS tree
if prec[v] is not None: # v was already visited
cycle = [v, u]  # cycle found, (u,v) back edge
while u not in (prec[v], prec[u]):  # directed
assert u is not None
u = prec[u]  # climb up the tree
cycle.append(u)
return cycle
else:
prec[v] = u  # v is new vertex in tree
S.append(v)
return None

[docs]
def is_bipartite(G: Graph) -> bool:
""" Checks whether a given graph is bipartite.

This is done by a graph traversal, assigning alternating colors.
Once an edge with identicial endpoint colors is detected
we know graph is not bipartite.

:param G: graph
:returns: True if G is bipartite
:complexity: linear
"""
n = len(G)
color = [0] * n     # 0=not visited, +1,-1=colors
for u in range(n):  # for each connected component
if color[u] == 0:
Q = [u]     # initiate a graph traversal
color[u] = 1
while Q:
v = Q.pop()
for w in G[v]:
if color[w] == color[v]:
return False    # odd cycle detected
if color[w] == 0:
color[w] = -color[v]    # opposite color
Q.append(w)
return True

```