Content

Defining Graphs Graph Implementation Complexity <- Go Back

EECS 281: Data Structures and Algorithms

Section 15

Graphs and Graph Algorithms

University of Michigan at Ann Arbor

Last Edit Date: 06/06/2023

Disclaimer and Term of Use:

1. We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file

2. This personal note is adapted from Professor Marcus Darden and David Paoletti. Please contact us to delete this file if you think your rights have been violated.

3. This work is licensed under a Creative Commons Attribution 4.0 International License.

---

Defining Graphs

i. Introduction

• A graph G = (V, E) is a set of vertices V = {$v_1, v_2, ...$} together with a set of edges E = {$e_1, e_2, ...$} that connect pairs of vertices.

• Edges are often represented as ordered pairs, such as $e_m = (v_s, v_t)$

• In general

  • Parallel edges are allowed

  • Self-loops are allowed

  • $E \le \frac{v(v - 1)}{2}$

• However, graphs without parallel edges and without self-loops are called simple graphs

• In general, assume a graph is simple unless explicity specified

• Definitions:

  • Simple Path: sequence of edges leading form one vertex to another with no vertex appearing twice

  • Connected Graph: a simple path exists between any pair vertices

  • Cycle: simple path, except that first and final nodes are the same

  • Directed Graph ot "digraph"

    • Edges have direction (one-way)

    • Nodes on edges form ordered pairs

      • Order of vertices in edge is impotant

      • $e_n = (u, v)$ means there is an edge from u to v

  • Undirected Graph

    • Nodes on edges form unordered pairs

      • Order of vetices in edge is not important

      • $e_n = (u, v)$ means there is an edge between u and v

  

• Edges may be "weighted"

  • Think of weight as the "distance between nodes" or "cost to traverse the edge"

  • In undirected graphs, weights may be different for sets of parallel edges

  • Algorithms often search a graph for a path (unweighted), or least cost path (weighted)

Example: Undirected and weighted

Graph Implementation

i. Graph Structures

• Complete Graph

  • All possible edges ($|E| = |V| \times |V - 1| / 2 \approx |V|^2$)

• Dense Graph

  • Many edges ($|E| \approx |V|^2$)

  • Represent as adjacency matrix (adjmat)

• Sparse Graph

  • Few edges ($|E| < |V|^2$) or ($|E| \approx |V|$)

  • Represent as adjacency list (adjlist)

Adjacency Matrix	Distance Matrix	Adjacency List

ii. Data Structures

Adjacency Matrix Implementation

• $|V| \times |V|$ matrix representing graph

• Directd vs. undirected

  • Directed adjacency matrix hs to / from

  • Undirected adjacency matrix only needs $V^2 / 2$ space

• Unweighted vs. weighted

  • Unweighted: 0 = no edge, 1 edge

  • Weighted: $\infty$ = noedge, value = edge

Undirected distance matrix:

Representing Infinity in C++

• #include <limits>

• Use numeric_limits<double>::infinity()

  – Adding, subtracting, multiplying and dividing finite values often does nothing to it

  – Multiplying by 0 results in 0 (Visual Studio) or nan (not a number) in g++

  – Dividing infinity by itself results in 1 (Visual Studio) or nan (g++)

  – Subtracting infinity from itself results in 0 (Visual Studio) or nan (g++

• Do not use numeric_limits<double>::max()

Adjacency List

• Assume random distribution of edges

• $\sim E / V$ edges on each vertex list

• Access vertex list: $O(1)$

• Find edge on vertex list: $O(E / V)$

• Average cost for individual vertex is $O(1 + E / V)$

• Cost for all verticesis $V \times O(1 + E / V) = O(V + E)$

• Directed vs. undirected

  • Directed adjacency List contains each edge once in edge set

  • Undirected adjacency List contains each edge twice in edge set

• Unweighted vs. weighted

  • Unweighted: nothing = no edge, <list_item> = edge

  • Weighted: nothing = no edge, <list_item_with_val> = edge

When to choose adjacency matrix or adjacency list?

If sparse, use adjacency list. If dense, use adjacency matrix.

Complexity

Complexity of graph algorithms is typically defined in terms of:

• Number of edges $|E|$, or

• Number of vertices $|V|$, or

• Both

Example 1: Determine whether non-stop flight from X to Y exists.

$$\text{Worst: }O(1)$$ $$\text{Best: }O(1)$$ $$\text{Average: }O(1)$$	$$\text{Worst: }O(V)$$ $$\text{Best: }O(1)$$ $$\text{Average: }O(1 + E / V)$$

Example 2: What is the closest other airport starting at X?

$$\text{Worst: }O(V)$$ $$\text{Best: }O(V)$$ $$\text{Average: }O(V)$$	$$\text{Worst: }O(V)$$ $$\text{Best: }O(1)$$ $$\text{Average: }O(1 + E / V)$$

Example 3: Determine if any flights depart from airport X.

$$\text{Worst: }O(V)$$ $$\text{Best: }O(1)$$ $$\text{Average: }O(V)$$	$$\text{Worst: }O(1)$$ $$\text{Best: }O(1)$$ $$\text{Average: }O(1)$$

Graph Algorithm Questions

• Associate a distance with each edge

• Associate a cost with each edge

• Describe an algorithm to determine greatest distance for least cost (ratio) that can be flown from JFK on a non-stop flight

• Give complexity

Route Planning

Task: determine the most efficient route (i.e. lowest cost) flown from X to Y on any trip, non-stop or connecting

Single-Source Shorest Path

• Find the shorest path to get to any vertex from somoe given starting point

• Depth First Search (DFS)

  • Ony works on trees; may find the wrong answer due to multiple paths in graphs

• Breadth First Search (BFS)

  • Works for unweighted edges or where all weights are considered the same

• Dijkstra's ALgorithm

  • Works for weighted edges

Depth-First Search

Given a graph $G = (V, E)$, explore the edges of $G$ to discover if any path exists from the source s to the goal g

• Use a stack

• Algorithm works on graphs and digraphs

• Path discovered may be a shorest path, but it is not guaranteed to be the shorest

Pseudocode:

Algorithm GraphDFS
    Mark source as visited
    Push source to Stack
    While Stack is not empty
        Get/Pop candidate from top of Stack
        For each child of candidate
            If child is unvisited
                Mark child visited
                Push child to top of Stack
                If child is goal
                    Return success
    Return failure

Example:

DFS: Analysis of Adjacency List

• DFS:

  • Called for each vertex at most once - $O(V)$

  • adjlist for each vertex is visited at most once and set of edges is distributed over set of vertices - $O(1 + E/V)$

• $O(V + E)$: linear with number of vertices and edges

DFS: Analysis of Adjacency Matrix

• DFS:

  • Called for each vertex at most once - $O(V)$

  • adjmat row for each vertex is visited at most once - $O(V)$

• $O(V^2)$: quadratic with number of vertices

Breadth-First Search

Given an unweighted graph $G = (V, E)$, explore the edges of G to discover a shortest path from source s to goal g, if any exists

• Use a queue

• Algorithm works on graphs and digraphs

• Discovers a shortest path only on unweighted graphs or where all edges have equal weight

Pseudocode:

Algorithm GraphBFS
    Mark source as visited
    Push source to back of Queue
    While Queue is not empty
        Get/Pop candidate from front of Queue
        For each child of candidate
            If child is unvisited
                Mark child visited
                Push child to back of Queue
                If child is goal
                    Return success
    Return failure

Example:

BFS: Analysis of Adjacency List

• BFS:

  • Called for each vertex at most once - $O(V)$

  • Adjlist for each vertex is visited at most once and set of edges is distributed over set of vertices - $O(1 + E/V)$

• $O(V + E)$: linear with number of vertices and edges

BFS: Analysis of Adjacency Matrix

• BFS:

  • Called for each vertex at most once - $O(V)$

  • Adjmat row for each vertex is visited at most once - $O(V)$

• $O(V2)$: quadratic with number of vertices

© Sample Academy