UNIT IV

Non Linear Data Structures – Graphs

Definition – Representation of Graph – Types of graph - Breadth-first traversal - Depth-

first traversal – Topological Sort – Bi-connectivity – Cut vertex – Euler circuits –
Applications of graphs.

PART A
1. Write the definition of weighted graph?
A graph in which weights are assigned to every edge is called a weighted graph.

2. Define Graph?
A graph G consist of a nonempty set V which is a set of nodes of the graph, a set E which
is the set of edges of the graph, and a mapping from the set of edges E to set of pairs of elements
of V. It can also be represented as G=(V, E).

3. Define adjacency matrix?

The adjacency matrix is an n x n matrix A whose elements aij are given by
aij = 1 if (vi, vj) Exists, =0 otherwise

4. Define adjacent nodes?

Any two nodes, which are connected by an edge in a graph, are called adjacent nodes.
For example, if an edge x E is associated with a pair of nodes (u,v) where u, v V, then we say that
the edge x connects the nodes u and v.

5. What is a directed graph?

A graph in which every edge is directed is called a directed graph.

6. What is an undirected graph?

A graph in which every edge is undirected is called an undirected graph.

7. What is a loop?
An edge of a graph, which connects to itself, is called a loop or sling.

8. What is a simple graph?

A simple graph is a graph, which has not more than one edge between a pair of nodes.

9. What is a weighted graph?

A graph in which weights are assigned to every edge is called a weighted graph.

10. Define indegree and out degree of a graph?

In a directed graph, for any node v, the number of edges, which have v as their initial node, is
called the out degree of the node v.

Outdegree: Number of edges having the node v as root node is the outdegree of the node v.
11. Define path in a graph?
The path in a graph is the route taken to reach terminal node from a starting node.

12. What is a simple path?

i. A path in a diagram in which the edges are distinct is called a simple path.
ii. It is also called as edge simple.
13. What is a cycle or a circuit?
A path which originates and ends in the same node is called a cycle or circuit.

14. What is an acyclic graph?

A simple diagram, which does not have any cycles, is called an acyclic graph.

15. What is meant by strongly connected in a graph?

An undirected graph is connected, if there is a path from every vertex to every other vertex.
A directed graph with this property is called strongly connected.
16. When a graph said to be weakly connected?

When a directed graph is not strongly connected but the underlying graph is connected, then the
graph is said to be weakly connected.

17. Name the different ways of representing a graph? Give examples (Nov 10)

a. Adjacency matrix
b. Adjacency list

18. What is an undirected acyclic graph?

When every edge in an acyclic graph is undirected, it is called an undirected acyclic graph. It
is also called as undirected forest.

19. What is meant by depth?

The depth of a list is the maximum level attributed to any element with in the list or with in
any sub list in the list.

20. What is the use of BFS?

BFS can be used to find the shortest distance between some starting node and the remaining
nodes of the graph. The shortest distance is the minimum number of edges traversed in order to
travel from the start node the specific node being examined.

21. What is topological sort?

It is an ordering of the vertices in a directed acyclic graph, such that: If there is a path from u
to v, then v appears after u in the ordering.
 22. Write BFS algorithm

1. Initialize the first node’s dist number and place in queue

2. Repeat until all nodes have been examined

3. Remove current node to be examined from queue

4. Find all unlabeled nodes adjacent to current node

5. If this is an unvisited node label it and add it to the queue

6. Finished.

23. Define biconnected graph?

A graph is called biconnected if there is no single node whose removal causes the graph to
break into two or more pieces. A node whose removal causes the graph to become disconnected
is called a cut vertex.

24. What are the two traversal strategies used in traversing a graph?
a. Breadth first search
b. Depth first search

25. Articulation Points (or Cut Vertices) in a Graph

A vertex in an undirected connected graph is an articulation point (or cut vertex) if removing it (and edges
through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network –
single points whose failure would split the network into 2 or more disconnected components. They are
useful for designing reliable networks
 PART B

1. How to represent graphs?

Graph Representations
Graph data structure is represented using following representations...
• Adjacency Matrix
• Adjacency List
Adjacency Matrix
Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph.
Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to
vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also
used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j
with weight w.
For example, consider the following undirected graph representation...

Directed graph representation...

Adjacency List
An array of linked lists is used. Size of the array is equal to number of vertices. Let the array
be array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This
representation can also be used to represent a weighted graph. The weights of edges can be stored
in nodes of linked lists. Following is adjacency list representation of the above graph

2. Explain BFS and DFS in detail with an example?

Graph Traversals
Graph traversal is technique used for searching a vertex in a graph. The graph traversal is also
used to decide the order of vertices to be visit in the search process.
A graph traversal finds the edges to be used in the search process without creating loops that
means using graph traversal we visit all vertices of graph without getting into looping path.
There are two graph traversal techniques and they are as follows...
1. DFS (Depth First Search)
2. BFS (Breadth First Search)

Depth First Search

The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves
exhaustive searches of all the nodes by going ahead, if possible, else by backtracking.
Here, the word backtrack means that when you are moving forward and there are no more
nodes along the current path, you move backwards on the same path to find nodes to traverse. All
the nodes will be visited on the current path till all the unvisited nodes have been traversed after
which the next path will be selected.
This recursive nature of DFS can be implemented using stacks. The basic idea is as follows:
Pick a starting node and push all its adjacent nodes into a stack. Pop a node from stack to select
the next node to visit and push all its adjacent nodes into a stack.
Repeat this process until the stack is empty.
However, ensure that the nodes that are visited are marked. This will prevent you from
visiting the same node more than once.
If you do not mark the nodes that are visited and you visit the same node more than once, you
may end up in an infinite loop.

Initialize the stack.

2
Mark S as visited and put it onto the stack. Explore any unvisited
adjacent node from S. We have three nodes and we can pick any of
them. For this example, we shall take the node in an alphabetical
order.

3
Mark A as visited and put it onto the stack. Explore any unvisited
adjacent node from A. Both Sand D are adjacent to A but we are
concerned for unvisited nodes only.

4 Visit D and mark it as visited and put onto the stack. Here, we
have B and C nodes, which are adjacent to D and both are
unvisited. However, we shall again choose in an alphabetical
order.

5
We choose B, mark it as visited and put onto the stack.
Here Bdoes not have any unvisited adjacent node. So, we
pop Bfrom the stack.

6 We check the stack top for return to the previous node and check if
it has any unvisited nodes. Here, we find D to be on the top of the
stack.

7
Only unvisited adjacent node is from D is C now. So we visit C,
mark it as visited and put it onto the stack.

As C does not have any unvisited adjacent node so we keep popping the stack until we find a
node that has an unvisited adjacent node. In this case, there's none and we keep popping until the
stack is empty.
Breadth First Search
There are many ways to traverse graphs. BFS is the most commonly used approach.
BFS is a traversing algorithm where we start traversing from a selected node (source or
starting node) and traverse the graph layer wise thus exploring the neighbour nodes (nodes which
are directly connected to source node).

We must then move towards the next-level neighbour nodes.

As the name BFS suggests,
1. First move horizontally and visit all the nodes of the current layer
2. Move to the next layer
To make this process easy, use a queue to store the node and mark it as 'visited' until all its
neighbours (vertices that are directly connected to it) are marked.
The queue follows the First In First Out (FIFO) queuing method, and therefore, the neigbors
of the node will be visited in the order in which they were inserted in the node i.e. the node that
was inserted first will be visited first, and so on.

Initialize the queue.

We start from visiting S(starting node), and mark it as visited.

3
We then see an unvisited adjacent node from S. In this example,
we have three nodes but alphabetically we choose A, mark it as
visited and enqueue it.

4
Next, the unvisited adjacent node from S is B. We mark it as
visited and enqueue it.

5
Next, the unvisited adjacent node from S is C. We mark it as
visited and enqueue it.
6
Now, S is left with no unvisited adjacent nodes. So, we dequeue
and find A.

7
From A we have D as unvisited adjacent node. We mark it as
visited and enqueue it.

At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we
keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the program
is over.
 3. Explain Bi-Connectivity and Euler Circuits?

Bi-Connectivity

Connectivity
Connectivity in an undirected graph means that every vertex can reach every other vertex via
any path. If the graph is not connected the graph can be broken down into Connected
Components.
Strong Connectivity
Strong Connectivity applies only to directed graphs. A directed graph is strongly connected if
there is a directed path from any vertex to every other vertex. This is same as connectivity in an
undirected graph, the only difference being strong connectivity applies to directed graphs and
there should be directed paths instead of just paths. Similar to connected components, a directed
graph can be broken down into Strongly Connected Components.

Articulation Point or Cut Vertex

A cut-vertex is a single vertex whose removal disconnects a graph.

In a graph, a vertex is called an articulation point if removing it and all the edges associated
with it results in the increase of the number of connected components in the graph. For example
consider the graph given in following figure.

If in the above graph, vertex 1 and all the edges associated with it, i.e. the edges 1-0, 1-2 and
1-3 are removed, there will be no path to reach any of the vertices 2, 3 or 4 from the vertices 0
and 5, that means the graph will split into two separate components. One consisting of the
vertices 0 and 5 and another one consisting of the vertices 2, 3 and 4 as shown in the following
figure.
 Likewise removing the vertex 0 will disconnect the vertex 5 from all other vertices. Hence the
given graph has two articulation points: 0 and 1.

Euler Circuits

Euler Path
An Euler path is a path that uses every edge of a graph exactly once.

Euler Circuit
An Euler circuit is a circuit that uses every edge of a graph exactly once.
An Euler path starts and ends at different vertices. An Euler circuit starts and ends at the same
vertex.
 4. State and explain topological Sort with suitable example?
Topological Sorting

Definition
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such
that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a
graph is not possible if the graph is not a DAG.
For example, a topological sorting of the following graph is “5 4 2 3 1 0”. There can be more
than one topological sorting for a graph. For example, another topological sorting of the
following graph is “4 5 2 3 1 0”. The first vertex in topological sorting is always a vertex with in-
degree as 0 (a vertex with no in-coming edges).

Topological Sort Example

Consider the following graph “D”. Find the topological ordering of this graph “G”.

Step 1: Write in-degree of all vertices:

Vertex in-degree
1 0
2 1
3 1
4 2
Step 2: Write the vertex which has in-degree 0 (zero) in solution. Here vertex 1 has in-degree 0.
So, solution is: 1 -> (not yet completed)
Step 3: Decrease in-degree count of vertices who are adjacent to the vertex which recently
added to the solution. Here vertex 1 is recently added to the solution. Vertices 2 and 3 are
adjacent to vertex 1. So decrease the in-degree count of those and update.
Updated result is:
Vertex in-degree
1 Already added to solution
2 0
3 0
4 2
Step 4: Again repeat the same thing which we have done in step1 that is, write the vertices which
have in-degree 0 in solution. Here we can observe that two vertices (2 and 3) have in- degree 0
(zero). Add any one vertex into the solution.
Note that, you may add vertex 2 into solution, and I may add vertex 3 to solution. That means
the solution to topological sorting is not unique. Now add vertex 3.
Solution is: 1->3->
Step 5: Again decrease the in-degree count of vertices which are adjacent to vertex 3.
Updated result is:

Vertex in-degree
1 Already added to solution
2 0
3 Already added to solution
4 1
Now add vertex 2 to solution because it only has in-degree 0.
Solution is: 1->3->2->
Updated result is:
Vertex in-degree
1 Already added to solution
2 Already added to solution
3 Already added to solution
4 0
Finally add 4 to solution.
Final solution is: 1->3->2->4
 5. Explain Prim’s Algorithm and kruskal’s algorithm with example?
•Prim’s algorithm is a greedy algorithm
•Used to form a minimum spanning tree for a connected weighted undirected graph.
•Builds a tree that includes every vertex and a subset of the edges in such a way that the total weight of
all the edges in the tree is minimized.
•Tree vertices Vertices that are a part of the minimum spanning tree T.
•Fringe vertices Vertices that are currently not a part of T, but are adjacent to some tree vertex.
•Unseen vertices Vertices that are neither tree vertices nor fringe vertices fall under this category.

Select a as starting vertex

KRUSKAL ALGORITHM
Step-01:
Sort all the edges from low weight to high weight.
Step-02:
Take the edge with the lowest weight and use it to connect the vertices of graph.
If adding an edge creates a cycle, then reject that edge and go for the next least weight edge.
Step-03:
Keep adding edges until all the vertices are connected and a Minimum Spanning Tree (MST) is
obtained.
 6. Write an appropriate algorithm to find the shortest path from ‘A’ to every other
node of A?

DIJIKSTRA‘S ALGORITHM

1) Single-source shortest-path problem

2) For a given vertex called the source in a weighted connected graph
i) Find shortest paths to all its other vertices.
3) The best-known algorithm for the single-source shortest-paths problem is called Dijkstra’s
algorithm.

First, it finds the shortest path from the source to a vertex nearest to it, then to a second nearest, and
so on
1) Create a set Tree Vertices that keeps track of vertices included in shortest path tree
a) Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph.
a) Initialize all distance values as INFINITE.
b) Assign distance value as 0 for the source vertex so that it is picked first.
3) While Tree Vertex doesn’t include all vertices
a) Pick a vertex u which is not there in Tree Vertex and has minimum distance value.
b) Include u to Tree Vertex.
c) Update distance value of all adjacent vertices of u.
(a) For every adjacent vertex v if sum of distance value of u (from source) and
weight of edge u-v, is less than the distance value of v then update the distance
value of v.
from a to b : a - b of length 3
from a to d : a - b - d of length 5
from a to c : a - b - c of length 7
from a to e : a - b - d - e of length 9