1 of 32

Chapter 8: Graphs (part 2)

2 of 32

Objectives

Looking ahead – in this chapter, we’ll consider

  • Graph Representation
  • Graph Traversals
  • Shortest Paths
  • Minimum spanning trees (NOT on final exam)

​

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

3 of 32

Graph Representation

  • Graphs can be represented in a number of ways
  • One of the simplest is an adjacency list, where each vertex adjacent to a given vertex is listed
  • This can be designed as a table (known as a star representation) or a linked list, shown in Figure 8.2b-c on page 393
  • Another representation is as a matrix, which can be designed in two ways
  • An adjacency matrix is a |V| x |V| binary matrix where:

​

​

​

Data Structures and Algorithms in C++, Fourth Edition

4 of 32

Graph Representation -- Pros & Cons?

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

5 of 32

Graph Representation -- Pros and Cons?

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

6 of 32

Graph Traversals

  • Like tree traversals, graph traversals visit each node once
  • However, we cannot apply tree traversal algorithms directly to graphs because of cycles and isolated vertices
  • One algorithm for graph traversal, called the depth-first search (DFS), was developed by John Hopcroft and Robert Tarjan in 1974
    • In this algorithm, each vertex is visited and then all the unvisited vertices adjacent to that vertex are visited
    • If the vertex has no adjacent vertices, or if they have all been visited, we backtrack to that vertex’s predecessor
    • This continues until we return to the vertex where the traversal started

​

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

7 of 32

Graph Traversals

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

void Tree::preorder_search(Node & N)

{

N.visited = true;

for (each Node C that is a child of N)

preorder_search(C);

}

void Graph::DFS(Vertex & V)

{

V.visited = true;

for (each Vertex W that is a neighbor of V)

if (!W.visited)

DFS(W);

}

8 of 32

Graph Traversals

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

void Tree::preorder_search(Node & N)

{

N.visited = true;

for (each Node C that is a child of N)

preorder_search(C);

}

​

9 of 32

Graph Traversals

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

void Tree::preorder_search(Node & N)

{

N.visited = true;

for (each Node C that is a child of N)

preorder_search(C);

}

void Graph::DFS(Vertex & V)

{

V.visited = true;

for (each Vertex W neighboring V)

if (!W.visited)

DFS(W);

}

10 of 32

Graph Traversals

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

void Tree::preorder_search(Node & N)

{

N.visited = true;

for (each Node C that is a child of N)

preorder_search(C);

}

void Graph::DFS(Vertex & V)

{

V.visited = true;

for (each Vertex W neighboring V)

if (!W.visited)

DFS(W);

}

Assuming neighbors are visited in alphabetical order, what is the overall order of visitation of DFS(a)? DFS(g)?

11 of 32

Graph Traversals without Recursion

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

​

// all vertices are initially unvisited

void Graph::DFS(Vertex & start)

{

Stack<Vertex> S;

S.push(start);

while (!S.empty()) {

Vertex V = S.top(); S.pop();

if (!V.visited) {

V.visited = true;

for (each Vertex W neighboring V)

if (!W.visited)

S.push(W);

}

}

}

Assuming neighbors are visited in alphabetical order, what is the overall order of visitation of DFS(a)? DFS(g)?

12 of 32

Graph Traversals

  • Like tree traversals, graph traversals visit each node once
  • However, we cannot apply tree traversal algorithms directly to graphs because of cycles and isolated vertices
  • One algorithm for graph traversal, called the depth-first search (DFS), was developed by John Hopcroft and Robert Tarjan in 1974
    • In this algorithm, each vertex is visited and then all the unvisited vertices adjacent to that vertex are visited
    • If the vertex has no adjacent vertices, or if they have all been visited, we backtrack to that vertex’s predecessor
    • This continues until we return to the vertex where the traversal started

​

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

How to modify DFS() to make it path search between two

specific vertices? I.e., how to solve a maze?

13 of 32

Graph Traversals (continued)

  • The algorithm guarantees that we will create a tree (or a forest, which is a set of trees) including the graph’s vertices
  • Such a tree is called a spanning tree
  • The guarantee is based on the algorithm not processing any edge that leads to an already visited node
  • Consequently, some edges are not included in the tree (marked with dashed lines)
  • The edges included in the tree are called forward edges; those omitted are called back edges

​

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

14 of 32

Eulerian and Hamiltonian Graphs

  • Eulerian Graphs
    • A trail in a graph which visits every edge exactly once is called an Eulerian trail (or Eulerian path)
    • Similarly, an Eulerian trail which starts and ends on the same vertex is called an Eulerian circuit or Eulerian cycle
    • They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736

​

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

15 of 32

Eulerian and Hamiltonian Graphs�(continued)

  • Eulerian Graphs (continued)
    • Figure 8.34 shows an example of finding an Eulerian cycle

​

​

​

Fig. 8.34 Finding an Eulerian cycle

    • A test needs to be made, before an edge is chosen, to see if that edge is a bridge in the untraversed subgraph
    • If it is, it could lead to the in ability to complete the path because certain vertices could become unreachable

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

16 of 32

Eulerian and Hamiltonian Graphs�(continued)

  • Hamiltonian Graphs
    • A Hamiltonian path is a path in an undirected graph that visits each vertex exactly once
    • A Hamiltonian cycle is a Hamiltonian path that is a cycle
    • Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete
    • Knight's tour problem in chess

​

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

17 of 32

Graph Traversals: Breadth-First Search

  • Idea: visit all of the neighbors one edge away, then two edges away, and so on
  • Analogous to the level-order tree traversal

​

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

18 of 32

Breadth-First Search without Recursion

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

​

// all vertices are initially unvisited

void Graph::BFS(Vertex & start)

{

Queue<Vertex> Q;

Q.push(start);

while (!Q.empty()) {

Vertex V = Q.top(); Q.pop();

if (!V.visited) {

V.visited = true;

for (each Vertex W neighboring V)

if (!W.visited)

Q.push(W);

}

}

}

Assuming neighbors are visited in alphabetical order, what is the overall order of visitation of BFS(a)? BFS(g)?

19 of 32

Breadth-First Search: Shortest Path

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

void Graph::BFS_ShortestPath(Vertex & start)

{

Queue<Vertex> Q;

for (each Vertex V in the graph)

V.dist = INFINITY;

start.dist = 0;

start.path = NULL; // build finish to start SLL

Q.enqueue(start);

while (!Q.empty()) {

Vertex V = Q.dequeue();

for (each Vertex W neighboring V)

if (W.dist == INFINITY) { // aka not visited

W.dist = V.dist + 1;

W.path = V; // record predecessor

Q.enqueue(W);

}

}

}

20 of 32

21 of 32

Shortest Paths

  • A classical problem in graph theory is finding the shortest path between two nodes, with numerous approaches suggested
  • The edges of the graph are associated with values denoting such things as distance, time, costs, amounts, etc.
  • If we’re determining the distance between two vertices, say v and u, information about the distance between the intermediate vertices in the path, w, needs to be kept track of
  • This can be recorded as a label associated with the vertices
  • The label may simply be the distance between vertices, or the distance along with the current node’s predecessor in the path
  • Methods for finding shortest paths depend on these labels

Data Structures and Algorithms in C++, Fourth Edition

22 of 32

Shortest Paths (continued)

  • One of the first label-setting algorithms was developed by Edsgar Dijkstra in 1956
    • In this algorithm, the shortest from among a number of paths from a vertex, v, are tried
    • This means that a particular path may be extended by adding one more edge to it each time v is checked
    • However, if the path is longer than any other path from that point, it is dropped, and the other path is expanded
    • Since the vertices may have more than one outgoing edge, each new edge adds possible paths for exploration
    • Thus each vertex is visited, the new paths are started, and the vertex is then not used anymore
    • Once all the vertices are visited, the algorithm is done
  • May fail when negative weights are present

​

Data Structures and Algorithms in C++, Fourth Edition

23 of 32

Dijkstra's Shortest Path Algorithm

Data Structures and Algorithms in C++, Fourth Edition

​

​

​

​

​

​

​

​

​

void Graph::Dijkstra(Vertex & start)

{

PriorityQueue<Vertex> PQ; // min PQ on vertex dist

for (each Vertex V in the graph) {

if (V == start)

V.dist = 0; // so start will be chosen first from PQ

else

V.dist = INFINITY;

V.checked = false; V.path = NULL;

PQ.insert(V);

}

while (true) {

Vertex V = PQ.removeMin();

if (!V) return; // PQ empty, we are done

V.checked = true;

for (each Vertex W neighboring V)

if (!W.checked && W.dist > V.dist + weight(V, W)) {

W.dist = V.dist + weight(V, W); // decrease W.dist, which

W.path = V; // changes PQ placement

}

}

}

24 of 32

Example: Dijkstra's Shortest Path Algorithm

Data Structures and Algorithms in C++, Fourth Edition

Data Structures and Algorithms in C++, Fourth Edition

Execution of Dijkstra(d)

void Graph::Dijkstra(Vertex & start)

{

PriorityQueue<Vertex> PQ; // min PQ on vertex dist

for (each Vertex V in the graph) {

if (V == start)

V.dist = 0; // so start will be chosen first from PQ

else

V.dist = INFINITY;

V.checked = false; V.path = NULL;

PQ.insert(V);

}

while (true) {

Vertex V = PQ.removeMin();

if (!V) return; // PQ empty, we are done

V.checked = true;

for (each Vertex W neighboring V)

if (!W.checked && W.dist > V.dist + weight(V, W)) {

W.dist = V.dist + weight(V, W); // decrease W.dist, which

W.path = V; // changes PQ placement

}

}

}

25 of 32

Example: Dijkstra's Shortest Path Algorithm

Data Structures and Algorithms in C++, Fourth Edition

Data Structures and Algorithms in C++, Fourth Edition

void Graph::Dijkstra(Vertex & start)

{

PriorityQueue<Vertex> PQ; // min PQ on vertex dist

for (each Vertex V in the graph) {

if (V == start)

V.dist = 0; // so start will be chosen first from PQ

else

V.dist = INFINITY;

V.checked = false; V.path = NULL;

PQ.insert(V);

}

while (true) {

Vertex V = PQ.removeMin();

if (!V) return; // PQ empty, we are done

V.checked = true;

for (each Vertex W neighboring V)

if (!W.checked && W.dist > V.dist + weight(V, W)) {

W.dist = V.dist + weight(V, W); // decrease W.dist, which

W.path = V; // changes PQ placement

}

}

}

26 of 32

27 of 32

Spanning Trees

  • Consider an airline that has routes between seven cities represented as the graph in Figure 8.14a

​

​

​

​

​

Fig. 8.14 A graph representing (a) the airline connections between

seven cities and (b–d) three possible sets of connections

  • If economic hardships force the airline to cut routes, which ones should be kept to preserve a route to each city, if only indirectly?
  • One possibility is shown in Figure 8.14b

Data Structures and Algorithms in C++, Fourth Edition

28 of 32

Spanning Trees (continued)

  • However, we want to make sure we have the minimum connections necessary to preserve the routes
  • To accomplish this, a spanning tree should be used, e.g one created using DFS()
  • There is a possibility of multiple spanning trees, but each of these has the minimum number of edges
  • We don’t know which of these might be optimal, since we haven’t taken distances into account
  • The airline, wanting to minimize costs, will want to use the shortest distances for the connections
  • So what we want to find is the minimum spanning tree, where the sum of the edge weights is minimal

Data Structures and Algorithms in C++, Fourth Edition

29 of 32

Spanning Trees (continued)

  • The problem we looked at earlier involving finding a spanning tree in a simple graph is a case of this where edge weights = 1
  • So each spanning tree is a minimum tree in a simple graph
  • One popular algorithm is Kruskal’s algorithm, developed by Joseph Kruskal in 1956
  • It orders the edges by weight, and then checks to see if they can be added to the tree under construction
  • It will be added if its inclusion doesn’t create a cycle

Data Structures and Algorithms in C++, Fourth Edition

30 of 32

Spanning Trees (continued)

  • The algorithm is as follows (wording from Wikipedia):

​

​

  • Create a forest F (a set of trees), where each vertex in the graph is a separate tree
  • Create a set S containing all the edges in the graph
  • While S is nonempty and F is not yet spanning
    • Remove an edge with minimum weight from S
    • If the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree

​

At the termination of the algorithm, the forest forms a minimum spanning forest of the graph. If the graph is connected, the forest has a single component and forms a minimum spanning tree.

​

​

Data Structures and Algorithms in C++, Fourth Edition

31 of 32

Spanning Trees (continued)

  • The algorithm is as follows (adapted from Wikipedia):

​

​

algorithm Kruskal(G) is

F:= ∅

for each v ∈ G.V do

MAKE-SET(v)

for each (u, v) in G.E ordered by weight(u, v), increasing do

if FIND(u) ≠ FIND(v) then

F:= F ∪ {(u, v)} ∪ {(v, u)}

UNION(FIND-SET(u), FIND-SET(v))

return F

​

​

Data Structures and Algorithms in C++, Fourth Edition

32 of 32

Spanning Trees (continued)

  • The algorithm is as follows (adapted from Wikipedia):

​

algorithm Kruskal(G) is

F:= ∅

for each v ∈ G.V do

MAKE-SET(v)

for each (u, v) in G.E ordered by weight(u, v), increasing do

if FIND(u) ≠ FIND(v) then

F:= F ∪ {(u, v)} ∪ {(v, u)}

UNION(FIND-SET(u), FIND-SET(v))

return F

​

​

Data Structures and Algorithms in C++, Fourth Edition