graph intro and DFS flashcards

Graph Representation

Graphs consist of vertices (nodes) and edges (connections) and can be directed or undirected

Adjacency List

Stores for each node a list/set/vector of all connected neighbors and is efficient for sparse graphs

Adjacency Matrix

A 2D matrix where matrix[i][j] indicates edge presence and is efficient for dense graphs but uses O(V^2) space

Node Map Representation

UTK notes often use maps from node names to sets/vectors of neighboring nodes for flexible graph construction

Directed Graph

Edges have direction from one node to another

Undirected Graph

Edges work both ways

Sparse Graph

Has relatively few edges compared to possible maximum

Dense Graph

Has many edges and may justify matrix storage

DFS (Depth First Search)

Traverses graph by exploring as deep as possible along one path before backtracking

DFS Core Idea

Visit node then recursively visit each unvisited neighbor

DFS Data Structure

Uses recursion or explicit stack

DFS Starting Point

Begins at chosen source node then expands depth-first

DFS Visit Rule

Mark node visited immediately to avoid revisits/cycles

DFS Backtracking

When no unvisited neighbors remain return to previous node

DFS Runtime

O(V + E) because each node and edge is processed once

DFS Space Complexity

O(V) due to recursion stack/visited tracking

DFS Tree

The traversal creates a spanning tree showing discovery paths

DFS Recognition Pattern

Long branch exploration before returning rather than level-by-level

DFS Example Pattern

Go deep A→B→D→F before exploring sibling branches

Recursive DFS

Function calls itself on each unvisited neighbor

Iterative DFS

Uses stack manually instead of recursion

Recursive DFS Advantage

Simpler and cleaner code

Iterative DFS Advantage

Avoids recursion depth limits

Stack Behavior

LIFO order causes newest discovered node to be explored next

DFS vs BFS

DFS explores depth-first while BFS explores breadth/level-first

DFS on Cyclic Graphs

Requires visited set to prevent infinite loops

Connected Component

A maximal set of vertices where each is reachable from others

DFS for Connected Components

Run DFS from unvisited nodes repeatedly to identify each component

Component Counting

Each new DFS call from an unvisited node indicates a new connected component

DFS Forest

Collection of DFS trees for disconnected graphs

Spanning Tree

A subset of edges connecting all reachable nodes without cycles

DFS Spanning Tree

Contains discovery edges only

Tree Edge

Edge used to first discover a node

Back Edge

Edge connecting node to ancestor indicating cycle in directed DFS

Cross Edge

Edge connecting unrelated branches in directed DFS

Cycle Detection with DFS

If DFS reaches an already active ancestor then a cycle exists

Undirected Cycle Detection

Ignore parent edge but revisiting another visited node implies cycle

Topological Sort Connection

Reverse DFS postorder can produce valid topological ordering in DAGs

Preorder Traversal

Order nodes when first visited

Postorder Traversal

Order nodes when fully processed after children

Reverse Postorder

Useful for topological sort

DFS Maze Analogy

Follow one corridor fully before trying alternatives

Graph File Parsing

UTK notes emphasize reading vertices and edges from structured input files

Building Graph from File

Create node entries then add adjacency relationships

Node Discovery State

Commonly white/unvisited gray/active black/finished conceptually

Marking Visited

Usually boolean set/map

DFS Pseudocode

Mark current node visited then recursively process each unvisited neighbor

DFS Base Case

Return when all neighbors are already visited

DFS Order Dependency

Traversal order depends on adjacency list ordering

Neighbor Ordering

Changing adjacency ordering changes DFS output but not correctness

DFS for Path Existence

Can determine if target node is reachable

Reachability

If DFS visits node then it is reachable from source

DFS Path Reconstruction

Store parent pointers to reconstruct route

Parent Pointer

Tracks node from which current node was discovered

DFS Parent Tree

Allows path backtracking to source

DFS on Disconnected Graph

Must loop through all nodes and launch DFS on unvisited ones

Full Graph Traversal

Outer loop + DFS covers all components

DFS Application Maze Solving

Explores possible routes deeply until exit found

DFS Application Topological Sort

Postorder stack gives valid dependency ordering

DFS Application Cycle Detection

Detects loops in prerequisite/dependency graphs

DFS Application Connectivity

Determines whether graph is fully connected

DFS Application SCC Foundations

Forms basis for strongly connected component algorithms

BFS Comparison Runtime

Both BFS and DFS are O(V+E)

BFS Comparison Memory

BFS often uses more memory due to queue of broad frontier

DFS Memory Strength

Usually smaller active set if graph is deep not wide

DFS Weakness

Does not guarantee shortest path

BFS Shortest Path

BFS guarantees shortest path in unweighted graphs

DFS Traversal Output

Produces deep recursive-like visitation order

BFS Traversal Output

Produces level-order visitation

DFS Edge Processing

Each adjacency list scanned once

DFS with Stack Push

Push neighbors onto stack for later processing

DFS Iterative Ordering

May reverse neighbor visitation depending on push order

DFS Recursive Output

Typically follows adjacency list order directly

Infinite Loop Risk

Without visited markers DFS may repeat forever in cyclic graphs

Graph Search Goal

Explore structure

DFS Component Example

If graph has 3 disconnected groups DFS outer loop runs 3 times

Visited Vector

Boolean vector indexed by node ID for fast tracking

Visited Set

Useful when node labels are strings

Adjacency Set Advantage

Prevents duplicate edges automatically

Adjacency Vector Advantage

Faster iteration and preserves insertion order

Graph Construction Complexity

O(E) insertion plus node setup

DFS Discovery Edge

Edge followed to first visit new node

DFS Finish Time

Timestamp after exploring all descendants

Discovery Time

Timestamp when node first visited

Finish Time Use

Helpful in topological sort and SCC algorithms

DFS Exam Phrase

Explore one branch fully before backtracking using recursion/stack in O(V+E)

Connected Graph

A graph where every node is reachable from every other

Disconnected Graph

Contains multiple components

DAG

Directed acyclic graph with no directed cycles

DFS on DAG

Can support topological sorting

DFS Tree Height

Can be as deep as longest path

Worst Case Stack Depth

O(V)

DFS Best Use Cases

Connectivity cycle detection topological preprocessing

DFS Poor Use Case

Shortest path in unweighted graph

Edge List

Simple pair list of edges often converted into adjacency list

DFS Traversal Determinism

Depends on neighbor processing order

Graph Label Mapping

Map string labels to integer indices for efficient storage

DFS Start Node Choice

Affects traversal order but not full reachability

DFS Forest Root

Each unvisited start node becomes root of new DFS tree

Component Labeling

Mark all nodes in same DFS run with same component ID