ADTs So Far…

• Set
• Multiset/Bag
• List
• Stack
• Queue
• Deque
• Map/Dictionary
• Priority Queue

Types of Graphs and Graph Applications

• Directed/Undirected
• Weighted/Unweighted

Sampling of graph terminology:

• Terminology from the reading:
  • vertex/node
  • edge
  • undirected
  • directed
  • digraph
  • weight
  • weighted graph
  • sparse
  • dense
  • path
  • cycle/cyclic/acyclic
• Important graph terminology not discussed in the reading:
  • degree - The number of edges incident to a vertex.
  • out degree - Number of outgoing edges from a vertex (directed graphs).
  • in degree - Number of incoming edges.
  • connected graph - Graph with a path connecting all pairs of vertices.
  • subgraph - A graph whose vertices and edges are a subset of another graph.
  • connected component - A connected subgraph that is not part of a larger connected subgraph.
  • complete graph - All possible edges are present.
  • clique - a complete subgraph.

Graph ADT

Since there is so much variability in types of graphs and how they are used, most standard collection libraries don’t include a Graph implementation. Here is a sample ADT described as a Java interface:

/**
 * Minimal Unweighted Graph Interface. 
 * This interface assumes that the graph size is known at initialization time. 
 * Each node has an integer identifier. 
 * No self-edges are allowed.
 */
public interface Graph<T> {

  void init(int numNodes);

  int numNodes();

  int numEdges();

  void addEdge(int from, int to);

  boolean hasEdge(int from, int to);

  void removeEdge(int from, int to);

  Iterable<Integer> neighbors(int id);

}

Graph Implementations: Adjacency Matrix

• Let’s look at an example…
  • https://www.cs.usfca.edu/~galles/visualization/BFS.html

• Performance?

  public interface Graph<T> {
  
    boolean hasEdge(int from, int to); // Theta(??)
  
    Iterable<Integer> neighbors(int id); // Theta(??) 
                                         // to perform the iteration
  
  }

• Memory requirements?

Graph Implementations: Adjacency Matrix

• Let’s look at an example…
  • https://www.cs.usfca.edu/~galles/visualization/BFS.html

• Performance?

  public interface Graph<T> {
  
    boolean hasEdge(int from, int to); // Theta(1)
  
    Iterable<Integer> neighbors(int id); // Theta(V) 
                                         // to perform the iteration
  
  }

• Memory requirements? \(\Theta(V^2)\)

Graph Implementations: Adjacency List

• Let’s look at an example…
  • https://www.cs.usfca.edu/~galles/visualization/BFS.html

• Performance?

  public interface Graph<T> {
  
    boolean hasEdge(int from, int to); // Theta(??)
  
    Iterable<Integer> neighbors(int id); // Theta(??) 
                                         // to perform the iteration
  
  }

• Memory requirements?

Graph Implementations: Adjacency List

• Let’s look at an example…
  • https://www.cs.usfca.edu/~galles/visualization/BFS.html

• Performance?

  public interface Graph<T> {
  
    boolean hasEdge(int from, int to); // Theta(out-degree from)
  
    Iterable<Integer> neighbors(int id); // Theta(out-degree id) 
                                         // to perform the iteration
  
  }

• Memory requirements: \(\Theta(V + E)\), where \(V\) is the number of vertices and \(E\) is the number of edges.

Graph Implementation: Hashing

• Adjacency HashSets

• Performance?

  public interface Graph<T> {
  
    boolean hasEdge(int from, int to); // Theta(1) (Average case)
  
    Iterable<Integer> neighbors(int id); // Theta(out-degree id) 
                                         // to perform the iteration
  
  }

• Memory requirements? \(\Theta(V + E)\)

Depth-First Traversal

• Recursive:

  RecursiveDFS(currentV) {
     if ( currentV is not in visitedSet ) {
        Add currentV to visitedSet
        "Visit" currentV
        for each vertex adjV adjacent to currentV {
           RecursiveDFS(adjV)
        }
     }
  }

• Non-Recursive:

  DFS(startV) {
     Push startV to stack
  
     while ( stack is not empty ) {
        currentV = Pop stack
        if ( currentV is not in visitedSet ) {
           "Visit" currentV
           Add currentV to visitedSet
           for each vertex adjV adjacent to currentV
              Push adjV to stack
        }
     }
  }

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

Breadth-First Traversal

BFS(startV) {
   Enqueue startV in frontierQueue
   Add startV to discoveredSet

   while ( frontierQueue is not empty ) {
      currentV = Dequeue from frontierQueue
      "Visit" currentV
      for each vertex adjV adjacent to currentV {
         if ( adjV is not in discoveredSet ) {
            Enqueue adjV in frontierQueue
            Add adjV to discoveredSet
         }
      }
   }
}

Example:

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