Data Structure and Algorithm Design

Sections

• Graph

• Graph Traversal

• Single Source Shortest Path (SSSP) Dijkstra’s Algorithm

Graph

Outline

• Overview

• Concepts

• Example graphs

• Representations

• Algorithms

Overview

• Graphs are a fundamental data structure in computer science.

• Graphs are used to model networks, complex relationships, etc.

• Vertices(nodes) connected by edges.

Applications

Concepts

Examples

Representations

• Vertices with pointers to neighbors (uncommon)

• List of edges

  A list of edges is a 1d array in which every element in the array represents an edge. It is the simplest way to represent a graph. It is also an easy way to store a graph in a relational database. It is not efficient for most graph algorithms though.

• Adjacency list

  An adjacency list is a 1d array in which every element in the array represents a vertex and points to a list of its neighbors.

• Adjacency matrix

  An adjacency matrix is a 2d array in which each row represents a source vertex and each column represents a destination vertex. The elements in the matrix represents the edge between the two vertices.

Algorithms

• Graph traversal

  • Breadth-first search

  • Depth-first search

• Topological sort (DAG only)

• Shortest path

  • Dijkstra’s algorithm (single source, greedy)

  • Floyd-Warshall Algorithm (all pairs, dynamic programming)

• Minimum spanning tree

  • Prim’s algorithm (greedy)

  • Kruskal’s algorithm (greedy)

Graph Traversal

• Overview

• Depth First Search (DFS)

• Breadth First Search (BFS)

• Visualization

Overview

• Start from a vertex

• Visit all reachable vertices connected to it in a systematic order

• Two common ways to traverse a graph

  • Depth First Search (DFS)

  • Breadth First Search (BFS)

Depth First Search (DFS)

• Like walking in a maze, you go as far as you can, then backtrack

function dfs(startVertex):
  create a new stack

  push startVertex onto the stack
  mark startVertex as visited

  while the stack is not empty:
    current = pop from the stack
    process(current)  # Perform an action on the current node

    for each neighbor in current.neighbors:
      if neighbor is not in visited set:
        push neighbor onto the stack
        add neighbor to the visited set

function dfs(vertex, visited):
  if vertex is not visited:
    mark vertex as visited
    visit(node)  # Perform an action on the vertex

    for each neighbor of the vertex:
      if neighbor is not visited:
          dfs(neighbor, visited)

Breadth First Search (BFS)

• Like a wave, you visit all vertices at the same level before going deeper

• Queue based implementation

function bfs(startVertex):
  create a new queue

  enqueue the startVertex
  mark the startVertex as visited

  while the queue is not empty:
    dequeue a vertex from the queue
    process(vertex)  # Perform an action on the vertex

    for each neighbor of the vertex:
      if neighbor is not visited:
        mark the neighbor as visited
        enqueue the neighbor

Visualization

• https://visualgo.net/en/dfsbfs

• https://www.cs.usfca.edu/~galles/visualization/BFS.html

• https://www.cs.usfca.edu/~galles/visualization/DFS.html

Dijkstra’s Algorithm

• Single source shortest path algorithm

• Greedy algorithm

• visualization

  • https://visualgo.net/en/sssp

  • https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html

function dijkstra(graph, source):
  create a priority queue PQ
  initialize distances to all vertices as infinity
  set the distance to the source as 0
  enqueue source to PQ

  while PQ is not empty:
    current_vertex = vertex with the smallest distance in PQ
    remove current_vertex from PQ

    for each neighbor of current_vertex:
      edge_weight = weight of the edge between current_vertex and neighbor
      tentative_distance = distance to current_vertex + edge_weight
      if tentative_distance < distance to neighbor:
        set distance to neighbor as tentative_distance
        add neighbor to PQ