Graphs

Graph Definitions

Graph: A data structure that consists of a set of nodes and a set of edges that relate the nodes to each other

Vertex: A node in a graph

Edge (arc): A pair of vertices representing a connection between two nodes in a graph

Undirected graph: A graph in which the edges have no direction

Directed graph (digraph): A graph in which each edge is directed from one vertex to another (or the same) vertex

Formally, a graph G is defined as follows:

G = (V,E)

where

• V(G) is a finite, nonempty set of vertices
• E(G) is a set of edges (written as pairs of vertices)

Graphs as Collections

Useful when you have data that needs to be related to other items of data in numerous relationships

The vertex holds the object of information

• Linear = one predecessor; one successor
• Binary => one predecessor; up to two successors
• Graphs => any number of predecessors and/or successors (in the case of directed graphs); a higher degree of interconnection

Edges represent direct relationships between nodes. Edges may also have numeric values called weights.

Graphs can be used to represent complex relationships. In practice, if you have large quantities of data and data of different object types, you would use a database (relational or object oriented) to help organize and facilitate retrieval.

If you have "smaller" quantities of homogeneous data that have a multiple degree of interconnection, then you might use a graph structure.

We will only review the graph structure for purposes of completeness of the overview of data structures in this course. Fuller discussions of graph theory is covered in Algorithms and Analysis.

Examples

More Definitions

Adjacent vertices: Two vertices in a graph that are connected by an edge

Path: A sequence of vertices that connects two nodes in a graph

Complete graph: A graph in which every vertex is directly connected to every other vertex

Weighted graph: A graph in which each edge carries a value

Weighted graph example

Graph Traversals

Want to be able to visit each node in a graph once.

Depth-First Search-- search is biased to follow connections of children before processing siblings (use a stack or recursion)

Breadth-First Search--search is biased to follow connections of siblings before processing children (use a queue)

The visit order and relationship of nodes in the visit process is called a spanning tree

Weighted Graph Interface

public interface WeightedGraphInterface
{
  public boolean isEmpty();
  // Effect:         Determines whether this graph is empty.
  // Postcondition:  Return value = (this graph is empty)

  public boolean isFull();
  // Effect:         Determines whether this graph is full.
  // Postcondition:  Return value = (this graph is full)

  public void addVertex(Object vertex);
  // Effect:	     Adds vertex to the graph.
  // Precondition:   Graph is not full.
  // Postcondition:  vertex is in V(graph).

  public void addEdge(Object fromVertex, Object toVertex, int weight);
  // Effect:         Adds an edge with the specified weight from fromVertex 
  //                   to toVertex.
  // Precondition:   fromVertex and toVertex are in V(graph).
  // Postcondition:  (fromVertex, toVertex) is in E(graph) with the specified weight.

  public int weightIs(Object fromVertex, Object toVertex);
  // Effect:         Determines the weight of the edge from fromVertex to toVertex.
  // Precondition:   fromVertex and toVertex are in V(graph).
  // Postcondition:  if edge exists, Return value = (weight of edge from fromVertex 
  //                   to toVertex)
  //                 otherwise return value = (special “null-edge” value)

  public QueueInterface getToVertices(Object vertex);
  // Effect:         Returns a queue of the vertices that are adjacent from vertex.
  // Precondition:   vertex is in V(graph).
  // Postcondition:  returns a queue containing all the vertices that are adjacent
  //                   from vertex.

  public void clearMarks();
  // Effect:         Sets marks for all vertices to false.
  // Postcondition:  All marks have been set to false.

  public void markVertex(Object vertex);
  // Effect:         Sets mark for vertex to true.
  // Precondition:   vertex is in V(graph).
  // Postcondition:  isMarked(vertex) is true.

  public boolean isMarked(Object vertex);
  // Effect:         Determines if vertex has been marked.
  // Precondition:   vertex is in V(graph)
  // Postcondition:  return value = (vertex is marked true)
}

Array-Based Implementation

Adjacency Matrix: for a graph with N nodes, and N by N table that shows the existence (and weights) of all edges in the graph

Adjacency Matrix for Flight Connections

Linked Implementation

Adjacency List: A linked list that identifies all the vertices to which a particular vertex is connected; each vertex has its own adjacency list

Adjacency List Representation of Graphs