This is the second part of article names GRAPH. Click on graph and read that article first.

Graph Traversals

A graph traversal means visiting all the nodes of the graph. There are two main graph traversal methods:

1.    Breadth First Search
2.    Depth First Search

Breadth First Search

In breadth first search, one node is selected as the start position. It is visited first and marked and then all adjacent nodes to that node are visited and marked in some sequential order. Once this is done, all remaining unvisited nodes immediately adjacent to these nodes are visited and marked. This process goes on until the entire graph has been traversed.

Consider the graph shown in figure-10. Initially all the nodes are assigned False (0) then the initial state will look like, as shown in figure-11. Let we start with A. Its adjacent nodes are B, C and D. We visit all one by one. Let we pick B. The unvisited adjacent to B is E. We visit E and go back to the remaining unvisited nodes of A and let we pick C. The unvisited adjacent to C is F. We visit F and go back to the remaining unvisited nodes of A. Finally we pick D and visited the unvisited adjacent to D, that is F. Thus the sequence so generated is A, B, E, C, F, D, G

Figure 10

For this we need a queue and add unvisited nodes adjacent to the one just visited at the rear and read at front to find the next node to visit. Figure-11 shows the step-by-step procedure.

Figure 11

Here is the algorithm that performs this task.

Algorithm : BreadthFirstSearch

Here is the ‘C’ implementation of this algorithm:

BreadthFirstSearch(adj[], n, s)

Here ‘adj’ is an array of graph nodes, ‘n’ is th total number of nodes in a graph and ‘s’ is the source node from which the traversal is being started.

Step-1 : Initialize  Visited[s]=True
Step-2 : Initialize front = NULL and rear = NULL
Step-3 : Call InsertQueue(&front, &rear, s);
Step-4 : Repeat through step-14 while (!(front==NULL))
Step-5 :     Set u = front node of the queue
Step-6 : Set current=adj[u]
Step-7 : Repeat through step-12 while (current!=NULL)
Step-8 : Initialize     v=current->vertex
Step-9 : Check if (Visited[v]==False) then go to step-10
Otherwise go to step-12
Step-10 : Set Visited[v]=True
Step-11 : Call InsertQueue(&front, &rear, v)
Step-12 : Update the value of ‘current’ as current=current->link
Step-13 : Delete the front node of the queue and assign it to ‘u’ as u=DeleteQueue(&front, &rear);
Step-14 : Print the value of ‘u’
Step-15 : Exit

Implementation : BreadthFirstSearch

BreadthFirstSearch(GraphNode *adj[], int n, int s)
{
 GraphNode *current, *front, *rear;
 int u, v;
 Visited[s]=True;
 front = rear = NULL;
 InsertQueue(&front, &rear, s);
 while (!(front==NULL))
 {
 u = FrontElement(front);
 current=adj[u];
 while (current!=NULL)
 {
 v=current->vertex;
 if (Visited[v]==False)
 {
 Visited[v]=True;
 InsertQueue(&front, &rear, v);
 current=current->link;
 }
 else
 current=current->link;
 }
 u=DeleteQueue(&front, &rear);
 printf("\n%d",u);
 }
}

In this function we have used three function InsertQueue(), DeleteQueue() and FrontElement().

Depth First Search

In depth first search, the first node is visited initially and then the unvisited node which is adjacenct to first node is visited and a depth first search is initiated from the adjacent node. If all the adjacent nodes have been visited then the process back tracks to the last node visited and find another adjacent node and initiate the depth first search from the adjacent one. This process continues until all nodes have been visited.

Here is the algorithm that traverses a graph using dpeth first search technique. 

Algorithm : DepthFirstSearch

DepthFirstSearch(adj[], n, s)

Here ‘adj’ is an array of graph nodes, ‘n’ is th total number of nodes in a graph and ‘s’ is the source node from which the traversal is being started.

Step-1 : Initialize Visited[s]=True
Step-2 : Initialize top = NULL 
Step-3 : Call PushNode(&top, s);
Step-4 : Repeat through step-16 while (!(top==NULL))
Step-5 :     Set u = top node of the queue
Step-6 : Set current=adj[u]
Step-7 : Repeat through step-14 while (current!=NULL)
Step-8 : Initialize     v=current->vertex
Step-9 : Check if (Visited[v]==False) then go to step-10
Otherwise go to step-12
Step-10 : Set Visited[v]=True
Step-11 : Call PushNode(&top, v)
Step-12 : Set u = current->vertex
Step-13 : Update the value of ‘current’ as current=adj[u]
Step-14 : Update the value of ‘current’ as current as
Current = current->link;               
Step-15 : Delete the top node of the stack and assign it to ‘u’ as u=PopNode(&top);
Step-16 : Print the value of ‘u’
Step-17 : Exit

The ‘C’ implementation of this algorithm is as:

Implementation : DepthFirstSearch

DepthFirstSearch(GraphNode *adj[], int n, int s)
{
 GraphNode *current, *top;
 int u, v;

 Visited[s]=True;
 top=NULL;
 PushNode(&top, s);

 while (top!=NULL)
 {
 u = StackTopNode(top);
 current=adj[u];

 while (current!=NULL)
 {
 v=current->vertex;
 if (Visited[v]==False)
 {
 Visited[v]=True;
 PushNode(&top, v);
 u=current->vertex;
 current=adj[u];
 }
 else
 current=current->link;
 }

 u=PopNode(&top);
 printf("\n%d",u);
 }
}

In this function we have used three function PushNode(), PopNode() and StackTopNode().

Topological Sort

If G is a directed graph with no direct cycles then a topological order of G is a linear ordering of all the vertices in G such that if G contains an edge from v to w (v, w), then v appears before w in the linear ordering. Such a graph is also known as directed acyclic graph (DAG) or simple DAG. Remember that if G contains any cycle then the graph G is not DAG and thus no linear ordering is possible.

DAGs are used in many applications to indicate precedence among events. For example, consider the courses available at a university as the vertices of a graph G, where there is an edge from one course to another, if the first is a prerequisite from the second.

In topological sort we perform depth first traversal on each vertex. As each vertex is finished we insert it at front of the linked list, say first. And finally we print the elements of the linked list in order. Consider the DAG as shown in figure-12.

Figure 12

The adjacency list of graph, shown in figure-12, is as shown in figure-13

Figure 13

Figure-14 shows the step-by-step procedure of finding the topological order of a DAG of figure-12

Figure 14

Now let us develop algorithms that produce a topological ordering of the vertices of a DAG.

Algorithm : TopologicalSort

TopologicalSort(adj, n, first)

Here adj is the adjacency list of ‘n’ number of vertices and first is a pointer to a pointer to a list of nodes which contains the list of vertices in topological order. 

Step-1 : Initialize i=1
Step-2 : Repeat through step-4 while (i<=n)
Step-3 : Set Visited[i] = false
Step-4 : Increment the value of i as i=i+1
Step-5 : Initialize i=1
Step-6 : Repeat through step-8 while (i<=n)
Step-7 : Call DFSModified() algorithm if (Visited[i] == false)
Step-8 : Increment the value of i as i=i+1
Step-9 : Exit

This algorithm calls DFSModified(). The working of DFSModified() algorithm is as:

DFSModified(adj, n, first)

Here adj is the adjacency list of ‘n’ number of vertices and first is a pointer to a pointer to a list of nodes which contains the list of vertices in topological order.

Step-1 : Set Visited[v] = 1
Step-2 : Initialize     ptr = adj[v]
Step-3 : Repeat through step-6 while (ptr != NULL)
Step-4 : Set w = ptr->vertex
Step-5 : If (Visited[w] == false) then Call DFSModified(adj, w, first)
Step-6 : Update the value of ptr as ptr = ptr->link
Step-7 : Create a temporary node ‘temp’
Step-8 :     Set temp->vertex = v
Step-9 : Set temp->link = (*first)
Step-10 : Update the value of first as (*first) = temp
Step-11 : Exit

The implementation of these algorithms is as:
Implementation : TopologicalSort

TopologicalSort(GraphNode *adj[], int n, GraphNode **first)
{
 int i;
 for(i=1; i<=n; i++)
 Visited[i] = False;

 for(i=1; i<=n; i++)
 {
 if (Visited[i] == False)
 DFSModified(adj, i, first);
 }
}
DFSModified(GraphNode *adj[], int v, GraphNode **first)
{
 int w;
 GraphNode *ptr, *temp;
 Visited[v] = True;
 ptr = adj[v];

 while (ptr != NULL)
 {
 w = ptr->vertex;
 if (Visited[w] == False)
 DFSModified(adj, w, first);
 ptr = ptr->link;
 }
 temp = getnode();
 temp->vertex = v;
 temp->link = (*first);
 (*first) = temp;
}

Minimum Spanning Trees

A graph is said to be spaning tree if it has (n-1) edges for ‘n’ vertices. A spanning tree ‘T’ for a connected weighted graph ‘G’ is said to be minimum if the sum of the weights of the tree edges in T is as small as possible. A minimum spanning tree represents the cheapest way of connected all the nodes in ‘G’. In general, a weighted graph may have more than one minimum spanning tree, that is the minimum spanning tree of a graph is not necessarily unique.

There are numbers of algorithms for creating a minimum spanning tree for a weighted graph. But here we will study two familiar algorithms – Kruskal and Prim, to compute minimum cost spanning tree of a weighted graph.

Kruskal’s Algorithm

Kruskal’s algorithm was designed by J.Kruskal in 1957. This algorithm works on a list of edges of a graph (the list is sorted in order of increasing weights (costs) of the edges). A list of edges can be easily created from adjacency matrix or adjacency list of a graph. Once this list of edges is created, we sort this list in increasing order of their weights.

Initially the nodes of a graph are considered as ‘n’ distinct partial trees with one node each. At each step of algorithm two distinct partial trees are connected into a single partial tree by an edge from the sorted list. The edge is added only if its inclusion does not form a cycle, that is an edge with the smallest weight is inserted without introducing a cycle. After the inclusion of an edge, it is deleted from the sorted list. This process goes on until (n-1) edges are inserted or the list of edges is exhausted. When only one partial tree exists (after ‘n-1’ insertions) it is a minimum spanning tree. One main point to remember in Kruskal algorithm is to determine whether the insertion of a new edge introduces a cycle in a forest or not.

Let us understand this process by considering an undirected weighted graph as shown in figure-15.

Figure 15

Initially we will create a list of edges in a list ‘EdgeList’ and then we will sort this EdgeList according to their increasing weights. The list of sorted edges of graph, shown in figure-15, is as:

(1, 2)    (1, 3)    (2, 3)    (2, 4)    (2, 5)    (5, 6)    (3, 4)    (3, 6)

Initially we have 6 distinct partial trees with one node each as shown in figure-16(a). We take the first edge from the sorted list and connect two partial tree of vertices 1 and 2 as shown in figure-16(b). Next we take second edge from the list and connect vertices 1 and 3 as shown in figure-16(c). Figure-16 shows step-by-step procedure to creating a minimum spanning tree.

Figure 16

Now let us write an algorithm, which form a minimum spanning tree from a weighted undirected graph. Input to this algorithm is a list of edges ‘EdgeList’ which is being sorted in increasing order of their weights and ‘n’ number of vertices in the graph. However the definition of nodes of EdgeList and MainList is slightly different than GraphNode.

The definition of an EdgeNode is as follows:

struct EdgeNode
{
 int v;
 int w;
 int weight;
 struct EdgeNode *link;
};
typedef struct EdgeNode EdgeNode;

This algorithm arranges the edges in MainList in the order in which they are connected to partial minimum spanning tree.

Algorithm : KruskalMinSpanningTree

KruskalMinSpanningTree(EdgeList, n, MainList)

Here EdgeList contains the address of the edges of the graph in increasing order of their weights, ‘n’ is total number of nodes and MainList is passed as pointer to a pointer. 

Step-1 : Initialize    i=1
Step-2 : Repeat through step-4 while (i<=n)
Step-3 : Set parent[i] = i
Step-4 : Increment the value of i as i=i+1
Step-5 : Initialize edgecount=1
Step-6 : Repeat through step-12
while ((edgecount < n)&&(EdgeList != NULL))
Step-7 : Set current = EdgeList
Step-8 : Update the value of EdgeList = EdgeList->link
Step-9 : If current does not form a cycle in MainList then go to step-10; otherwise go to step-6
Step-10: Check if ((*MainList) == NULL) then
Set (*MainList) = current and temp = (*MainList)
Otherwise Set temp->link = current and  temp = temp->link
Step-11:    Set temp->link = NULL
Step-12 : Increment the value of edgecount as
edgecount = edgecount+1
Step-12 :Exit

The implementation of this function is as:

Implementation : KruskalMinSpanningTree

KruskalMinSpanningTree(EdgeNode *EdgeList, int n, EdgeNode **MainList)
{
 EdgeNode *current, *temp;
 int parent[Size];
 int i, x, y, wt, edgecount;
 edgecount=1;
 for(i=1; i<=n; i++)
 parent[i] = i;
 while ((edgecount < n)&&(EdgeList != NULL))
 {
 current = EdgeList;
 EdgeList = EdgeList->link;
 x = find((current->v), parent);
 y = find((current->w), parent);

 if (x != y)
 {
 parent[x] = y;
 edgecount++;
 if ((*MainList) == NULL)
 {
 (*MainList) = current;
 temp = (*MainList);
 }
 else
 {
 temp->link = current;
 temp = temp->link;
 }
 temp->link = NULL;
 }
 }
}

This algorithm makes use of another function find() in order to find whether the addition of specific edge introduces a cycle or not. Here is the definition of find() function:

find(int i, int parent[])
{
 int j;
 j=i;
 while (parent[j] != j)
 j = parent[j];
 return (j);
}

The time complexity of creating a sorted list of edges is O(e*loge), where ‘e’ is the number od edges in the graph and O(logn) is the time complexity of detecting whether an edge forms a cycle or not. Thus the overall time complexity of this algorithm is O(e*loge) + O(e*logn).

Prim’s Algorithm

In this an arbitrary node of graph ‘G’ is chosen initially from ‘n’ number of nodes as the tree root of the partial minimum spanning tree ‘T’. The nodes of the graph ‘G’ are then appended to the tree one at a time until all nodes of the Graph ‘G’ are included. In each iteration, one edge (v, w) is added to this partial tree ‘T’ so that one end of this edge belongs to the set of vertices in ‘T’, of all such possible edges the edge having the minimum weight is selected.

In other words each iteration the node (vertex) of the graph added to the tree is that node adjacent to a node of the tree by an edge of minimum weight. The edge of minimum weight becomes a tree edge connected a new node to the tree. Finally when all the nodes of the graph ‘G’ have been added to the tree, a minimum spanning tree ‘T’ has been constructed for the graph ‘G’.

In order to implement this we maintain one array Visited[] and two linked lists – EdgeList and MainList. The array Visited maintains the vertices which are included in the minimum spanning tree. The list EdgeList contains those edges which are have exactly one end belonging to the partial minimum spanning tree. The list MainList contains those edges which are chosen to form minimum spanning tree.

Let we have a graph as shown in figure-15. The illustration of the working of Prim’s algorithm is shown in figure-17.

Figure 17

Shortest Path Problems

Graphs are more frequently used to represent the highway structure of a district, state or country with vertices representing the area (city or state) and edges representing sections of highway. The edges may then assigned weights which may represent distance, cost, time or some other quantity. If somebody wants to go from one place, say Delhi, to another place, say Moscow, then he would be interested in answers to the following questions:

(i)    Is there any path from Delhi to Moscow
(ii)    If there is more than one path from Delhi to Moscow then which is the shortest one

These problems are special types of path problems that we shall be studying in this section. In this section we will study shortest path problems in weighted graphs. In a general weighted graph, G, it is frequently desired to find the shortest path between two nodes (vertices). A path from source vertex ‘v’ to destination ‘w’ is said to be shortest path from ‘v’ to ‘w’ if the sum of weights on the path is as small as possible. In fact there could be more than one path between a pair of specified vertices, say ‘v’ and ‘w’. The shortest path need are not necessarily unique.

Note that the weights can be either positive or negative. But unfortunately applications using negative weights are very-very rare. Therefore for the sake of simplicity we will consider the cases where edges have positive values. Consider the weighted graph as shown in figure-18. The shortest path from vertex 1 to vertex 5 goes via vertex 3 and 6 and has a cost of 17, compared to the cost of 24 for the path via vertex 2.

Figure 18

There are many different variations of the shortest path problems, but here we will study only two – the shortest path from a specified source vertex to every other vertex (single source all destinations) and the shortest paths between all possible source and destination vertices (all pairs shortest paths).

Single Source All Destinations

Consider the graph G = (V,E) which contains ‘n’ vertices 1, 2, 3,…., n. Let Wij denotes the weight (cost) of the edge Eij which connects vertex ‘i’ to vertex ‘j’. If the value of Wij is greater than 0 then it means that there is a path from vertex ‘i’ to vertex ‘j’ and if Wij is infinity then it means that there is no path from vertex ‘i’ to vertex ‘j’. Usually shortest paths are defined on weighted directed graph. An edge from a directed graph (v, w) has to be interpreted as two edges (v, w) and (w, v). For the further discussion of finding shortest path problems we will consider weighted undirected graph.

Dijkstra’s Algorithm (Greedy Algorithm)

One popular algorithm for solving single source all destinations problem is due to Dijkstra. This algorithm is called greedy algorithm. This algorithm takes the source vertex 1 and it finds the shortest path from vertex 1 to every vertex in the graph. In this algorithm we keep a set ‘S’ of those vertices whose shortest distance from vertex 1 is known. Initially it contains only vertex 1. At each step we add to ‘S’ remaining vertex for which the shortest path from vertex 1 has been calculated.

The main point to keep in mind is to find out which vertex to add to ‘S’ at each step. To facilitate this we will use an array, called d[], to keep track the current shortest distance for any vertex from the vertex 1. The value of d[i] is initialized to W0j for all ‘i’, 1 ≤ i ≤ n. The array d[] is maintained in such a way that d[i] gives the shortest distance from vertex 1 to vertex ‘i’ provides i € S. However if ‘i’ is not in ‘S’ then d[i] gives the length of the path from vertex 1 to some other vertex ‘k’ in S plus the weight of the edge from ‘k’ to ‘i’, and all the edges of this path except the last one are marked.

Now let us try to prove that d[i] actually gives the shortest distance between vertex 1 to vertex ‘i’. For this suppose that d[i] is not the shortest distance between vertex 1 to vertex ‘i’ as the shortest path from vertex 1 to vertex ‘i’ consists of a vertex ‘k’ which is not currently included in ‘S’. If it is so then this algorithm will choose ‘k’ rather than ‘i’ for this as the next vertex to add to ‘S’. But the vertex ‘k’ lies on the shortest path from vertex 1 to vertex ‘i’. Thus d[k] < d[i]. After this we must update the entries of d[] by checking, for each vertex k not in ‘S’, whether a path through ‘i’ and then directly to k is shorter than the previous recorded distance to ‘k’. That is we replace d[k] by d[i] plus the weight of the edge from ‘i’ to ‘k’ if later one is shorter.

Before writing an algorithm for computing shortest paths for single source, say vertex 1, to all destinations, let us go through the graph shown in figure-18. Initially the set ‘S’ consists of 1 alone, and the entries of the distance array d[] are shown besides the other vertices. The shortest distance from vertex 1 is from 1 to 3, so 3 is added to S as shown in figure-9(c). Next closest vertex to 1 is vertex 2. Since the distance from vertex 1 to 2 via vertex 3 is smaller than the direct distance from vertex 1 to vertex 2, therefore its distance is updated. These steps are shown one-by-one in figure-19.

Now let us write an algorithm for this.

Algorithm : DijkstraShortPath

DijkstraShortPath(adj, n, d, t, source)

Here ‘adj’ is the adjacency list of ‘n’ number of vertices and source is the starting vertex from where we have to find the shortest paths to all destinations. This algorithm will produce the distances in an array d[] and their paths in array t[].

Step-1 : Initialize i=1
Step-2 : Repeat through step-3 while (i<=n)   
Step-3 : Set d[i] = Infinity, t[i] = source and sd[i] = 0
Step-4 : Increment the value of ‘i’ as i=i+1
Step-5 : Initialize with source vertex alone in the set.
Step-6 : Update the value of ‘d’ according to the source vertex
Step-7 : Set t[source] = -1 and sd[source] = 1
Step-8 : Set d[source] = 0
Step-9 : Initialize x=1
Step-10 : Set min = Infinity
Step-11 : Repeat through step-14 while (x < n)
Step-12 : We will find the closest vertex ‘v’ to source vertex and add it to set
Step-13 : Update the value of remaining distances one by one.
Step-14 : Increment the value of x as x=x+1
Step-15 : Exit

All Pairs Shortest Paths

The all pairs shortest path problems invites the call for finding the shortest paths as well as their weights (costs) between every pair of vertices vi and vj of a graph such that i  ≠ j. Of course we can apply the DijkstraShortPath algorithm ‘n’ times, once with each vertex of the graph ‘G’ as the source vertex. In such case the total complexity of the algorithm will be O(n³). However we can achieve this in same computing time, O(n³), with much simpler way using Floyd-Warshall algorithm. The Floyd-Warshall algorithm also runs in O(n³) time.

Floyd-Warsahl’s Algorithm

Let an adjacency matrix ‘a’ of ‘n’ number vertices, such that there is self-loop, represents a directed weighted graph ‘G’. In this for any pair of vertices, say vertices v_i and v_j, if there is direct shortest path between them without any other intermediate vertex then aij is the shortest distance between vertices v_i and v_j . However there is any shortest path between vertices v_i and v_j using any intermediate vertex, say v1, then a shorter distance between the vertices vi and vj may be recalculated. In other words we have to find the minimum of aij and (a_i1 + a_1j). And this process goes on for more vertices from 1 to k to be used as intermediate vertices and discover even shorter paths.  Now we can easily formalize it.

Let A^k[i,j] denotes the shortest path between the vertices vi and vj of a graph ‘G’ provided that there is no intermediate vertex of index greater than k, say (k+1), (k+2), (k+3),…n. In a generalize way we can say that A_ⁿ[i,j] represents the shortest distance between the vertices vi and vj of a graph ‘G’ since G contains no vertex greater than ‘n’. The basic idea behind this algorithm is to successively generate the matrices A^0, A¹, A²,…,Aⁿ. We can easily generate Ak from A^k-1.

We can generate A^k using A^k-1 by realizing the fact that for any pair of vertices v_i and v_j either – the shorter path from vertices vi to vj going through no vertex with index greater than k does not go through the vertex with index k, or the shortest path from vertices vi to vj go through vertex v^k. In later case the shortest path is divided into two subpaths – p1 and p2. The subpath p1 is from from vertices vⁱ to v^k and p² is from vertices vj to vk. Paths p1 and p2 must be the shortest paths from vertices vi to vk and from vertices vk to vj going through no vertex with index greater than k-1. Based on the above observations, we can define recursive formulation of shortest path for Ak as:

Ak[i, j]= min (Ak-1 [i, j], Ak-1 [i, k]+ Ak-1 [k, j]) for k≥ 1
Or
A0[i, j]= aij

Similarly we can compute the path matrix. Specifically the sequence of the path matrices P0, P1, P2,…., Pn. the elements of Pkij is defined to be predecessor of vertex vj on a shortest path from vertex vi with all intermediate vertices in the set {1, 2, 3, …., k}. Now its recursive definition can be easily written as:

P0[i, j] = 0 (for i=j) or I (if≠ j)
and
Pk [i, j] = Pk-1 [i, j] if Ak-1 [i, j]  Ak-1 [i, k]+ Ak-1 [k, j]) or
= Pk-1 [k, j] if Ak-1 [i, j] > Ak-1 [i, k]+ Ak-1 [k, j])

Let us understand this algorithm by using the weighted graph shown in figure-20.

Figure 20

The following matrices are the sequence of matrices A and P, generated by using above formulas.

FloydWarshalAllPairPath(adj, n, dist, path)

Here ‘adj’ is an adjacency table of ‘n’ number of vertices. The array dist[] is used to contain the distances between every pair of vertices and the array path contains the shortest path for every pair of vertices. {

Step-1 : Initialize i=1
Step-2 : Repeat through step-7 while (i<=n)
Step-3 :     Initialize j=1
Step-4 : Repeat through step-6 while (j<=n)
Step-5 : Check if (adj[i][j] == 0) then
set path[i][j] = 0 and dist[i][j] = Infinity
else set dist[i][j] = adj[i][j] and path[i][j] = i
Step-6 : Increment the value of j as j=j+1               
Step-7 : Increment the value of i as i=i+1               
Step-8 : Initialize k=1
Step-9 : Repeat through step-18 while (k<=n)
Step-10 : Initializei=1
Step-11 : Repeat through step-17 while (i<=n)
Step-12 : Initialize j=1
Step-13 : Repeat through step-16 while (j<=n)
Step-14 : If (i != j) then go to step-15; otherwise go to step-16
Step-15 : If ((dist[i][j]) > (dist[i][k] + dist[k][j])) then
Set dist[i][j] = dist[i][k] + dist[k][j] and
path[i][j] = path[k][j]
Else set dist[i][j] = dist[i][j] and path[i][j] = path[i][j];
Step-16 : Increment the value of j as j=j+1               
Step-17 : Increment the value of i as i=i+1               
Step-18 : Increment the value of k as k=k+1               
Step-19 : Exit

Transitive Closure of a Directed Graph

Let we have a directed graph G = (V, E) where V is the set of vertices and E is the set of edges. The adjacency matrix ‘A’ of the graph ‘G’ is said to be the transitive closure matrix A+ of the graph ‘G’ if it has the following property:

A+[i, j] = 1 if there is a path in ‘G’ from vertex ‘i’ to vertex ‘j’; 0 otherwise

The simplest way to compute the transitive closure is to assign a weight of 1 to each edge of E in the Floyd-Warshall and use the Floyd-Warshall algorithm. If there exists a path from vertex ‘i’ to vertex ‘j’ then dist[i][j] =1; otherwise dist[i][j]= ∞. However we can even simplify it by slightly modifying the algorithm using the logical operations ν (OR) and Λ (AND) as:

For k=0        Ak[i, j] = 1 if dist[i][j] is not  and 0 if dist[i][j] is 
For k>0        Ak[i, j] = Ak-1[i, j]   (Ak-1[i, k]  Ak-1[k, j])

Here is the algorithm for finding the transitive closure of a directed Graph ‘G’.

Algorithm : TransitiveClosure

TransitiveClosure (adj, n, trans)

Here ‘adj’ is an adjacency table of ‘n’ number of vertices. This algorithm computes the transitive closure and stires the result in matrix ‘trans’.  

Step-1 : Initialize i=1
Step-2 : Repeat through step-7 while (i<=n)
Step-3 :     Initialize j=1
Step-4 : Repeat through step-6 while (j<=n)
Step-5 : Check if (adj[i][j] == 1) then
set trans[i][j] = 1
else set trans[i][j] = 0
Step-6 : Increment the value of j as j=j+1               
Step-7 : Increment the value of i as i=i+1               
Step-8 : Initialize k=1
Step-9 : Repeat through step-17 while (k<=n)
Step-10 : Initializei=1
Step-11 : Repeat through step-16 while (i<=n)
Step-12 : Initialize j=1
Step-13 : Repeat through step-15 while (j<=n)
Step-14 : Set trans[i][j] = trans[i][j]  trans[i][k]  trans[k][j]
Step-15 : Increment the value of j as j=j+1               
Step-16 : Increment the value of i as i=i+1               
Step-17 : Increment the value of k as k=k+1               
Step-18 : Exit

A graph ‘G’ consists of a set of vertices ‘V’ and a set of edges ‘E’ such that G = (V,E) where V={v1, v2, …., vn) and E={e1, e2, …., en). Graphs can be either directed or undirected. In a directed graph, each edge is represented in an ordered pair of vertices, that is e=(v,w) is an edge having ‘v’ as initial vertex and ‘w’ as final vertex. On the other hand, in an undirected graph  the elements of ‘E’ are unordered.

The number of edges incident on a vertex determines its degree. However if you have a directed graph then its degree can be of two types indegree and outdegree. For a directed graph, degree of a vertex is equal to indegree plus outdegree. If a vertex has no edge then it is called as an isolated vertex. An isolated vertex has zero degree. A graph is said to be complete or fully connected if there is path from every vertex to every other vertex. A graph is said to be weighted if every edge in the graph is assigned some weight or value. This weight can represent any positive value. A path from a vertex vi to vj is a sequence of vertices v1, v2, …. such that (vi, vi+1) is an edge where i varies from 1 to j-1 and all edges are distinct.

Two most familiar implementating ways of graphs are adjacency matrix and adjacency list. In an adjacency matrix, each element aijof it is either 0 or 1. If the value of aij is 1 then it means that there is an edge from vertex ‘i’ to vertex ‘j’. Adjacency list of a graph isa linked list representation of it.

Graphs can be traversed in various different ways. Two familiar ones are depth first search and breadth first search. In depth first traversal we start traversing from a vertex, say f, and then explore new vertices by initiating the same process from any of the unvisited vertices adjacent to the starting vertex ‘f’. In breadth first traversal, we start traversing from any vertex, say ‘f’, and visits all unvisited vertices adjacenct to the start vertex ‘f’.

If G is directed graph with no direct cycles then a topological order of G is a linear ordering of all the vertices in G such that if G contains an edge from v to w (v, w), then v appears before w in the linear ordering. Such a graph is also known as directed acyclic graph (DAG) or simple DAG. Remember that if G contains any cycle then the graph G is not DAG and thus no linear ordering is possible. 

A spanning tree ‘T’ for a connected weighted graph ‘G’ is said to be minimum if the sum of the weights of the tree edges in T is as small as possible. There are two familiar algorithms – Kruskal and Prim, to compute minimum cost spanning tree of a weighted graph. Kruskal algorithm works on a sorted list of edges and forms a spanning tree by starting with a forest on ‘n’ vertices. On the other hand, Prim algorithm starts with a vertex and goes on adding edges to an already formed partial minimal spanning tree. This algorithm inserts that minimum cost edge which has exactly one end belonging to the already formed minimal spanning tree.

Finding shortest paths is another important type of problem. A path from source vertex ‘v’ to vertex ‘w’ is said to be shortest path from ‘v’ to ‘w’ if there is no path from ‘v’ to ‘w’ with minimum cost. Two main ways of finding shortest paths are Dijkstra and Floyd-Warshal. Dijkstra algorithm is used for solving single source and all destinations and Floyd-Warshal is used for solving all pair shortest path problem.

 

q. WAP to implement the use of scope resolution operator

#include
#include
int number=100;
int main()
{clrscr();
coute block\n";
int number=555;
couter;
}
coutin";
cout"numberumber=";
getch();
return 0;
}



output of the program:
in main
inside block
number=555 ::number=555
back in main
number=234 ::number=234

Description about program:

in the above programe firstly we declared globally number to100. Then in the main fuction we firstly define that we are in main then define an integer type number =243 . then inside an another block we again define an integer type number=555. Then if we simply write cout number in side that block it show an output number=555. outside the block if we write cout

In this article I am sharing the basic concepts of Object Oriented Programming (OOP): Objects and Classes, Inheritance and Polymorphism. This article will also discuss the need of OOPs. After this we will see the importance of OOPs over Structured programming. In last we will also discuss the brief history of C and C++ languages and the relationship between C and C++.

Why We Need OOPs

Before I write about Object Oriented Programming (OOP), let us understand the limitations of procedural programming, modular programming, structured programming etc.

In earlier days, the programs were written in machine languages that were loaded into memory through a set of console switches or through a numeric keypad. Such programs were very difficult to debug. After this assembly language was designed that enabled us to use mnemonic codes for machine instruction and symbolic names for memory locations. But still our machine understood only the machine language. Therefore assemblers were needed to translate assembly language programs into machine codes. Since the concept of assembly language was still machine independent and it was very difficult to debug large and complex programs.

After that high level language such as FORTRAN, BASIC and so on are designed. These higher level languages are just like English language. The programs written in higher level languages are translated into machine language by a compiler. Each higher level language has its own compiler. The programming in higher level language is simpler than low level language. But still these programs have some following limitations:

1. The program, which was used once, can not be reused.

2. The programs used global variables. And it was very difficult to trace out the changes in these global variables.

3. It was very horrible to write, understand and maintain complex programs.

These limitations are overcome by procedural languages that also support structured programming. In this the large programs are broken into smaller units. For this reason, the functions/ subprograms/ procedures are introduced in these higher level languages to make programs more comprehensible to their human creators. Thus a large program is divided in various functions and each function performs a well-defined task. Each function is also clear defined interface to the other functions in the program. Each function has its own local variables and set of instructions to perform a well-defined task.

• The idea of breaking a program into functions can be further extended by combining a number of functions into a large entity called a module. The concept is same even for a module – a module is made to carry out specific task. Therefore structured programming concept involves both dividing a program into functions and modules, one of the corner stones of structured programming.

• Structured programming also introduced a new concept – abstraction. In structured programming, programmer needs to know only the task performed by functions, rather than to know how that task is performed by that function. This is called functional abstraction. And it is another corner stone of structured programming.

• But the structured programming begins to loose its grip over programmers, as programs grow ever larger and more complex. One of the most crucial reasons for the failure of procedural language is the role played by data.

• In a procedural language, the whole emphasis on doing things – read the data, check for errors and finally display the data, if there is no error. Therefore the concept is how to receive the data, how to process the data, how to display the data and so on. The functions that perform these activities are given prime status in the organization of procedural languages and the data is given second class status in the organization of procedural languages whereas data is, after all, the reason for a program’s existence.

• Thus procedural-programming concept is to decide which functions/procedures you want and then select the best one that suited your requirement.

• In procedural languages, the programs use both global and local variables. If data is treated as global, then they are accessible to all functions or programs. It means that one function may read it, one may analyze it, one may update it, and one may display it and so on. Therefore knowingly or unknowingly any function can corrupt this global data. On the other hand, if the data is defined as local then they are not accessed by many different functions, because local variables are accessed within the function.

• Another reasons with structured programming is that their major components – functions and data structures do not model the real world very well. For example, let you are writing a program to create the elements of Graphic User Interface (GUI): menus, windows and so on. One can not predict – what functions will you need? What data structures you need? Thus there are no obvious program elements to which a menu or a window would correspond because procedural languages fit a problem to the procedural approach that is they fit the problem into the functions.

• Another problem with procedural languages is that of creating a new data types. Built – in data types, such as integers, real numbers, and characters are provided by the language. On the other hand if programmer wants to create its own data type, such as data type that deals with complex numbers, then for traditional languages it is very difficult to create such data types.

Therefore more programmers are started to use Object-Oriented Programming (OOP). The OOP languages provide a new way of organizing data and code that promises increased control over the complexity of the software development process.

Object Oriented Programming

• The basic idea behind Object Oriented Languages is to combine into a single unit both data and functions that operate on this data. Such a unit is called an object. An object represents an entity that can store data and has its interface through functions. The data of an object are called as data members and the functions are called as member functions in C++. The member functions are also referred as methods in some object–oriented languages such as Smalltalk. These data members represent the information contained in the object and member functions define the operations that can be performed on that object.

• While accessing this data, one can not access it directly. The only way to access its data is through its member functions. It means that if we want to read a data item, we call a member function in the object. This function reads the item and returns the value to us. Therefore the data is hidden for the functions that are defined outside the object. This is known as data hiding. And obviously it is safe from accidental alteration.

• The data and functions are said to be encapsulated into a single entity. Thus the data encapsulation and data hiding are the main pillars of Object Oriented Programming (OOP).

• It is the data abstraction that specifies the data as well as the functions to be used by others. You can also say that data abstraction is the process of defining a new data type, together with the principle of data type. In C++, class is synonymous with a data abstraction. Thus a class represents a template from which objects are created and when an object is created it sets aside a memory space for the data members of the objects.

• A C++ program typically consists of a number of objects, which communicate with each other by calling one another’s member functions.

When we solve a problem in an Object Oriented Programming environment, we divide the problem into objects rather into functions. However when you will see a C++ program first time, you see that most individual programming statements in C++ are similar to statements in C. Even member functions in C++ look alike a procedural function in C. When you look at the complete large program only then you can determine whether it is a part of a procedural language or an Object Oriented C++ program.

Characteristics of OOP

The major components of Object Oriented language in general and C++ in particular that overcomes the limitations of procedural languages are as:
1.    Objects
2.    Classes
3.    Inheritance
4.    Reusability
5.    Polymorphism
6.    Dynamic Binding
7.    Message Communication

Objects

In a procedural programming approach we divide our problems into functions. But in Object Oriented programming it will be divided into objects. And it is easier way to design a program in terms of objects rather than in functions. But now the question arises – what kinds of things becomes objects in Object Oriented programming. Actually there is no hard and fast rule that specifies that it must be treated as objects and it must not. It is the programmer who selects the objects according to his limitations. Here are some typical candidates that can be treated as objects in different programming environment:

• Students in a library management system
• Programming constructs such as array, stack, queue, linked list etc.
• Graphics user interface elements such as windows, menus, graphic objects (icons) mouse and keyboard.
• Elements in computer games such as chess, cannons, guns, animals etc.
• User defined data types such as distances, complex numbers etc.

Classes

A class is a specification of describing a user-defined data type and an object in C++ is an instance of a class or you can say objects are members of classes. We know that almost all computer languages have built–in data types, such as int, floats and chars. If we want to declare x, y, and z of type integer then we use following statement
int x, y, z;

Like this once a class has been defined, we can create any number of objects belonging to that same class. Thus a class is an entity that specifies what data and functions will be included in object of this class. Just as the mere existence of a type int does not create any integer variable, likewise when a class is defined it does not create any object; it just defines a new data form.

Inheritance

OOP provides a concept of inheritance. Unlike built–in data types, one class can inherits the properties of another class by using inheritance. Inheritance is the capability of a new class to inherit the data and functions of the old class without knowing the details of old class. The new class is known as derived class and the old class is known as base class. The derived class not only inherits some characteristics from its base class but also adds some new features of its own.
The set of base class and derived class instances is referred as the class inheritance hierarchy. Multiple inheritance is one of the many types of inheritance. By multiple inheritance we mean deriving a class from more than one base class. Not all Object-Oriented Programming languages support multiple inheritance.

Reusability

One of the main objectives of OOP is of its reusability. Once a class has been written, created and tested, it can be distributed to other programmers for use it in their own programs. This functionality is called as reusability. If these programmers want to add their own new features then new classes can be derived from it. This new class will inherit the capabilities of the old one but is free to add new features of its own.

For example, let we have a class that adds and subtracts two complex numbers. So here if we derive a new class from this class then the new class contains both these, addition and subtraction, features and can add its own feature of multiplying two complex numbers and so on.

The ides of inheriting a class can be further extended by creating a derived class from another derived class. It means that if we have derived a class–B from a base class–A then class–C can be derived from class–B . Here the class–C naturally inherits the properties of class–A and this property of inheritance is known as transitive nature of inheritance.

Polymorphism

In a general term, polymorphism means the ability of having more than one form. In the context of OOP, polymorphism is the ability for a data to be processed in more than one form or you can say that different objects react in different manner to the same operation. We know that the arithmetic operator + (plus) is generally applied on built–in data types, such as integers, floats etc. For example, we can use the expression (a+b) to denote the sum of a nad b, for so many values of a and b. And if we want to apply + (plus) operator on user defined data type then we will define new operations for this + (plus) operator. For example we can even define the ‘+’ operator for two strings to mean the concatenation of the string.

Let we have two strings:

char name1[20] = “ATI”;
char name2[10] = “SHRESTHA”;

If we want to concatenate these two strings then we will use the following statement:
strcat(name1, name2);

And by using polymorphism property we can write it as:
name1 = name1 + name2 ;
This + (plus) operator will be the member function of say string class. Like this other operators can also be operated on user defined data types. This is called as operator overloading. Like this we can also have a single function name to handle different numbers and types.

This concept of using a single function name to perform different type of activities is known as function overloading. Thus using operators and functions in different ways, depending upon what they are operating on, is called polymorphism.

Dynamic Binding

Generally binding is performed either at compile time or at run time. The binding which is done at compile time is known as static binding (early binding) and the binding which is done at run time is known as dynamic binding (late binding). Thus we can determine only at run time that which function is called. Basically dynamic binding is associated with polymorphism and inheritance.

Message Communication

Another important feature of OOP is message communication that is idea of sending message to an object, causing it to perform an operation by invoking the appropriate function of the object. And of course the calling member function of the object must be capable of handling the operation you want. This is a typical message communication between two objects.

Importance of OOPs over Structured Programming

• OOPs provide the concept of object and class to encapsulate the data and functions into one entity. Structured programming does not support such facility.

• OOPs provide the concept of data hiding that helps programmers to have secured data from improper access.

In OOPs, data are treated as first class entity, whereas structured programming treats functions as first class entity and data as second class entity.

• OOPs provide the facility of having multiple instances of an object to coexist with any interference.

• OOPs provide the facility of inheritance in which we can derive a new class from an older one. On the other hand, structured programming does not support such facility.

• OOPs also provide the facility of reusability of the existing class without modifying it.

• In OOPS, we can use same function name for two or more functions. On the other hand, in structured programming we use unique name for each function.
• OOPs also provide the additional meaning to arithmetical and logical operators. It means that we can perform arithmetical and logical operations on user defined data type also. In contrast to this, structured programming performs these operators on built – in data type only.

Advantages of OOP

It is easy to write simple programs for small problems. But the situation becomes complex when the program size becomes large. Therefore while writing complex programs there may have some error, either at logical level or at any run time level. And it is the Object Oriented Paradigm that provides some new and powerful features to solve this complexity. The objectives of Object Oriented Programming are clearer, more reliable, more easily maintained programs. The Object Oriented Paradigm is the latest invention in the software development. Thus the ultimate conclusion is that sooner or later the Object Oriented approach to organize a program impresses every computer programmer.

OOPs and C++

C++ is one of the most popular languages that support OOPs features. C++ joins together two separate programming traditions – procedure oriented programming, represented by C, and object oriented programming, represented by C++, a superset of C language. The main reason to avail you of its object oriented features. Since C++ is a superset of C language, so for the C programmers it would be a bit easy to migrate from Turbo C to Turbo C++. Now one may ask – Is it necessary to have sound background in Standard C? Its answer is Yes and No. Knowledge of C would certainly help in understanding loops, arrays, structures, and pointers of C++. But if you do know C then the transformation of C lovers from Turbo C to Turbo C++ is very exciting and thrilling.

Actually C and C++ are two different languages, though they have similar syntax. C++ is a fresh programming methodology designed to cope with escalating complexity of modern programming tasks. We can also say that C++ is the language of future.

History of C

• C was developed by Dennis Ritchie a programmer at AT and T Bell laboratories, in the early 1970s. It was not his motto to design a new language at that time. Actually he was working on a project to develop the Unix multi-user, multitasking operating system along with another programmer Ken Thompson. Initially Unix was written by Ken Thompson in machine language. But due to lack of portability Unix was restricted to use on the specific machine, say PDP-7 and PDP-11.To overcome this limitation, they needed a language that was concise, that produced compact, fast programs, and that could control hardware efficiently. This necessity invented the development of another new high level language C; thus C was intentionally design to make Unix portable.

• After the development of C, Ken Thompson successfully rewrote Unix in C and no doubt they made programming history. Now almost 90% Unix was written in C and thus it was made a truly portable operating system. Another main point to note that Unix was the first major operating system to be written in something other then low-level programming language. Since Unix was not 100% portable, so when Unix is ported to another type of system it needed rewriting a few assembly language operating system drivers and interface functions, and recompiling the operating system. This feature made C as a unique language that could be used to write system programs and that could be used to write portable programs, a goal that was never achieved by the high level language that came before it.

• The C++ language has been available outside AT and T since about 1985. Now a day C++ like C before it, has become the language of choice among programmers.

History of C++

• C++ programming language was designed and developed by Bjarne Stroustrup also at AT and T BELL laboratories in the early 1980’s as a means of making programs easier to write and maintain. At that time people found that there are some limitations in procedural languages like Pascal, Basic, Fortran, Cobol etc. The limitations of procedural language are already discussed in earlier section.

• Therefore rather than design a new language from the ground up, Bjarne Stroustrup decided to build upon the C language. Bjarne Stroustrup added some new features, such as objects, classes, polymorphism, inheritance, operator overloading, functions overloading etc, to the most popular language C without significantly changing its components. Some features were taken from one of the earlier object oriented language: Simula67. Bjarne Stroustrup called it “C with classes” originally. Later it was named as C++ (pronounced as C plus plus) where “++” is the C increment operator indicating an incremental development of C. Thus C++ is a superset of C, meaning that any valid C programming is a C++ programming too.

• The other languages that support OOPs features are Smalltalk, Simula, Objective C, Eiffel, Turbo Pascal 7.0, Java etc. Among these OOPs languages, C++ is by far the most popular languages and Java is the latest one.

• C lovers might wonder about C’s future given the current popularity of C++ and object-oriented programming. Some C++ lovers might say that C++ would the language of choice. To some extend, it is true but C is more suitable for solving some special programming problems. Many C++ lovers might not agree with this opinion, but it is widely held by others. You might be surprised to know that window 98 operating system is written almost entirely in C, even though its developer, Microsoft, also developed Visual C++. However of course, if one were to understand the development from scratch of a new operating system today, the language of choice probably would be C++.
C versus C++

Now let us see some distinguish features of C programs and C++ programs. Since C++ is a superset of C, it means that a C++ compiler is able to compile any C program. However there are suitable differences between C programs and C++ programs.

The C++ language has some extra reserved words that are not reserved by the C language. Such extra keywords can be used in a C programs as identifier for functions and variables C programmers can omit function prototypes, as they are optional in C program. But it is compulsory to declare function prototypes in C++ programs.

Many standard C functions have counter parts in C++, and C++ programmers view them as improvements to the C language. Here are some ones:

• The C++ provides new and delete dynamic memory allocation/deallocation operator that replace standard C’s malloc() and free() functions.
• The C++ iostream class library replaces Standard C’s stdio function library for console input and output.
• The C++ provides try\catch\throw exception handling mechanism that replaces standard C’s setjmp() and longjmp() function.

Structure of a C++ Program

Actually C++ is a procedural language with the object-oriented extensions. It means that we can define as well as instantiate (create from a class) objects in C++. The procedural modules in C++ programs are called functions. Every C++ program consists of one or more functions. Any function can call any function. Even a function can call itself.

Functions may contain parameters. When a function is called, the values for its parameters are passed to the called function. Some functions return a value and others do not. The calling function that returns a value can code the function call on the right hand side of an assignment statement, assigning the returned value to a named variable. Each function consists of one or more block statements. In C++ a block is just a set of statements enclosed in a pair of curly braces ‘{’ and ‘}’. Each block has its own set of local variables, which remains in scope as long as the statements in that block are executed. A C++ program can also have global variables. Global variables are declared outside all functions. Global variables are called as global because the statements in all functions in the same source file can reference them.

In C++ statements are one of the following types:

• Declaration Statements – The statements that declare variables and functions are called as declaration statements. A variable declaration specifies the variable’s storage class, data’s type, name and dimensions, if it is an array. A function declaration, also known as function prototype, declares the function’s return type, name and number and types of its arguments.

• Definition Statements – The statements that define the instances of variables and functions are called as definition statements. A variable definition includes the components of declaration and may include an initializer if the variable has an initializing value. A function definition contains the function’s executable code.

Here one should remember that a variable declaration and definition are the same statement but a function declaration and definition are usually in different places. However the function definition may also serve as its prototype only if the function’s definition appears in the source code file ahead of all calls to the function.

• Procedural Statements – These statements include assignments, expressions, or control statements. Expressions consist of variables, constants, operators, and function calls. An expression can stand on its own or be on the right side of an assignment statement.

I have already written that in this article that a function is collection of statements which is designed to perform a specific task. The statements must appear in the function in the same order in which we wish them to be executed. C provides sequential, selective and repetitive statements. C++ allows separately compiled functions to used without being in the program proper, that is a function can be accessed by any program.

Here is the structure of a typical C++ program:

[Preprocessor Directives]
[External Variable Declaration]
[Class Definition and Declaration]
main()
{
[Local Variable Declaration]
Program Statements
}

[User-defined Functions] The square brackets denote optional structures.

A Simple ‘C++’ Program

Before going into the depth of C++, let us consider a very simple program, examine it and try to discover what it does.

Program article1.cpp represents a very simple C++ program.
/ Program – article.cpp // Comment statement
#include // Preprocessor directive
void main() // A function heading
{
cout << “Nobody is greater than God.”; // Statement
}

Like C, every C++ program is basically a collection of functions in which main () is an essential function and several other fundamentals. C++ language constructs. Typically, we organize a program into major tasks, then design separate functions to carry out these tasks.

The main () function

Almost every C++ program consists of one or more functions in which main() is an essential function. It provides the entry and exit points to the program. The program starts executing with the first statement in main() and terminates when the main() function returns.

The program article1.cpp consists of a single function main(). The very first line of the function, main(), is called the function heading, and the portion enclosed in the braces ({ and }) is called the function body. The single left brace ‘{‘ character defines the start of main()’s outermost statement block. The statement block continues until its corresponding enclosing right brace ‘}’ character encounters. A brace surrounded group of statements is called a statement block.

Every function has at least one statement block. The statement blocks can be nested. It is the function heading that interfaces between the rest of the program and the function. The function body represents the activity performed by the function. The program article1.cpp has the following statement block:

{
cout << “Nobody is greater than God”; // statement
}

this statement block has only one statement:
cout << “Nobody is greater than God”;

This statement tells the compiler to display a string constant on the screen. Like C, in C++ every statement is ended by a semicolon (;). If you do not mention a semicolon then the compiler will definitely signal an error message.

Generally, a C++ function is called by another function. The part that precedes the function name is called the function return type, and it describes the information flow from the function to the function that called it. The part that follows the function name is called the argument list, and it describes the information flow from the calling function to the function being called. In the program article1.cpp, the word void preceding the function name describes that this particular function does not have a return value. Since main() takes no argument so the argument list is empty.

In short void main(void) states that the main() function does not return any value to the function that calls it and that main() function takes no argument from the function that calls it. If a function is not receiving any argument then it is optional to have void in the argument list. Thus the following notations are treated similarly by the C++ compiler:

void main(void) or void main()

Now the question arises – why the main() function is an essential function? (And not, by the way, MAIN() or Main() or mane() or any other function name). When we execute a C++ program, execution always begins at the beginning of the main() function. If you don’t have main(), your program will be compiled successfully, but it will not run and the compiler will report that you have not defined a main() function. That’s why every C++ program begins with a function named main(). In last remember that your program is not allowed to call the main() function explicitly. It is called implicitly by the compiler.

The C++ Preprocessor Directives: #include

Like C, C++ uses a preprocessor. A preprocessor is a program that processes a source file before the main compilation takes place. C++ handles directives whose names begin with a number sign #. We don’t need to do anything special to invoke this preprocessor. It is invoked automatically when we compile the program.

In the program article1.cpp, we have used the following preprocessor directive: #include.
The #include directive tells the compiler to include a different source-code file in your program. This directive tells the compiler to add the contents of the iostream.h file into our source file. This action of preprocessor is similar to pasting a block of text data into a document with your word processor.

Now the question arises – why add the contents of the iostream.h file to the program? The iostream.h describes classes, functions, and global values used for console input/output. The iostream.h stands for input–output stream. By input we mean the information brought into the program and output sends out the information from the program. We can receive information either from a standard input device, keyboard, or from a file. Similarly we can send information either to a standard output device, VDU, or to a file.

The iostream.h defines cin object to receive information from a standard input device and cout object to send information to a standard output device. That’s why it is necessary for the programs that use cin and cout for input and output, to include the iostream.h file. Without its inclusion, the compiler would not recognize cin and cout objects. The files with .h extension are referred as header files.

The filename in the #include directive is enclosed by angle brackets, that is ‘’ (greater than symbol). This usage identifies header files that compiler system provides. However if you want to include your own header files then you would surround these user-defined header files within double quotes (“ …. “). In C, the inclusions of header files are often optional; whereas in C++ they are always necessary.

The Standard Output Stream: cout

In program article1.cpp, the statement
cout << “Nobody is greater than God”;

writes the string constant, which is the character sequences between double quotes, to the console. In this statement, the cout variable is the C++ standard output stream object that writes the data to the console. You might have already listen the word – stream. A stream is an abstraction that refers to a flow of data. By default the standard output stream is associated with the monitor. Also it can be associated with other output devices.

The << operator is the output operator, also called as insertion operator. The insertion operator inserts data, which is on its right side into the output stream, which his on its left side. Thus the insertion operator points symbolically from what is being sent to where it is going. In the above statement the string constant is being written to the cout object that displays data on the monitor. You can also think of cout as an output device. Later on, you will learn how to display other data types.

White Spaces

Like C, C++ also is a free-form language, which means that C++ compiler ignores white-space characters – newline characters, spaces, tabs and blank lines completely. These characters are invisible to the compiler. Except for the rare occasion when two tokens are separated by a space or inside string constants. Actually your program does not need any type of white spaces to compile. Thus the program article1.cpp looks like this without white spaces:

#include
void main () {cout << “Nobody is greater than God”; }

This program will certainly compile and run correctly. But without white spaces it is rarely hard to read most programs. Therefore programmers often use white spaces to indent and separate code in various styles to make their programs more readable. There are so many ways for writing a C++ program. There is no hard and fast rule. Therefore choose a style that works for you, make it legible and be consistent in its use.

STRUCTUIRE

A structure ia a collection of heterogeneous variable referenced under one name. The keyword struct tell the compiler that a structure is being defined.

General syntax:
Struct tag
{
Type variable name1;
Type variable name2;
:
:
:
}structure variable;

There are two ways to declared a structure variable i.e.

1.

Struct student
{
Char name[20];
Int roll_no;
Float marks;
} s1;

2.

Struct student
{
Char name[20];
Int roll_no;
Float marks;
} ;
Student s1;

Different points regarding structure:
• The moment structure variable is declared the memory is assign to the structure.
• Tag name or structure variable may be omitted but not both.
• The struct tag can be omitted when only one structure variable is needed.
• More than one structure variable can be created by using commas.

Example: Write a structure to hold students related information like roll no, class, marks, and grade. Definitions should also declared two variable senior and junior.
Solution:
Struct student
{
Char name[20];
Int roll_no;
Float marks;
Int class;
Char c;
} senior _student, junior _student;

Once the structure variable has been defined the structure can be exist to the structure variable and dot(.) variable.

General syntax:
Struct variable.struct element
Example: coutsenior_student.name;


INITILIZATION OF STRUCTURE ELEMENT

Structure element can be initialized either separately using assignment operator or jointly using the notation similar to array.
Example:
ss.name = “Pankaj”;
ss.roll_no = 1;
ss.marks = 65.5;
ss.class = 12;
ss.c = ‘A’;

OR

student.ss = {“Pankaj”,1, 65.5, 12, ‘A’};
Example 2: using structure display the cost of a car according to it make model and chases number by assigning all the pieces of necessary information.
Solution:
#include
#include
Struct car
{
Char car_make[20];
Int car_model;
Int number;
Float cost;
} c;
Void main()
{
Clrscr();
c.car_make = “Maruti”;
c.car_model = 2000;
c.number = 39456;
c.cost = 100050.00;
coutee
{
Char first_name[20];
Char second_name[20];
Int emp _id;
} emp[50];

Void main()
{
Int n,i;
Coutn;
For(i=0;iemp[i].first_name