Graphs

9.1 Introduction

A graph G consists of a set V, whose members are called vertices of G, together with a set E of pairs of distinct vertices from V. These pairs are called the edges of G. If the pairs are unordered then G is called undirected Graph and if they are in order they are called Directed or digraphs.

9.2 Computer Representation of Graphs

1. The set representation
2. Adjacency Table or Adjacency Matrix
3. Adjacency List
a. Linked Implementation
b. Contiguous List
c. Mixed Implementation

9.3 Operations on Graphs
1. Breadth First Traversal
2. Depth First traversal

Experiment 27

Aim –Write a program to execute a Breadth First search on a Graph G beginning at A

Algorithm -

1. Initialize all node to ready state (Status = 1)
2. Put the starting node A in Queue and change its state to waiting (status = 2)
3. Repeat steps 4 and 5 until queue is empty
4. Remove the first node N of queue. Process N and change its status to processed state (status=3)
5. Add to the rear of queue all the neighbors of N that are in the ready state (status=1)
and change their status to waiting (status=2)
[End of Step 2 Loop]
6. Exit

Experiment 28


Aim –Write a program to execute a Depth First search on a Graph G beginning at A

Algorithm –

1. Initialize all nodes to ready state (Status = 1)
2. Push the starting node A in Queue and change its state to waiting (status = 2)
3. Repeat steps 4 and 5 until stack is empty
4. Pop the Top node N of stack . Process N and change its status to processed state (status=3)
5. Push onto stack all the neighbors that are in the ready state (status=1)
and change their status to waiting (status=2)
[End of Step 3 Loop]
6. Exit


9.4 Viva Voice

1. Define graph, directed and undirected graph?
2. Define the following:
a. Adjacent vertices
b. Path
c. Cycle
d. Connected graph
e. Degree
f. Complete graph
g. Weighted graph
3. How the graph is represented in computers memory?
4. What do you mean by graph traversal? What are different traversal methods of graph?
5. Minimum spanning tree are designed on directed or undirected graph?
6. What must a graph look like if a row of its matrix consists only of zeros?