1

GRAPHS

A graph ‘G’ consists of nonempty set ‘V’ called the 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 a set of pair of elements of V. We can write a graph G=(V,E)
then V and E of a graph are finite.
In a graph G=(V,E) an edge which is directed from one node to another is called a directed edge, while an edge
which has no specific direction is called an undirected edge. A graph in which every edge is directed is called a
directed graph or digraph. A graph in which every edge is undirected is called undirected graph. If some of
the edges are directed and some are undirected in a graph then the graph is a mixed graph. A graph in which
weights are assigned to every edge is called a weighted 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. The number of edges which have v as their terminal node is called the in degree of the
node v, and the sum of the out degree and in degree of a node v is called the total degree. The number of edges
appearing in the sequence of a path is called the length of the path.
Graph can be represented in 3 ways namely (i) Adjacencty matrix (ii) Linked List and (iii) Adjacency Multi list.
Adjacency matrix representation: Graph can be represented in a two dimensional array, which is
adjacency matrix with N rows and N columns. A[i][j] will be assigned to 1 if there is an edge connecting V i and
Vj in E; otherwise it will be 0. The adjacency matrix for the following graph is:

1 2

3 4

Adjacency matrix for the above graph is

1 2 3 4

1 0 1 1 1

2 1 0 1 1

3 1 1 0 1

1 1 1 0
4

Linked List Representation: The adjacency list stores the information about those edges that exists. The adjacency list
contains a directory and a set of linked lists. The directory contains one entry for each node. Each node of the linked list
has three fields. Those are node identifier link to the next field, weigth of the edge. The adjacency list for the above graph.

(iii) Multi list representation: it consists of two parts a directory of node information and a set of linked list of edge
information. The node directory contains one entry for each node.
 2

Graph Traversal

The breadth first search (BFS) and the depth first search (DFS) are the two algorithms used for traversing and
searching a node in a graph. They can also be used to find out whether a node is reachable from a given node or not.

Depth First Search (DFS)

The aim of DFS algorithm is to traverse the graph in such a way that it tries to go far from the root node. Stack is used in
the implementation of the depth first search. Let’s see how depth first search works with respect to the following graph:

As stated before, in DFS, nodes are visited by going through the depth of the tree from the starting node. If we do the depth first
traversal of the above graph and print the visited node, it will be “A B E F C D”. DFS visits the root node and then its children
nodes until it reaches the end node, i.e. E and F nodes, then moves up to the parent nodes.

Algorithmic Steps
1. Step 1: Push the root node in the Stack.
2. Step 2: Loop until stack is empty.
3. Step 3: Peek the node of the stack.
4. Step 4: If the node has unvisited child nodes, get the unvisited child node, mark it as traversed and push it on
stack.
5. Step 5: If the node does not have any unvisited child nodes, pop the node from the stack

Breadth First Search (BFS)

If we do the breadth first traversal of the above graph and print the visited node as the output, it will print the following
output. “A B C D E F”. The BFS visits the nodes level by level, so it will start with level 0 which is the root node, and then it
moves to the next levels which are B, C and D, then the last levels which are E and F.
Algorithmic Steps
Step 1: Push the root node in the Queue.
Step 2: Loop until the queue is empty.
 3

Step 3: Remove the node from the Queue.

Selection Sort
The idea of selection sort is rather simple: we repeatedly find the next largest (or smallest) element in the array and move
it to its final position in the sorted array. Assume that we wish to sort the array in increasing order, i.e. the smallest
element at the beginning of the array and the largest element at the end. We begin by selecting the largest element and
moving it to the highest index position. We can do this by swapping the element at the highest index and the largest
element. We then reduce the effective size of the array by one element and repeat the process on the smaller (sub)array.
The process stops when the effective size of the array becomes 1 (an array of 1 element is already sorted).
For example, consider the following array, shown with array elements in sequence separated by commas:

The leftmost element is at index zero, and the rightmost element is at the highest array index, in our case, 4 (the effective
size of our array is 5). The largest element in this effective array (index 0-4) is at index 2. We have shown the largest
element and the one at the highest index in bold. We then swap the element at index 2 with that at index 4. The result is:

We reduce the effective size of the array to 4, making the highest index in the effective array now 3. The largest element in
this effective array (index 0-3) is at index 1, so we swap elements at index 1 and 3 (in bold):

The next two steps give us:

The last effective array has only one element and needs no sorting. The entire array is now sorted. The algorithm for an
array, x, with lim elements is easy to write down:
for (eff_size = lim; eff_size > 1; eff_size--)
find maxpos, the location of the largest element in the effective
array: index 0 to eff_size - 1
swap elements of x at index maxpos and index eff_size - 1
The implementation of the selection sort algorithm in C, together with a driver program is shown in Figure 10.6.

ALGORITHM
 4

An algorithm is the step by step logical procedure for solving a problem. Each step is called an instruction. Algorithm can
be written in English like sentences and is called ‘pseudocode’.
All algorithms must satisfy the following properties
1. INPUT: zero or more inputs.
2. OUTPUT: at least one quantity is produces.
3. DEFINITENESS: each instruction is clear and unambiguous.
4. FINITENESS: the algorithm should terminate after a finite number of steps. It should not enter into an infinite loop.
5. EFFECTIVENESS: each operation must be simple and should complete in a finite time.
FLOWCHART: A flowchart is a pictorial representation of an algorithm. It shows flow of operations in pictorial form and and any
error in the logic of the problem can be detected very easily. A flowchart uses different shapes of boxes and symbols to denote
different types of instructions. These symbols are connected by solid lines with arrow marks to indicate the operation flow.
Flow chart symbols:
1. Terminal: the terminal (oval) symbol is used to indicate the beginning and ending and halt in the program logic.

2. Input output: the input/output (parallelogram) symbol is used to denote any function of an input/output device in the
program.

3. Processing: a processing (rectangle) symbol is used to represent arithmetic and data movement instructions.

4. Flow lines: flow lines with arrow heads are used to indicate the flow of operation, i.e. exact sequence in which the
instructions are to be executed.

5. Decision: the decision(diamond) symbol is used to indicate a point at which a decision has to be made and a branch to
one or two or more alternate points are possible.

6. Connectors: if a flow chart becomes too long to fit in a single page. A connector symbol is used to indicate a continued
flow in the next page.

7. Predefined process: the predefined process (double sided rectangle) symbol is used in flow chart to indicate that
modules are specified elsewhere.

8. Annotation: the annotation (bracket with broken line) symbol is used to indicate the descriptive comments .

----------------