GRAPHS: GENERAL INFORMATION

Graph definition:

A graph, G = (V,E), is a set of vertices, V, and a set of edges, E.

Each edge is a pair (v,w), where $v \in V$ and $w \in V$.

Example (directed graph):

In a directed graph, the edge (a,d) and (d,a) are different edges.

G = (V,E) where $V = \{a,b,c,d\}$ and
$E = \{(a,b), (a,c), (a,d), (b,c), (c,d), (d,a)\}$

Example (un-directed graph):

In an undirected graph, edge (a,d) automatically implies that (d,a) exists. Below is an example of an undirected graph:

G = (V,E) where $V = \{a,b,c,d\}$ and
$E = \{(a,b), (a,c), (a,d), (b,c), (b,d), (c,d)\}$

Edge Weights:

For many applications, an edge can have a weight value.

Also, we can label the vertices with any label, or the vertices themselves could store data!

Example (weighted graph):

G = (V,E) where $V = \{NY,LA,MIA,ATL\}$ and
$E = \{(NY,LA,\$1000), (NY,MIA,\$600), (NY,ATL,\$500),$
$(MIA,LA,\$1200)\}$

Graph Terminology:

• Adjacent vertices (directed graphs): Vertex a is adjacent to vertex b only if edge (a,b) is present.
• Adjacent vertices (undirected graphs): Vertex a and b are adjacent if (a,b) is present. (note: (b,a) implies that (a,b) is present.)
• Path: A sequence of adjacent vertices. $v_1,v_2,\ldots,v_k$ such that $(v_i,v_{i+1}) \in E$ for all i from 1 to k. (note: this path has a length of k-1; the length of a path is the number of edges along the path.)
• Connected vertices: Two vertices a and b are connected if there exists a path from a to b.
• Cycle: Any path of length 2 or greater that starts and ends with the same vertex.
• Acyclic graph: A graph with no cycles.
• Connected undirected graph: An undirected graph such that there exists a path from every vertex to every other vertex.
• Strongly connected directed graph: A directed graph such that there exists a directed path from every vertex to every other vertex.
• Weakly connected directed graph: A directed graph such that there exists an undirected path from every vertex to every other vertex (i.e. the underlying graph without edge directions is connected).
• Complete graph: Every vertex is mutually adjacent with every other vertex.

Applications of Graphs:

Almost any problem that involves entities and relationships can be modeled as a graph.

In the graph below the vertices are characters from the TV show ``Friends.'' An edge connects two friends if they have had ``intimate relations.'' The weight of an edge is the episode number that the two friends had ``relations.''

Such a graph can be used to solve problems. For instance, if ``Ross's wife'' contracted a disease before Episode 1, we could figure out who is likely to have caught the disease through ``relations.''

Formally, we want to find a path from ``Ross's wife'' to every other vertex such that the edge labels of the path are in increasing order (since the episode numbers correspond to time). If there exists an increasing path from ``Ross's wife'' to another friend then the disease is likely to have been passed to that friend.

More conventional graph problems and applications include:

• Transportation problems
• Network routing
• Supply-demand relationships
• Optimization and Planning problems.

GRAPH IMPLEMENATIONS

1. Adjacency lists.

Advantage: Compact representation for sparse graphs (i.e. graphs with few edges).

Disadvantage: Requires iterating through adjacency list. Thus, determining adjacency or searching for an edge is not a constant time operation (it depends on the number of adjacencies for a particular vertex).

2. Adjacency matrix. Advantage: Constant time access for all edges. Thus, determining adjacency or searching for an edge is a constant time operation.

Disadvantage: Requires |V|² memory. Wastes memory for sparse graphs.

MINIMUM SPANNING TREE PROBLEM

Input: A weighted graph (must be connected and undirected) G = (E,V)

Output: A subset of E that forms a tree which connects all the vertices of G and has minimum weight.

Details: The weight of the tree is the sum of the weights of all the tree's edges. A tree is simply a graph with no cycles.

Algorithms:

Prim's O(|V|²) without heaps $O(\vert E\vert \log \vert V\vert)$ with heaps

1.

Start with an arbitrary vertex and add it to the Tree

2.

Pick a connected edge with the minimum weight

3.

Add the edge along with its other vertex to the Tree

4.

Pick an edge (connected to the Tree) with the minimum weight

5.

Add the edge along with its other vertex to the Tree if the vertex is not already part of the tree

6.

Repeat until all vertices are part of the tree.

Kruskal's $O(\vert E\vert \log \vert E\vert)$ with heaps

void Graph::kruskal() {
   int edgesAccepted;
   DisjSet s(NUM_VERTICES);    // Set of disjoint sets
   PriorityQueue h(NUM_EDGES);// Priority queue of edges
   Vertex u, v;                // Vertices     
   SetType uset, vset;         // Vertex sets
   Edge e;                     // e = (u,v)

   h = readGraphIntoHeapArray();
   s = readVerticesIntoDisjSet();
   h.buildHeap();

   edgesAccepted = 0;
   while ( edgesAccepted < NUM_VERTICES - 1 ) {
      e = h.deleteMin();
      uset = s.find(e.u);
      vset = s.find(e.v);
      if (uset != vset) {
         edgesAccepted++;
         s.unionSets( uset, vset );
      }
   }
}

Sample Problem

Starting Graph:

 

 

 

 

 

 

Minimum Spanning Tree:

Actions of Kruskal's Algorithm

Running time of Prim and Kruskal's algorithms

Recall that for an undirected connected graph, the number of edges |E| ranges from |V| - 1 to $\vert V\vert(\vert V\vert - 1)/2 = \Theta(\vert V\vert^2)$

For an directed connected graph, the number of edges |E| ranges from |V| - 1 to $\vert V\vert(\vert V\vert - 1) = \Theta(\vert V\vert^2)$

Prim's
O(|V|²) which is good for dense graphs
(i.e. $\vert E\vert = \Theta(\vert V\vert^2)$), or
$O(\vert E\vert \log \vert V\vert)$ (using heaps) which is good sparse graphs
(i.e. |E| grows smaller than $\Theta(\vert V\vert^2)$).

Kruskal's
$O(\vert E\vert \log \vert E\vert)$ by its nature Kruskal's algorithm is not good for dense graphs. Why?

Question: Why is $O(\vert E\vert \log \vert E\vert)$ = $O(\vert E\vert \log \vert V\vert)$?

SINGLE SOURCE SHORTEST PATH PROBLEM

Given as input a weighted graph (usually connected, but can be directed or undirected), G = (V,E), and a distinguished vertex, s, find the shortest weighted path from s to every other vertex in G.

Sample problem

 

 

 

 

 

 

 

Implemenation of Dijkstra's

First, we need a class for storing the needed vertex information and a class for string the graph.

class Vertex {
   bool known;     // Has the vertex been visited?
   DistType dist;  // The distance from the source to this vertex
   Vertex * path;  // The path from the source to this vertex
   DataType data;  // The data stored in the vertex
};

class Graph {
   vector<Vertex> vertices; // The vertices
   vector< vector<DistType> > matrix; // The edges
};

Next, we need to initialize the graph. Assume we have some data source such as a file and a function for parsing and reading in the data.

void Graph::init(SomeDataSource t) {
  readVertices(t);
  for (int i = 0; i < vertices.size(); i++) {
    vertices[i].known = false;
    vertices[i].dist = INFINITY;
    vertices[i].path = NULL:
  }
}

Pseudocode for Dijkstra's algorithm

Vertex s is the source vertex (s should be in the Graph) For every vertex v in the graph, this algorithm will compute the shortest distance from s to v and the algorithm will also compute the path from s to each vertex v.

void Graph::dijkstra(Vertex s) {
   Vertex v, w;
   s.dist = 0; /* Set the distance to the source to zero */
   /* Loop until all the vertices in the graph are known */
   while(1) {
      /* Find an unknown vertex with the minimum .dist */
      v = find_unknown_min();    
      if (v == NULL)
         break;
      v.known = true;
      /* Iterate through the adjacency list of v */
      for each w adjacent to v 
         if (!w.known) 
            if (v.dist + matrix[v][w] < w.dist) {
               w.dist = v.dist + dist(v,w);
               w.path = &v;
            }
   }
}

Finding an unknown vertex with minimum distance

Dijkstra's algorithm needs to search the vector of vertices (i.e vector<Vertex>) to find a vertex that is unknown (i.e v.known == false) and has the minimum distance of all unknown vertices (i.e v.dist is minimum).

Note: this is a member function of Graph.
Vertex * find_unknown_min() {
  Vertex * v = NULL;
  DistType d = INFINITY;
  for (int x = 0; x < vertices.size(); x++) 
    if (vertices[x].known == false)
       if (vertices[x].dist < d) {
          d = vertices[x].dist;
          v = &vertices[x];
       }
  return v;
}

Using the graph information to print the shortest path

Dijkstra's algorithm computes the distance from the source, s, to every other vertex. This information is stored in v.dist.

Dijkstra's algorithm also computes the actual shortest paths from s to every other vertex. This information is stored in v.path

Here is an algorithm which uses the path pointers to actually print the path:

Note: this is a member function of Graph.
void printShortestPath(Vertex * v) {
  if (v.path != NULL) {
    printShortestPath(v->path);
    cout << `` to ``;
  }
  cout << v.label; // or cout << v.data
}

About this document ...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -no_navigation -split 0 head.tex.

The translation was initiated by Eric Breimer on 2000-12-04