Depth-First Search and Related Algorithms

Flashcards covering important concepts related to Depth-First Search, Breadth-First Search, and Dijkstra's Algorithm.

Depth First Search (DFS)

A recursive algorithm for searching all vertices of a graph or tree data structure by exploring as far as possible along each branch before backtracking.

Traversal

The process of visiting all the nodes in a graph.

Time Complexity of DFS

O(|V| + |E|), where |V| is the number of vertices and |E| is the number of edges.

Space Complexity of DFS

O(|V|) in the worst case, for storing the stack of vertices and visited vertices.

Backtracking

The process of moving backwards in the search path when there are no more nodes to explore in the current path.

Visited List in DFS

A list that marks vertices as visited to avoid cycles during traversal.

Topological Sort

An ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, vertex u comes before v.

Spanning Tree

A tree that includes all vertices of the graph and is obtained through processes like DFS.

Applications of DFS

Used for finding paths, detecting cycles, and performing topological sorting in graphs.

Breadth First Search (BFS)

An algorithm for searching tree or graph data structures that explores all nodes at the present depth before moving on to the next depth level.

Dijkstra's Algorithm

An algorithm for finding the shortest path between vertices in a weighted graph.

Greedy Algorithm

An algorithm that makes the locally optimal choice at each stage with the hope of finding the global optimum.

Infinity in Graph Algorithms

Represents a distance value that is extremely large, indicating a vertex has not been visited yet or is unreachable.

Queue in BFS

A data structure used to keep track of the next nodes to visit in breadth-first search.

Graph Cycle

A path in a graph where the start and end vertices are the same and consists of at least one edge.