Advanced Data Structures using ‘C’ - Graphs and their Applications – I

Advanced Data Structures using ‘C’ Unit 3

Unit 3 Graphs and their Applications – I Structure:
3.1 Introduction to Graphs
3.2 Representation
3.3 Examples of Graph Problems
3.3.1 Telecommunication
3.3.2 Sample Problem: Riding The Fences
3.3.3 Knight moves
3.3.4 Overfencing
Self Assessment Questions
3.4 Terminology
3.5 Directed Graph
3.6 Paths
3.7 Graph Representation
3.7.1 Edge List
3.7.2 Adjacency Matrix
3.7.3 Adjacency List
3.7.4 Implicit Representation
Self Assessment Questions
3.8 Connectedness
3.9 Sub graphs
3.10 Special Graphs
3.10.1 Rooted tree
3.10.2 Forest
3.10.3 Complete Graph
3.10.4 Bipartite Graph
Self Assessment Questions
3.11 Uninformed Search
3.11.1 Breadth-first search
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 75
3.11.2 Uniform-cost search
3.11.3 Depth-first search
3.11.4 Depth-limited search
3.11.5 Iterative deepening search
3.11.6 Bidirectional search
Self Assessment Questions 3.12 Summary 3.13 Terminal Questions
3.1 Introduction to Graphs
A graph is a collection of vertices V and a collection of edges E consisting of pairs of vertices. Think of vertices as locations. The set of vertices is the set of all the possible locations. In this analogy, edges represent paths between pairs of those locations. The set E contains all the paths between the locations.
3.2 Representation
The graph is normally represented using that analogy. Vertices are points or circles, edges are lines between them. In this example graph: V = {1, 2, 3, 4, 5, 6} E = {(1,3), (1,6), (2,5), (3,4), (3,6)}.
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 76
Each vertex is a member of the set V. A vertex is sometimes called a node. Each edge is a member of the set E. Note that some vertices might not be the end point of any edge. Such vertices are termed isolated. Sometimes, numerical values are associated with edges, specifying lengths or costs; such graphs are called edge-weighted graphs (or weighted graphs). The value associated with an edge is called the weight of the edge. A similar definition holds for node-weighted graphs.
3.3 Examples of Graph Problems
3.3.1 Telecommunication
Given a set of computers and a set of wires running between pairs of computers, what is the minimum number of machines whose crash causes two given machines to be unable to communicate? (The two given machines will not crash.) Graph: The vertices of the graph are the computers. The edges are the wires between the computers. Graph problem: minimum dominating sub-graph.
3.3.2 Sample Problem: Riding The Fences
Farmer John owns a large number of fences, which he must periodically check for integrity. He keeps track of his fences by maintaining a list of points at which fences intersect. He records the name of the point and the one or two fence names that touch that point. Every fence has two end points, each at some intersection point, although the intersection point may be the end point of only one fence.
Given a fence layout, calculate if there is a way for Farmer John to ride his horse to all of his fences without riding along a fence more than once. Farmer John can start and finish anywhere, but cannot cut across his fields (i.e., the only way he can travel between the intersection points is along a fence). If there is a way, find one way.
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 77
Graph: Farmer John starts at intersection points and travels between the
points along fences. Thus, the vertices of the underlying graph are the
intersection points, and the fences represent edges. Graph problem:
Traveling Salesman Problem.
3.3.3 Knight moves
Given: Two squares on an 8x8 chessboard. Determine the shortest
sequence of knight moves from one square to the other.
Graph: The graph here is harder to see. Each location on the chessboard
represents a vertex. There is an edge between two positions if it is a legal
knight move. Graph Problem: Single Source Shortest Path.
3.3.4 Overfencing
Farmer John created a huge maze of fences in a field. He omitted two
fence segments on the edges, thus creating two “exits'' for the maze. The
maze is a “perfect'' maze; you can find a way out of the maze from any point
inside it.
Given the layout of the maze, calculate the number of steps required to exit
the maze from the “worst'' point in the maze (the point that is “farther'' from
either exit when walking optimally to the closest exit).
Here's what one particular W=5, H=3 maze looks like:
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 78
Graph: The vertices of the graph are positions in the grid. There is an edge between two vertices if they represent adjacent positions that are not separated by a wall. Graph problem: Shortest Path. Self Assessment Questions
1. What do you mean by a Graph? How graphs are represented? Explain.
2. What are various applications of Graph Data Structure? Discuss.
3.4 Terminology
An edge is a self-loop if it is of the form (u,u). The sample graph contains no self-loops. A graph is simple if it neither contains self-loops nor contains an edge that is repeated in E. A graph is called a multigraph if it contains a given edge more than once or contain self-loops. For our discussions, graphs are assumed to be simple. The example graph is a simple graph. An edge (u,v) is incident to both vertex u and vertex v. For example, the edge (1,3) is incident to vertex 3. The degree of a vertex is the number of edges which are incident to it. For example, vertex 3 has degree 3, while vertex 4 has degree 1. Vertex u is adjacent to vertex v if there is some edge to which both are incident (that is, there is an edge between them). For example, vertex 2 is adjacent to vertex 5. A graph is said to be sparse if the total number of edges is small compared to the total number possible ((N x (N-1))/2) and dense otherwise. For a given graph, whether it is dense or sparse is not well-defined.
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 79
3.5 Directed Graph
Graphs described thus far are called undirected, as the edges go `both ways'. So far, the graphs have connoted that if one can travel from vertex 1 to vertex 3, one can also travel from vertex 1 to vertex 3. In other words, (1,3) being in the edge set implies (3,1) is in the edge set. Sometimes, however, a graph is directed, in which case the edges have a direction. In this case, the edges are called arcs. Directed graphs are drawn with arrows to show direction.
The out-degree of a vertex is the number of arcs which begin at that vertex. The in-degree of a vertex is the number of arcs which end at that vertex. For example, vertex 6 has in-degree 2 and out-degree 1. A graph is assumed to be undirected unless specifically called a directed graph.
3.6 Paths
A path from vertex u to vertex x is a sequence of vertices (v 0, v 1, ..., v k) such that v 0 = u and v k = x and (v 0, v 1) is an edge in the graph, as is (v 1, v 2), (v2, v 3), etc. The length of such a path is k.
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 80
For example, in the undirected graph above, (4, 3, 1, 6) is a path. This path is said to contain the vertices v 0, v 1, etc., as well as the edges (v 0, v 1), (v 1, v 2), etc. Vertex x is said to be reachable from vertex u if a path exists from u to x. A path is simple if it contains no vertex more than once. A path is a cycle if it is a path from some vertex to that same vertex. A cycle is simple if it contains no vertex more than once, except the start (and end) vertex, which only appears as the first and last vertex in the path. These definitions extend similarly to directed graphs (e.g., (v 0, v 1), (v 1, v 2), etc. must be arcs).
3.7 Graph Representation
The choice of representation of a graph is important, as different representations have very different time and space costs. The vertices are generally tracked by numbering them, so that one can index them just by their number. Thus, the representations focus on how to store the edges.
3.7.1 Edge List
The most obvious way to keep track of the edges is to keep a list of the pairs of vertices representing the edges in the graph. This representation is easy to code, fairly easy to debug, and fairly space efficient. However, determining the edges incident to a given vertex is expensive, as is determining if two vertices are adjacent. Adding an edge is quick, but deleting one is difficult if its location in the list is not known. For weighted graphs, this representation also keeps one more number for each edge, the edge weight. Extending this data structure to handle directed graphs is straightforward. Representing multigraphs is also trivial.
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 81
Example The sample undirected graph might be represented as the following list of edges:
V1
V2
e1
4
3
e2
1
3
e3
2
5
e4
6
1
e5
3
6
3.7.2 Adjacency Matrix
A second way to represent a graph utilized an adjacency matrix. This is a N by N array (N is the number of vertices). The i,j entry contains a 1 if the edge (i,j) is in the graph; otherwise it contains a 0. For an undirected graph, this matrix is symmetric. This representation is easy to code. It's much less space efficient, especially for large, sparse graphs. Debugging is harder, as the matrix is large. Finding all the edges incident to a given vertex is fairly expensive (linear in the number of vertices), but checking if two vertices are adjacent is very quick. Adding and removing edges are also very inexpensive operations. For weighted graphs, the value of the (i,j) entry is used to store the weight of the edge. For an unweighted multigraph, the (i,j) entry can maintain the number of edges between the vertices. For a weighted multigraph, it's harder to extend this.
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 82
Example The sample undirected graph would be represented by the following adjacency matrix:
V1
V2
V3
V4
V5
V6
V1
0
0
1
0
0
1
V2
0
0
0
0
1
0
V3
1
0
0
1
0
1
V4
0
0
1
0
0
0
V5
0
1
0
0
0
0
V6
1
0
1
0
0
0
It is sometimes helpful to use the fact that the (i,j) entry of the adjacency matrix raised to the k-th power gives the number of paths from vertex i to vertex j consisting of exactly k edges.
3.7.3 Adjacency List
The third representation of a matrix is to keep track of all the edges incident to a given vertex. This can be done by using an array of length N, where N is the number of vertices. The i-th entry in this array is a list of the edges incident to i-th vertex (edges are represented by the index of the other vertex incident to that edge).
This representation is much more difficult to code, especially if the number of edges incident to each vertex is not bounded, so the lists must be linked lists (or dynamically allocated). Debugging this is difficult, as following linked lists is more difficult. However, this representation uses about as much memory as the edge list. Finding the vertices adjacent to each node is very cheap in this structure, but checking if two vertices are adjacent requires checking all the edges adjacent to one of the vertices. Adding an edge is easy, but deleting an edge is difficult, if the locations of the edge in the
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 83
appropriate lists are not known. Extend this representation to handle weighted graphs by maintaining both the weight and the other incident vertex for each edge instead of just the other incident vertex. Multigraphs are already representable. Directed graphs are also easily handled by this representation, in one of several ways: store only the edges in one direction, keep a separate list of incoming and outgoing arcs, or denote the direction of each arc in the list. Example The adjacency list representation of the example undirected graph is as follows:
Vertex
Adjacent Vertices
1
3, 6
2
5
3
6, 4, 1
4
3
5
2
6
3, 1
3.7.4 Implicit Representation
For some graphs, the graph itself does not have to be stored at all. For example, for the Knight moves and Overfencing problems, it is easy to calculate the neighbors of a vertex, check adjacency, and determine all the edges without actually storing that information, thus, there is no reason to actually store that information; the graph is implicit in the data itself. If it is possible to store the graph in this format, it is generally the correct thing to do, as it saves a lot on storage and reduces the complexity of your code, making it easy to both write and debug.
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 84
If N is the number of vertices, M the number of edges, and d max the maximum degree of a node, the following table summarizes the differences between the representations:
Efficiency
Edge List
Adj Matrix
Adj List
Space
2*M
N^2
2xM
Adjacency Check
M
1
d max
List of Adjacent Vertices
M
N
d max
Add Edge
1
1
1
Delete Edge
M
2
2*d max
Self Assessment Question
1. What are various Graph representation schemes? Discuss.
2. Explain the following
i. Self-loop in Graph
ii. Simple Graphs
iii. Multi-graph
iv. Incident
v. Sparse Graph
3. What is a Directed Graph? Explain with example.
3.8 Connectedness 
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 85
An undirected graph is said to be connected if there is a path from every vertex to every other vertex. The example graph is not connected, as there is no path from vertex 2 to vertex 4. However, if you add an edge between vertex 5 and vertex 6, then the graph becomes connected. A component of a graph is a maximal subset of the vertices such that every vertex is reachable from each other vertex in the component. The original example graph has two components: {1, 3, 4, 6} and {2, 5}. Note that {1, 3, 4} is not a component, as it is not maximal. A directed graph is said to be strongly connected if there is a path from every vertex to every other vertex. A strongly connected component of a directed graph is a vertex u and the collection of all vertices v such that there is a path from u to v and a path from v to u.
3.9 Subgraphs
Graph G' = (V', E') is a subgraph of G = (V, E) if V' is a subset of V and E' is a subset of E. The subgraph of G induced by V' is the graph (V', E'), where E' consists of all the edges of E that are between members of V'. For example, for V' = {1, 3, 4, 2}, the subgraph is like the one shown ->
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 86
3.10 Special Graphs
An undirected graph is said to be a tree if it contains no cycles and is connected.
3.10.1 Rooted tree
Many trees are what is called rooted, where there is a notion of the "top" node, which is called the root. Thus, each node has one parent, which is the adjacent node which is closer to the root, and may have any number of children, which are the rest of the nodes adjacent to it. The tree above was drawn as a rooted tree.
3.10.2 Forest
An undirected graph which contains no cycles is called a forest. A directed acyclic graph is often referred to as a dag.
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 87
3.10.3 Complete Graph
A graph is said to be complete if there is an edge between every pair of vertices.
3.10.4 Bipartite Graph
A graph is said to be bipartite if the vertices can be split into two sets V1 and V2 such there are no edges between two vertices of V1 or two vertices of V2. Self Assessment Question
1. What do you mean by a Connected Graph? Differentiate a connected and strongly connected Graph.
2. Explain a Subgraph with suitable example.
3. Explain the following:
i. Rooted Graph
ii. Bipartite Graph
iii. Forest
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 88
3.11 Uninformed Search
Searching is a process of considering possible sequences of actions, first you have to formulate a goal and then use the goal to formulate a problem. A problem consists of four parts: the initial state, a set of operators, a goal test function, and a path cost function. The environment of the problem is represented by a state space. A path through the state space from the initial state to a goal state is a solution. In real life most problems are ill-defined, but with some analysis, many problems can fit into the state space model. A single general search algorithm can be used to solve any problem; specific variants of the algorithm embody different strategies. Search algorithms are judged on the basis of completeness, optimality, time complexity, and space complexity. Complexity depends on b, the branching factor in the state space, and d, the depth of the shallowest solution. Completeness: is the strategy guaranteed to find a solution when there is one? Time complexity: how long does it take to find a solution? Space complexity: how much memory does it need to perform the search? Optimality: does the strategy find the highest-quality solution when there are several different solutions? This 6 search type below (there are more, but we only show 6 here) classified as uninformed search, this means that the search have no information about the number of steps or the path cost from the current state to the goal - all they can do is distinguish a goal state from a non-goal state. Uninformed search is also sometimes called blind search. The 6 search type are listed below:
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 89
3.11.1 Breadth-first search
expands the shallowest node in the search tree first. It is complete, optimal for unit-cost operators, and has time and space complexity of O(b^d). The space complexity makes it impractical in most cases. Using BFS strategy, the root node is expanded first, then all the nodes generated by the root node are expanded next, and their successors, and so on. In general, all the nodes at depth d in the search tree are expanded before the nodes at depth d+1. Algorithmically: BFS(G,s) { initialize vertices; Q = {s]; while (Q not empty) { u = Dequeue(Q); for each v adjacent to u do { if (color[v] == WHITE) { color[v] = GRAY; d[v] = d[u]+1; // compute d[] p[v] = u; // build BFS tree Enqueue(Q,v); } } color[u] = BLACK; } BFS runs in O(V+E) Note: BFS can compute d[v] = shortest-path distance from s to v, in terms of minimum number of edges from s to v (un-weighted graph). Its breadth-first tree can be used to represent the shortest-path.
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 90
3.11.2 Uniform-cost search
expands the least-cost leaf node first. It is complete, and unlike breadth-first search is optimal even when operators have differing costs. Its space and time complexity are the same as for BFS. BFS finds the shallowest goal state, but this may not always be the least-cost solution for a general path cost function. UCS modifies BFS by always expanding the lowest-cost node on the fringe.
3.11.3 Depth-first search
expands the deepest node in the search tree first. It is neither complete nor optimal, and has time complexity of O(b^m) and space complexity of O(bm), where m is the maximum depth. In search trees of large or infinite depth, the time complexity makes this impractical. DFS always expands one of the nodes at the deepest level of the tree. Only when the search hits a dead end (a non-goal node with no expansion) does the search go back and expand nodes at shallower levels. Algorithmically:
DFS(G) { for each vertex u in V color[u] = WHITE; time = 0; // global variable for each vertex u in V if (color [u] == WHITE) DFS_Visit(u); } DFS_Visit(u) { color[u] = GRAY; time = time + 1; // global variable d[u] = time; // compute discovery time d[]
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 91
for each v adjacent to u if (color[v] == WHITE) { p[v] = u; // build DFS-tree DFS_Visit(u); } color[u] = BLACK; time = time + 1; // global variable f[u] = time; // compute finishing time f[] } DFS runs in O(V+E) DFS can be used to classify edges of G: 1. Tree edges: edges in the depth-first forest 2. Back edges: edges (u,v) connecting a vertex u to an ancestor v in a depth-first tree 3. Forward edges: non-tree edges (u,v) connecting a vertex u to a descendant v in a depth-first tree b. Cross edges: all other edges An undirected graph is acyclic iff a DFS yields no back edges.
3.11.4 Depth-limited search
places a limit on how deep a depth-first search can go. If the limit happens to be equal to the depth of shallowest goal state, then time and space complexity are minimized. DLS stops to go any further when the depth of search is longer than what we have defined.
3.11.5 Iterative deepening search
calls depth-limited search with increasing limits until a goal is found. It is complete and optimal, and has time complexity of O(b^d)
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 92
IDS is a strategy that sidesteps the issue of choosing the best depth limit by trying all possible depth limits: first depth 0, then depth 1, then depth 2, and so on. In effect, IDS combines the benefits of DFS and BFS.
3.11.6 Bidirectional search
can enormously reduce time complexity, but is not always applicable. Its memory requirements may be impractical. BDS simultaneously search both forward form the initial state and backward from the goal, and stop when the two searches meet in the middle, however search like this is not always possible. Self Assessment Questions
1. What are the criterions for evaluation of a Search Algorithm? Discuss.
2. What are various types of Blind Search or un-informed search? Explain.
3.12 Summary
Graphs is a collection of vertices and edges. Graphs are useful in solving the problems of telecommunication networks, computer networks, logical problems like knight moves in a 8x8 chess board etc, Directed or undirected graphs are usually used for different practical problems. Adjacency matrix representation of undirected graph is easy to code. Edge list and Adjacency list were other methods used to represent the undirected graphs. Searching is a process of considering possible sequences of actions. Search algorithms were judged on the basis of completeness, optimality, time complexity and space complexity parameters.
Advanced Data Structures using ‘C’ Unit 3
Sikkim Manipal University Page No.: 93
3.13 Terminal Questions
1. Draw the adjacency matrix and adjacency list representations of a complete tree with seven nodes and directed edges.
2. Draw the adjacency matrix and adjacency list representations of the directed graph shown below in figure 3.
3. Is the transitive closure of an undirected graph a representation of an equivalence relation? Explain.
4. Suppose that we use an n x n Boolean matrix to represent the edges of a directed graph. Assume as well that the diagonal elements are all true. How should we interpret the nth power of the adjacency matrix?
5. For the graph in figure 3 below show the output of a breadth-first search.