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

Algorithms and Their Applications

CS2004 (2024-2025)

  • Instructor: Dr. Mahir Arzoky

Previously On CS2004

  • Course Content Overview:

    • Concepts of Computation and Algorithms

    • Comparing algorithms

    • Some mathematical foundation

    • The Big-Oh notation

    • Computational Complexity

    • Data structures

    • Last lecture: Sorting Algorithms

Classic Algorithms - Graph Traversal

Overview of Lectures on Graph Traversal

  • Focus on classic graph traversal algorithms:

    • Depth-First Search (DFS)

    • Exhaustive Search

    • Breadth-First Search (BFS)

    • A* (A-Star) Search

    • Minimum Spanning Trees (MST)

Understanding Graphs

Definitions

  • A graph G = (V,E) comprises:

    • V: A set of vertices or nodes

    • E: A set of edges connecting the vertices

    • Example:

      • V={1,2,3,4,5}

      • E={(1,2),(1,3),(3,5),(2,5),(5,4)}

Types of Graphs

  • Characteristics of graphs:

    • Undirected: Edges go both ways

    • Complete: An edge exists between all nodes

    • Weighted: Each edge has an associated value

    • Directed: Edges have a specific direction (arrows)

Search in Graphs

Concepts

  • Objective: Start at the source node and search for the target node

  • Ensure each node is visited exactly once

    • Examples of applications:

      • Distributing information across network computers

      • Searching for data within a network

Depth-First Search (DFS)

Definition

  • DFS explores nodes and edges to reach a dead end before backtracking.

    • In undirected graphs, a node is a dead end if all adjacent nodes are visited.

    • In directed graphs, a node is a dead end if it has no outgoing edges or all connected nodes are visited.

DFS Procedure

  1. Visit starting node, follow links through the graph until reaching a dead end.

  2. Backtrack to find an unvisited adjacent node and continue.

  3. Complete when all adjacent nodes are visited and return to starting node.

  4. If there are multiple choices, prefer the node with the smaller label.

DFS Example Traversals

  • Example Order of Visits:

    • From Node 1: 1,2,3,4,7,5,6 (Backtracking illustrated)

Depth-First Search Algorithms

Pseudocode

DFS(G,n)  
- Input: G - graph, n - current node  
  1) Visit(n)  
  2) Mark(n)  
  3) For each edge nm in G do  
  4)   If m not marked then  
  5)    DFS(G,m)  
  6)   End If  
  7) End For  
- Output: Depends on the purpose of the search.

Running Time Analysis

  • DFS operates:

    • O(n) for n nodes

    • O(m) for m edges

    • Total: O(n+m)

Alternative Graph Searches

Other Search Methods

  • Finding paths between nodes may involve:

    • Shortest path (by edges)

    • Cheapest path (based on edge weights)

Exhaustive Search

Definition

  • Systematically evaluates every possible path in a graph

  • Guarantees finding the desired result

  • Unsuitable for real-world applications due to complexity.

Exhaustive Search Algorithm Pseudocode

Exhaustive(G, n, p)  
- Input: G - graph, n - current node, p - path so far  
  1) For each edge nm in G do  
  2)   If m not in p then  
  3)     p = p ∪ {m}  
  4)     Exhaustive(G, m, p)  
  5)   End If  
  6) End For  
- Output: Depends on the purpose of the search.

Running Time Analysis

  • Complicates computation based on node/edge organization:

    • Worst-case for complete graph: O((n-1)!)

Breadth-First Search (BFS)

Definition

  • Explores graph by visiting neighboring nodes first.

  • All neighbors of the start node are expanded before deeper nodes.

  • Similar to exhaustive search but stops upon reaching a goal node.

Best-First Search

Definition

  • Improvement over DFS using heuristics to decide which nodes to explore next.

  • Evaluates based on established rules of thumb.

A* Search

Overview

  • A* search is a best-first search particularly good for route finding.

  • Requires two cost estimates:

    • Cost of the current path

    • Estimate of cost remaining to goal

A* Scoring Function

  • Uses function: f = g + h

    • g = cost so far

    • h = estimate to the goal (e.g., Euclidean distance)

A* Example Walkthrough

  • Example of graph traversal deciding paths based on least cost evaluations.

Minimum Spanning Trees (MST)

Definition and Characteristics

  • A spanning tree includes all nodes from a connected undirected graph with no cycles.

  • A Minimum Spanning Tree minimizes the total edge weight.

Prim's Algorithm for MST

Prim’sMST(G=(V,E))  
- Input: G - weighted graph  
  1) Randomly choose node x from V  
  2) Vnew = {x}  
  3) Enew = {}  
  4) While Vnew ≠ V do  
  5)   Choose edge (u,v) with minimal weight from u ∈ Vnew and v ∉ Vnew  
  6)   Vnew = Vnew ∪ {v}  
  7)   Enew = Enew ∪ {(u,v)}  
  8) End While  
- Output: Gnew = (Vnew, Enew)

Applications of MST

  • Used in network design, minimizing infrastructure costs, and understanding complex structures like those in cancer research.

Next Topics

  • Upcoming lecture on Floyd-Warshall and Dijkstra's algorithm

  • Laboratory sessions on Minimum Spanning Trees (MST) with testing.