Chapter 24: Graphs

What is a Graph?

• A graph G = (V,E) is composed of:
  • V: set of vertices
  • E: set of edges connecting the vertices in V
• An edge e = (u,v) is a pair of vertices
• Example:
  • V= {a,b,c,d,e}
  • E= {(a,b),(a,c),(a,d), (b,e),(c,d),(c,e), (d,e)}

Applications

• electronic circuits
• networks (roads, flights, communications)

Terminology: Adjacent and Incident

• If (v0, v1) is an edge in an undirected graph,
  • v0 and v1 are adjacent
  • The edge (v0, v1) is incident on vertices v0 and v1
• If

Terminology: Degree of a Vertex

• The degree of a vertex is the number of edges incident to that vertex.
• If d_i is the degree of a vertex i in a graph G with n vertices and e edges, the number of edges is
• For directed graph,
  • the in-degree of a vertex v is the number of edges that have v as the head
  • the out-degree of a vertex v is the number of edges that have v as the tail

Terminology: Path

• path: sequence of vertices v1,v2,. . .vk such that consecutive vertices vi and v_{i+1} are adjacent.

More Terminology

• simple path: no repeated vertices
• cycle: simple path, except that the last vertex is the same as the first vertex

Even More Terminology

• subgraph: subset of vertices and edges forming a graph
• connected graph: any two vertices are connected by some path

More…

• tree - connected graph without cycles
• forest - collection of trees

Oriented (Directed) Graph

• A graph where edges are directed

Directed vs. Undirected Graph

• An undirected graph is one in which the pair of vertices in an edge is unordered, (v0, v1) = (v1,v0)
• A directed graph is one in which each edge is a directed pair of vertices,

Graph Representations

• Adjacency Matrix
• Adjacency Lists

Adjacency Matrix

• Let G=(V,E) be a graph with n vertices.
• The adjacency matrix of G is a two-dimensional n by n array, say adj_mat
• If the edge (vi, vj) is in E(G), adj_mat[i][j]=1
• If there is no such edge in E(G), adj_mat[i][j]=0
• The adjacency matrix for an undirected graph is symmetric; the adjacency matrix for a digraph need not be symmetric

Merits of Adjacency Matrix

• From the adjacency matrix, to determine the connection of vertices is easy

Adjacency Lists

• An undirected graph with n vertices and e edges ==> n head nodes and 2e list nodes

Graph Traversal

• Problem: Search for a certain node or traverse all nodes in the graph
• Depth First Search
  • Once a possible path is found, continue the search until the end of the path
• Breadth First Search
  • Start several paths at a time, and advance in each one step at a time

Depth-First Search

• DFS follows the following rules:
  • Select an unvisited node x, visit it, and treat as the current node
  • Find an unvisited neighbor of the current node, visit it, and make it the new current node;
  • If the current node has no unvisited neighbors, backtrack to the its parent, and make that parent the new current node;
  • Repeat steps 3 and 4 until no more nodes can be visited.
  • If there are still unvisited nodes, repeat from step 1.

Implementation of DFS

• Observations:
  • the last node visited is the first node from which to proceed.
  • Also, the backtracking proceeds on the basis of "last visited, first to backtrack too".
  • This suggests that a stack is the proper data structure to remember the current node and how to backtrack.

Breadth-First Search

• BFS follows the following rules:
  • Select an unvisited node x, visit it, have it be the root in a BFS tree being formed. Its level is called the current level.
  • From each node z in the current level, in the order in which the level nodes were visited, visit all the unvisited neighbors of z. The newly visited nodes from this level form a new level that becomes the next current level.
  • Repeat step 2 until no more nodes can be visited.
  • If there are still unvisited nodes, repeat from Step 1.

Implementation of BFS

• Observations:
  • the first node visited in each level is the first node from which to proceed to visit new nodes.
  • This suggests that a queue is the proper data structure to remember the order of the steps.

Minimum Spanning Trees

• A minimum spanning tree is a subgraph of an undirected weighted graph G, such that
  • it is a tree (i.e., it is acyclic)
  • it covers all the vertices V
  • contains |V| - 1 edges
  • the total cost associated with tree edges is the minimum among all possible spanning trees
  • not necessarily unique

Applications of MST

• Any time you want to visit all vertices in a graph at minimum cost (e.g., wire routing on printed circuit boards, sewer pipe layout, road planning…)
• Internet content distribution
  • Publisher produces web pages, content distribution network replicates web pages to many locations so consumers can access at higher speed
  • MST may not be good enough!
    • content distribution on minimum cost tree may take a long time!
• Provides a heuristic for traveling salesman problems(NP-hard).
  • The optimum traveling salesman tour is at most twice the length of the minimum spanning tree.

Prim’s Algorithm

• Initialization:
  • Pick a vertex r to be the root
  • Set D(r) = 0, parent(r) = null
  • For all vertices v Î V, v ¹ r, set D(v) = ¥
  • Insert all vertices into an ordered list P, using distances as the keys
• While P is not empty:
  1. Select the next vertex u to add to the tree
     • u = P.deleteMin()
  2. Update the weight of each vertex w adjacent to u which is not in the tree (i.e., w Î P)
     • If weight(u,w) < D(w),
       • parent(w) = u
       • D(w) = weight(u,w)
       • Update the ordered list to reflect new distance for w

Kruskal’s algorithm

• Initialization
  • Create a set for each vertex v Î V
  • Initialize the set of “safe edges” A comprising the MST to the empty set
  • Sort edges by increasing weight
• For each edge (u,v) Î E in increasing order while more than one set remains:
  • If u and v, belong to different sets U and V
    • add edge (u,v) to the safe edge set A = A È {(u,v)}
    • merge the sets U and V. F = F - U - V + (U È V)
  • Return A
• Running time bounded by sorting (or findMin)
• O(|E|log|E|), or equivalently, O(|E|log|V|)

Greedy Approach

• Both Prim’s and Kruskal’s algorithms are greedy algorithms
• The greedy approach works for the MST problem; however, it does not work for many other problems!