🐍
My Docs
PYTHONNOTES
PYTHONNOTES
  • Home
  • Downloads & Misc-Assets
  • README
  • Navigation
  • Curriculum
    • Outline
      • General Content
      • Python-Data-Structures-Unit
    • wk17
      • Outline-w17
      • homework
      • D1-Module 01 - Python I
        • Configuring Ubuntu for Python Web Development
        • Install Python
      • D2- Module 02 - Python II
      • D3- Module 03 - Python III
      • D4-Module 04 - Python IV
    • wk18
      • Outline-W-18
      • D1- Module 01 - Number Bases and Character Encoding
      • D2- Module 02 - Hash Tables I
        • Hash Table / Hash Map In Python:
        • Hash Table Use Cases
        • Practice
      • D3-Module 03 - Hash Tables II
      • D4- Module 04 - Searching and Recursion
    • wk19
      • Outline-W-19
      • D1- Module 01 - Linked Lists
        • Homework
          • Helpful Resource
      • D2- Module 02 - Queues and Stacks
      • D3- Module 03 - Binary Search Trees
        • BST Definition:
      • D4- Module 04 - Tree Traversal
        • Tree Traversals (Inorder, Preorder and Postorder)
    • wk20
      • Outline-W-20
      • D1-Graphs I
      • D2-Graphs 2
      • DFS
      • D4
  • Utilities
    • Utilites
      • Python Libraries
      • YouTube
      • Code Lab Notebook Embeds From Lecture
    • Code lab Notebooks
    • Repl.IT
      • Trinket
  • Abstract Data Structures
    • Algorithms
      • Algo-Resources
        • List-Of-Solutions-To-Common-Interview-Questions
      • Dijkstra's algorithm
      • Calculate a Factorial With Python - Iterative and Recursive
      • DFS
      • BFS
        • BFS Examples
      • Palendrome
    • Data Structures Overview
      • General Data Structures Notes
        • DS-Explained-Simple
      • Untitled
      • Algorithms
      • Dictionary
    • Abstract Data Structures:
      • Array
        • Extra-Array
        • Array Practice
      • Binary Search
      • Binary Tree
        • Binary Tree Explained
        • Find the maximum path sum between two leaves of a binary tree
      • Binary Search Tree
        • BST Explained
        • BST Insert
        • BST-Largest-Sub-Tree
      • Exotic
        • Tire
        • Dynamic Programming
      • Graphs
        • Overflow Practice Problems
        • Graphs Explained
        • Earliest Ancestor
        • _Mini Graph-Projects
          • # Social Graph
          • number of 1 islands
          • Searching and Generating Graphs
        • Graph FAQ
          • Graph DFS
        • Connected Components
        • Randomness
        • Graph BFS
        • Topological Sort
      • Hash Table
        • Hashmap or Hash tables
        • Hash Table and HashMap in Python
      • Heap
        • Heap Examples
      • String
      • Map
        • Examples
      • Queue
        • Queue Continued...
        • Queue Sandbox
        • Dequeue
      • Tree
        • In Order Traversal
        • Tree Equal ?
        • Ternary-search-trees
        • Red_Black Tree
        • Tree Mirror:
        • Tree Traversal
      • Recursion
        • Recursion Explained
          • Recursion Examples
      • Linked List
        • Linked List Background
        • Double Linked List
        • List Example
        • Examples (LL) continued
        • List Operations
      • Set
        • Set
        • Set Intersection Union
        • Disjoint Set
      • Sorting
        • In JavaScript
        • Merge Sort
        • Iterative Sorting
        • Recursive Sorting
        • Graph Topological Sort
        • SelectionSort
        • Quick Sort
        • Merge Sort
        • Insertion Sort
      • Stack
        • Stack Continued
        • Stack Part 3
      • Searching
        • Binary Search
        • Searching & Sorting Computational Complexity (JS)
  • practice
    • GCA Sprint Prep:
      • Practice Problems
      • Code Signal CGA Sprint Resources
      • CGA-Sprint Prep
    • Supplemental Practice:
      • Practice
      • JavaScript Algorithms
      • Industry Standard Algorithms
        • Interview Practice Resources
        • Write a Program to Find the Maximum Depth or Height of a Tree
      • Random Examples
      • Prompts
      • JS_BASICS
  • Resources
    • Python Cheat Sheet
      • Cheatsheet-v2
      • List Of Python Cheat Sheets
    • Youtube
    • PDF Downloads
    • Intro 2 Python
    • Dictionaries
      • Dictionaries Continued
    • Python VS JavaScript
    • Misc. Resources
    • Things To Internalize:
      • Functions
    • Intro To Python w Jupyter Notebooks
    • Calculating Big O
    • Useful Links
      • Awesome Python
      • My-Links
      • Beginners Guide To Python
  • Docs
    • Docs
      • Strings
        • Strings Continued
      • Touple
      • Values Expressions & Statments
      • Dictionaries, sets, files, and modules
        • Modules
      • Built-in Types
      • Built In Functions
        • Zip Function
      • Functions
      • Classes and objects
        • Inheritance
        • Classes
          • Python Objects & Classes
          • index
      • Dictionaries
      • Conditionals and loops
      • Lists
        • Reverse A List
        • Python Data Structures
        • More On Lists
        • Examples
          • More-Examples
        • List Compehensions
      • Basic Syntax
      • String-Methods
    • Queue & Stacks
  • quick-reference
    • My Medium Articles
    • Free Python Books
    • WHY Python?
    • Debugging
    • Python Snippets
    • Python3 Regex
    • Python Module Index:
      • Requests Module
    • Creating Python Modules
    • Useful Info
    • Python Glossary
    • Python Snippets
  • MISC
    • Built-in Methods & Functions
    • Data Structures Types
    • Math
    • Unsorted Examples
    • Outline
    • About Python
      • Python VS JavaScript
      • Python Modules & Python Packages
      • Misc
      • Python's Default Argument Values and Lists
      • SCRAP
  • Interview Prep
    • Interview Resources
      • By Example
        • Algo-Prep
      • Permutation
      • How to Write an Effective Resume of Python Developer
      • Interview Checklist
      • 150 Practice Problems & Solutions
  • Installations Setup & Env
    • python-setup
    • Installing Python Modules
    • Set Up Virtual Enviornment
  • Aux-Exploration
    • Related Studies
      • Self-Organizing Maps: Theory and Implementation in Python with NumPy
      • List Directory Contents
      • Employee Manager
      • OS Module
      • server-side-scripting
      • Web Scraping
      • Reading and Writing to text files in Python
      • General Data Structures
      • Touple
      • How to round Python values to whole numbers?
      • Python Array Module
      • Data Structures In JavaScript
      • Dunder Methods
      • Python GitHub API
      • JS-Event Loop
      • JavaScript Event Loop
      • Manipulating Files & Folders
  • experiments
    • Untitled
Powered by GitBook
On this page
  • Depth First Search (DFS)
  • Objective
  • Overview
  • Applications of DFS
  • Coloring Vertexes
  • Recursion
  • Pseudocode for DFS
  • Implementation:
  1. Abstract Data Structures
  2. Abstract Data Structures:
  3. Graphs
  4. Graph FAQ

Graph DFS

PreviousGraph FAQNextConnected Components

Last updated 3 years ago

Depth First Search (DFS)

Objective

  • Learn about one of the more famous graph algorithms

  • Learn uses of DFS

Overview

When searching a graph, one of the approaches is called depth first search. This "dives" "down" the graph as far as it can before needing to backtrack and explore another branch.

The algorithm never attempts to explore a vert that it either has explored or is exploring.

For example, when starting from the upper left, the numbers on this graph show a vertex visitation order in a DFS:

The bold lines show with edges were followed. (The thin edges were not followed since their destination nodes had already been visited.)

(Of course, the exact order will vary depending on which branches get taken first and which vertex is the starting vertex.)

Applications of DFS

  • Path finding

  • Detecting cycles in graphs

  • Solving and generating mazes

Coloring Vertexes

As the graph is explored, it's useful to color verts as you arrive at them and as you leave them behind as "already searched".

Commonly, unvisited verts are white, verts whose neighbors are being explored are gray, and verts with no unexplored neighbors are black.

Recursion

Since we want to pursue leads in the graph as far as we can, and then "back up" to an earlier branch point to explore that way, recursion is a good approach to help "remember" where we left off.

Looking at it with pseudocode to make the recursion more apparent:

explore(graph) {
    visit(this_vert);
    explore(remaining_graph);
}

Pseudocode for DFS

DFS(graph):
    for v of graph.verts:
        v.color = white
        v.parent = null

    for v of graph.verts:
        if v.color == white:
            DFS_visit(v)

DFS_visit(v):
    v.color = gray

    for neighbor of v.adjacent_nodes:
        if neighbor.color == white:
            neighbor.parent = v
            DFS_visit(neighbor)

    v.color = black

Implementation:

class Node(object):

    def __init__(self, name):
        self.name = name
        self.adjacencyList = []
        self.visited = False
        self.predecessor = None


class DepthFirstSearch(object):  # BFS -> queue + layer by layer algorithm   DFS -> stack + goes
    # as deep as possible into the tree !!!

    def dfs(self, node):

        node.visited = True
        print("%s " % node.name)

        for n in node.adjacencyList:
            if not n.visited:
                self.dfs(n)


node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")
node5 = Node("E")

node1.adjacencyList.append(node2)
node1.adjacencyList.append(node3)
node2.adjacencyList.append(node4)
node4.adjacencyList.append(node5)

dfs = DepthFirstSearch()
dfs.dfs(node1)
def graph_dfs(matrix):
    rows, cols = len(matrix), len(matrix[0])
    visited = set()
    directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
    def dfs(i, j):
        if (i, j) in visited:
            return
        visited.add((i, j))
        # Traverse neighbors.
        for direction in directions:
            next_i, next_j = i + direction[0], j + direction[1]
            if 0 <= next_i < rows and 0 <= next_j < cols: # Check boundary.
                # Add any other checking here ^
                dfs(next_i, next_j)

    for i in range(rows):
        for j in range(cols):
            dfs(i, j)

graph_dfs([
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
])

Finding of weighted graphs

, useful for scheduling sequences of dependent jobs

Minimum Spanning Trees
Topological sorting