5.
Graphs
5.1 Basic terminology:-
1. Graph :
A graph G consist of two sets V & E. set V is a finite , nonempty set of vertices
& E is a set of Pairs of vertices called edges.
i.e. G=(V , E)
2. Undirected Graph:-
A graph in which pair of vertices representing any edge is unordered i.e. (1,2),
(2,1) represent the same edge.
V(G1)={ 1, 2, 3, 4}
E(G1)={(1,2),(2,1),(3,2),(2,3),(2,4),(4,2),(4,3),(3,4),(1.3),(3,1)}
3. Directed graph:-
A graph in which each edge is represented by a directed pair < a,b>. where a is
tail & b is head of the edge <a,b> & <b,a> are two different edges directed graph
is also called digraph.
V(G1)={1,2,3}
E(G1)={<1,2>, <2,1>, <1,3>, <3,2>}
4. Adjacent vertices:-
- Vertex V1 is said to be adjacent to a vertex V2.
- If there is an edge(V1,V2) or (V2,V1)
- Vertices adjacent to node 2 are node 1& node 3 & another one is vertices
adjacent to node 4 are node 1& node 3.
5. Path:-
A path from vertex W is a sequence of vertices , each adjacent to the next consider
the below graph again node 1,node 2 and node 3 is a path & node 1,node 4 and
node 3 is also a path.
6. Cycle:-
A cycle is a path in which first & last vertices are the same. In below graph the
node 1 , node 2, node 3, node 4, node 1 is a cycle.
7. Connected graph:-
- A graph is called connected if there exists a path from any vertex to any
other vertex.
- Inordr to make it connected graph connect node 1 to node 4 & node 3 to
node 5, thus it becomes a connected graph.
8. Degree:-
- The number of edges incident on a vertex determine its degree
- The degree of vertex u ,is written as degree (u).
- If degree (u) =0 , this means that vertex u does not belong to any edge, then
vertex u is called isolated vertex.
- In a directed graph (Digraph). We attach indegree & an outdegree to each
of the vertices, Indegree of vertex 3 is 2 & Outdegree is 1.
9. Complete graph:-
- A graph is said to complete or fully connected if there is path from every
vertex to every other vertex.
𝐧(𝐧−𝟏)
- A complete graph with n vertices will have edges.
𝟐
10. Weighted gaph:-
- A graph is said to be weighted graph if every edge in the graph is assigned
some weigh or value
- The weight of the edge is a positive value that may be representing the cost
of moving along the edge or distance between the vertices.
5.2 Graph representation:-
There are several representation method for representing a graph.
1. Matrix representation:-
- Consider a graph g with set of vertices V(G) & set of edges E(G).
- If there are N nodes in V(G), for N >=1 , the graph G may be represented
by an adjacency matrix which is a table with N rows & N columns with the
property that
- A(i , j) = 1 , if & only if there is an edge (Vi, Vj) between i & j
=0 , otherwise
- If there is an edge connecting Vi & Vj in E(G) , the value in the [I ,j]
position in the table is 1, otherwise it is 0.
- For undirected graph shown in figure-A & the matrix representation for
undirected graph is shown in figure-B
Figure-A:- Undirected graph
Figure-B:- Undirected graph & matrix representation
- For directed graph shown in figure-C & the matrix representation for
directed graph is shown in figure-D
Figure:-C:- Directed Graph
Figure-D:- Matrix representation
- For weighted graph shown in figure-E & the matrix representation for
weighted graph is shown in figure-F
Figure:-E:- Weighted Graph
Figure-F:- Matrix representation
2. Adjacency lists:-
- The use of adjacency matrix to represent a graph is inefficient due
to its static implementation, which requires advance knowledge of
number of nodes.
- The solution to this problem is to use a linked structure, which
allocates & deallocates whenever required.
- Graph can be represent using adjacency list.
- This adjacency list stores information about only those edges which
are present in the graph.
- All the vertices are stored in a list & for each vertex , there is a linked
list of its adjacency vertices.
- The list contains header node pointing to the linked list of vertices.
- If there is not going edge from a vertex then the header pointer for
that vertex contains NULL.
- Figure –A shows directed graph & figure-B adjacency list
representation.
Figure –A shows directed graph
Figure-B:- adjacency linked-list representation.
- Figure –C shows undirected graph & figure-D adjacency list representation
Figure –C :-undirected graph
Figure-D:- adjacency linked-list representation
5.3 Graph traversal;:-
Many applications requires us to visit all the vertices in a graph
In case of all the data structure we have studied till now, including tree
We have a starting node with which we can start traversing the data
structure.
In case of graph there is no such starting node; we can specify any arbitrary
nodes as the starting nodes
Basically given an undirected graph G= (V, E) 7 vertex V in V9G).
We want to visit all vertices in G that are reachable from V which mean,
we are interested in visiting all the vertices which are connected to vertex
V.
There are many possible orders for visiting the vertices of the graph.
We shall look two ways
1) Depth first Search
2) Breadth First Search
1. Depth First Search (DFS)
- 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.
- It employs the following rules.
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it.
Push it in a stack.
Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It
will pop up all the vertices from the stack, which do not have adjacent
vertices.)
Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.
E.g.:-
Step-1:- Initialize the stack.
Step-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.
Step-3:- Mark A as visited and put it onto the stack. Explore any unvisited
adjacent node from A. Both S and D are adjacent to A but we are concerned for
unvisited nodes only.
Step-4:- Visit D and mark it as visited and put onto the stack. Here, we
have Band C nodes, which are adjacent to D and both are unvisited. However, we
shall again choose in an alphabetical order.
Step-5:- We choose B, mark it as visited and put onto the stack. Here B does not
have any unvisited adjacent node. So, we pop B from the stack.
Step-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.
Step-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
2. Breadth first search:-
- Breadth First Search (BFS) algorithm traverses a graph in a breadthward
motion and uses a queue to remember to get the next vertex to start a search,
when a dead end occurs in any iteration.
- 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.
- As in the example given above, BFS algorithm traverses from A to B to E
to F first then to C and G lastly to D. It employs the following rules.
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it.
Insert it in a queue.
Rule 2 − If no adjacent vertex is found, remove the first vertex from the
queue.
Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.
E.g.:-
Step-1:- Initialize the queue.
Step-2:- We start from visiting S (starting node), and mark it as visited.
Step3:- 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.
Step4:- Next, the unvisited adjacent node from S is B. We mark it as visited and
enqueue it.
Step5:- Next, the unvisited adjacent node from S is C. We mark it as visited and
enqueue it.
Step6:- Now, S is left with no unvisited adjacent nodes. So, we dequeue and
find A.
Step7:- From A we have D as unvisited adjacent node. We mark it as visited and
enqueue it.