Classic Algorithms – Graph Traversal (CS2004, 2024-2025)

Vocabulary flashcards covering key terms and definitions from the lecture on classic graph-traversal algorithms, including DFS, BFS, exhaustive, best-first, A*, and minimum spanning trees.

Graph (G = (V,E))

A data structure consisting of a set of vertices (nodes) V and a set of edges (connections) E linking pairs of vertices.

Vertex (Node)

An individual element or point in a graph where edges meet; part of the set V.

Edge

A connection between two vertices u and v in a graph, written as e = (u,v) or (v,u).

Undirected Graph

A graph whose edges have no orientation; movement is allowed both ways along each edge.

Directed Graph (Digraph)

A graph whose edges are ordered pairs, giving each edge a single direction (arrow).

Weighted Graph

A graph in which every edge is assigned a numerical value (weight) representing cost, length, etc.

Complete Graph

A graph in which every pair of distinct vertices is connected by an edge.

Graph Traversal

The process of systematically visiting every vertex (and often every edge) of a graph, usually exactly once.

Depth-First Strategy

A way of exploring a graph by following a path as far as possible before backtracking when a dead end is reached.

Depth-First Search (DFS)

A traversal algorithm that visits a start node, recursively explores as deep as possible, backs up on dead ends, and ends when all vertices reachable from the start are visited.

Dead End (DFS)

A node that has no unvisited adjacent vertices (directed: no outgoing edges) during depth-first search.

DFS Time Complexity

O(n + m) where n is the number of vertices and m is the number of edges, because each vertex and edge is processed once.

Exhaustive Search

A brute-force technique that systematically explores every possible path in a graph; always finds the goal but is usually impractical.

Exhaustive Search Complexity

Worst-case O((n−1)!), arising in complete graphs as the number of possible paths grows factorially.

Breadth-First Search (BFS)

A traversal method that explores all neighbors of the start node first, then their neighbors, level by level until the goal is found.

Best-First Search

An improvement on DFS that uses a heuristic to choose which node to expand next, preferring nodes estimated to be closer or cheaper to the goal.

Heuristic (in Search)

A rule of thumb or informed estimate that guides a search algorithm toward promising paths (e.g., straight-line distance).

A* Search

A best-first search that scores each partial path with f = g + h, where g is the cost so far and h is an admissible estimate of the cost to the goal, guaranteeing an optimal path.

f = g + h Function

The evaluation formula in A* where g is accumulated path cost and h is estimated remaining cost; the path with the smallest f is expanded next.

Greedy Search

A special case of best-first search where g is considered zero and decisions are based solely on the heuristic h, making locally optimal choices.

Spanning Tree

A sub-graph that is a tree containing all vertices of the original connected, undirected graph with no cycles.

Minimum Spanning Tree (MST)

A spanning tree whose total edge weight is the smallest possible among all spanning trees of the graph.

Prim’s Algorithm

A greedy algorithm for finding an MST by starting at an arbitrary vertex and repeatedly adding the lightest edge connecting the growing tree to a new vertex.

MST Applications

Used in network design, approximation for NP-hard problems (e.g., Traveling Salesperson), cosmology mapping, cancer imaging, and more.