iframe-proxy | Sunbelt Computer Software

History

50 lines (41 loc) · 1.38 KB

Raw

"""Non recursive implementation of a DFS algorithm."""

from __future__ import annotations

from typing import Set

def depth_first_search(graph: dict, start: str) -> Set[str]:

"""Depth First Search on Graph

:param graph: directed graph in dictionary format

:param start: starting vertex as a string

:returns: the trace of the search

>>> input_G = { "A": ["B", "C", "D"], "B": ["A", "D", "E"],

... "C": ["A", "F"], "D": ["B", "D"], "E": ["B", "F"],

... "F": ["C", "E", "G"], "G": ["F"] }

>>> output_G = list({'A', 'B', 'C', 'D', 'E', 'F', 'G'})

>>> all(x in output_G for x in list(depth_first_search(input_G, "A")))

True

>>> all(x in output_G for x in list(depth_first_search(input_G, "G")))

True

"""

explored, stack = set(start), [start]

while stack:

v = stack.pop()

explored.add(v)

# Differences from BFS:

# 1) pop last element instead of first one

# 2) add adjacent elements to stack without exploring them

for adj in reversed(graph[v]):

if adj not in explored:

stack.append(adj)

return explored

G = {

"A": ["B", "C", "D"],

"B": ["A", "D", "E"],

"C": ["A", "F"],

"D": ["B", "D"],

"E": ["B", "F"],

"F": ["C", "E", "G"],

"G": ["F"],

}

if __name__ == "__main__":

import doctest

doctest.testmod()

print(depth_first_search(G, "A"))

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

depth_first_search.py

Latest commit

History

depth_first_search.py

File metadata and controls