Chapter 1



Chapter - 1

Introduction To C Language:

C was developed by Dennis Ritchie at Bell Laboratories in 1972. Most of its principles and ideas were taken from the earlier language B, BCPL and CPL. CPL was developed jointly between the Mathematical Laboratory at the University of Cambridge and the University of London Computer Unit in 1960s. 

CPL (Combined Programming Language) was developed with the purpose of creating a language that was capable of both machine independent programming and would allow the programmer to control the behavior of individual bits of information. But the CPL was too large for use in many applications. In 1967, BCPL (Basic Combined Programming Language) was created as a scaled down version of CPL while still retaining its basic features. This process was continued by Ken Thompson.

He made B Language during working at Bell Labs. B Language was a scaled down version of BCPL. B Language was written for the systems programming. In 1972, a co-worker of Ken Thompson, Dennis Ritchie developed C Language by taking some of the generality found in BCPL to the B language.

  In 1973, C language had become powerful enough that most of the Unix kernel was rewritten in C. This was one of the first operating system kernels implemented in a language other than assembly.

  During the rest of the 1970's, C spread throughout many colleges and universities because of its close ties to UNIX and the availability of C compilers. Soon, many different organizations began using their own versions of C Language. This was causing great compatibility problems. In 1983, the American National Standards Institute (ANSI) formed a committee to establish a standard definition of C Language. That is known as ANSI Standard C. Today C is the most widely used System Programming Language.

Chapter - 2

Introduction to Data Structure:

Definition – Data Structure is a collection of data elements and a set of operations which can be performed on data elements.

Consider an educational institute system, Gurukul. Now to construct a system we have organize all of their records into a computer database. The first thing we have to do is to create a database of names with all the Institute’s administration and employees. To start our work, we have to make a list of everyone in the institute along with their position (designation), as shown in figure. 2.1

| |Name | |Designation |

| |Arjun | |Lecturer |

| |Bharat | |Librarian |

| |Geeta | |Lab Technician |

| |Karan | |Registrar |

| |Krishna | |HOD CSE |

| |Laxman | |HOD IT |

| |Radha | |Office Staff |

| |Sriram | |Principal |

| | | | |

Fig.2.1 List of employees

Fig. 2.2 Tree structure of employee designation

But this list only shows one view of the institute. We may also want our database to represent the relationships between employees at Gurukul. Even though our list contains both name and designation, it does not tell us about the relationship among them. So, we decide that a tree diagram is am much better structure for showing the work relationships at Gurukul, as shown in fig.2.2.

These two diagrams are examples of different data structures. In fig.21, our data is organized into a list. This is very useful for keeping the names of the employees in alphabetical order so that we can locate the employee’s record very quickly. However, this structure is not very useful for showing the relationships between employees. Fig.2.2 shows a tree structure for better representation.

Data structures are an important way of organizing information in a computer. Just like the fig.2.1 & 2.2 we have seen, there are many different data structures that programmers use to organize data in computer. Some data structure are similar to the tree diagram because they are good for representing relationships between data. Other structures are good for ordering data in a particular way like the list of employees. Each data structure has unique properties that make it well suited for some particular purpose.

There are may different ways of creating the same data structure in a computer. Each data structure has certain operations that naturally fit with the data structure.

Classification of data structure –

Data structure are normally divided into two broad categories :

1) Primitive data structure

2) Non – primitive data structure

Fig. 2.3 Classification of data structure

Chapter - 3

Introduction to Graph:-

This chapter is investigates another nonlinear data structure: the graph. As we have done with other data structure, we discuss the representation of graph in memory and present various operation and algorithm on them. In particular, we discuss the breadth-first search and the depth-first search of our graph. Certain applications of graph, including topological sorting, are also covered.

Trees provide a very useful way of representing relationship in which a hierarchy exists. If we remove the restriction that each node may be pointed at most one node, we come across another data structure called graph. Graph is used in many areas like Networking, Geographical information system (GIS). Global positioning system (GIS) for finding the route between the source and destination etc.

Graph theory has its history from Konigsberg bridge problem. The Prussian city of Konigsberg was built along the Prefer River and occupied both banks and two islands. The problem was to seek a route that would enable one to cross all seven bridges in the city exactly once and return to their starting point. Leonhard Euler, a mathematician, developed some concepts in solving this problem and these concepts formed the basis of the graph theory. He modeled the problem by treating each land mass as vertex and each bridge as an edge, deriving the graph.

Graph theory terminology

This section summarizes some of the main terminology associated with the theory of graph. Unfortunately, there is no standard terminology in graph theory. The reader is warned, therefore, that our definition may be slightly different from the definition used by other text on data structure and graph theory.

Chapter - 4

Type of Graph:-

Graph: A Graph G consists of two sets V & E. Set V is a finite, nonempty set of vertices & E is a set of pairs of vertices, called edges.

G=(V,E)

Fig.4.1 Graph(G)

Undirected Graph: A graph in which pair of vertices representation any edge is unordered i.e, (1,2)(2,1) representation same edge.

Fig.4.2 Undirected graph (G)

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)}

Directed Graph:

A directed Graph G, also called a digraph, is the same as a multigraph except that each edge e in G is assigned a direction, or in other words, each edge e is identified with an ordered pair (u,v) of nodes in G rather than an unordered pair [u, v].

Suppose G is a directed graph with a directed edge e =(u,v). Than e is also called an arc.

Moreover, the following terminology is used:

1) e begins at u and ends at v.

2) u is the origin or initial point of e, and v is the destination or terminal point e.

3) u is a predecessor of v, and v is a successor or neighor of u.

4) u is adjacent to v, and v is adjacent to u.

Directed Graph: A graph in which each edge is representation by a directed pair where ais tail & b is head of the & are two different edges. Directed graph is also called digraph.

Fig.4.3 Directed graph (G2)

V(G2)= {1,2,3}

E(G2)= {,,,}

Basic Terminology

1. Adjacent Vertices:- Vertices v1is said to be adjacent to a vertex v2 if there is an edge ( v1,v2 ) or ( v2,v1 ). Following graph show the adjacent vertices.

Fig.4.4

Vertices adjacent to node 2 are 1 and 3 and that to node 4 is 1,3

2. Path:- A path from vertex w is a sequence of vertices, each adjacent to that next. Consider the above example again 1,2,3 is a path and 1,4 and 3 is also a path.

3. Cycle:- A Cycle is a path in which first and last vertices are the same. In the above example (1,2,3,4,1) is a cycle.

4. Connected graph:-A graph is called connected if there exists a path from any vertex to any other vertex. Graph shown in following figure.

Fig.4.5

In order to make it connected graph , connected 1to 4 and 3 to 5 thus it becomes a connected graph as shown in following figure.

Fig.4.6

So far we have seen about paths, cycle and connectivity of undirected graph. Now let us see about directed graph. Consider the graph following figure.

Fig.4.7

There does not exists an edge from vertex 1 to 4 and also from vertex 5 other vertices and so on. Therefore it is weakly connected graph. In order to make it connected, certain changes are required as shown in following figure.

5. Degree:-The number of edge incident on a vertex determines 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 an indegree and an outdegree to each of the vertices. Indegree of vertex (3) is 2 and outdegree is 1.

Fig.4.8

6. Complete Graph:-A graph G is said to complete or fully connected if there is path from every vertex to every other vertex. A complete graph within vertices will have n(n-1)/2 edge.

7. Weighted Graph:-A graph is said to be weighted graph if every edge in the graph is assigned some weight or value. The weight of edge is a position value that may be representation the cost of moving along the edge or distance between the vertices.

In the above figure we mentioned the distance between Pune and Ahmednagar as 120 km and Pune and Aurangabad is 225km and Pune to Mumbai 200km

Fig.4.9

Chapter - 5.

Graph Representation:-

Scientific results are mostly available in the form of articles in journals and conference proceedings, and on various Web1resources. These articles are not self-contained, but cite previous articles with related content. However, when you read an article from 1975 with an interesting partial result, you may often ask yourself what the current state of the art is. In particular, you would like to know which newer articles cite the old article. Projects such as Google Scholar provide this functionality by analyzing the reference sections of articles and building a database of articles that efficiently supports looking up articles that cite a given article.

We can easily model this situation by a directed graph. The graph has a node for each article and an edge for each citation. An edge (u,v) from article u to article v means that u cites v. In this terminology, every node (= article) stores all its outgoing edges (= the articles cited by it) but not the incoming edges (the articles citing it). If every node were also to store the incoming edges, it would be easy to find the citing articles. One of the main tasks of Google Scholar is to construct the reversed edges. This example shows that the cost of even a very basic elementary operation on a graph, namely finding all edges entering a particular node, depends heavily on the representation of the graph. If the incoming edges are stored explicitly, the operation is easy; if the incoming edges are not stored, the operation is nontrivial. In this chapter, we shall give an introduction to the various possibilities for representing graphs in a computer. We focus mostly on directed graphs and assume that an undirected graph G = (V,E) is represented as the corresponding (bi)directed graph

G′ = (V,S{u,v}∈E {(u,v), (v,u)}). Figure 8.1 illustrates the concept of a directed graph. Most of the data structures presented also allow us to represent multiple parallel edges and self-loops. We start with a survey of the operations that we may want to support.

Matrix Representation:-

Sequential representation of Graph

There are two standard ways of maintaining a graph G in memory of computer. One way, called the sequential representation of G, is by means of its adjacency matrix A. The other way, called the representation, and shows how the adjacency matrix A of G can be used to easily answer certain questions of connectivity in G. The linked representation of G will be covered in sec. 8.5.

Regardless of the way one maintains a graph G in the memory of the computer, the graph G is normally input into the computer by using its formal definition: A collection of nodes and a collection of edges.

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 graph shown in following figure.

1 2 3 4

1 0 1 1 1

2 1 0 1 1

3 1 1 0 1

4 1 1 1 0

Fig.5.1 Undirected Graph and its matrix representation

The matrix representation for directed graph is as shown in following figure.

1 2 3 4

1 0 1 0 0

2 1 0 1 0 3 0 0 0 1

4 1 0 0 0

Fig.5.2 directed Graph and its matrix representation

The matrix representation for weighted graph is as shown in figure.

For a weighted graph, the [i,j] position contains the weight of that edge if there is an edge, otherwise it is 0.

1 2 3 4

6 7 1 0 5 0 0

5 2 6 0 4 0

3 0 0 0 6

4 7 0 0 0

4 6

Fig.5.3 Weighted graph and its matrix representation

This representation is very simple but problem occurs if the matrix is sparse (contains more number of zero element), so the alternative is adjacency list.

2). Adjacency List:-

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 and decollates whenever required. Graph can be represented 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 and for each vertex, there is a linked list of its adjacent vertices. The list contain header node pointing to the linked lists of vertices. If there is no outgoing edge from a vertex then the header pointer for that vertex contains NULL. Fig.(a) shown as directed graph and fig. (c) Shown the corresponding adjacency list representation.

Fig.5.4 A directed graph

List

1

2

3

4

5

6

Fig.5.5 Directed graph and Adjacency List representation.

Fig.5.6 Undirected Graph.

List

Fig. Undirected Graph and its adjacency list representation

Chapter - 6

Graph Traversal:-

Many applications requires us to visit all the vertices in a graph. In case of all the data Structures, we have studies till now, including tree, we have a starting node with which we can Start traversing the data structure. In case of a graph there is no such starting node, we can start traversing the data structure. In case of a graph there is no such starting node, we can specify any arbitrary node as the starting node. Basically, Given an undirected graph G=(V,E)and a vertex V in V(G), 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 graph. We shall look at tow ways of doing this :

1. Depth first search (DFS)

2. Breadth first search (BFS)

1. Depth First Search (DFS) :-

Depth first traversal of an undirected graph is roughly analogous to preorder traversal of an ordered tree. The start vertex V is visited first. Let w w………..w be the vertices adjacent to V. Then the vertex w1 is visited next. After visiting w1 all the vertices adjacent tow1 are visited in depth first manner before returning to traverse w2……wk The search terminates when no unvisited vertex can be reached from any of the visited ones.

In DFS we traverse a single path of the graph as far as it can go i. e. until it lists a node with no successors or a node all of whose successors have already been visited. We follow a path in the graph as deeply as we can go When there are no adjacent non visited nodes, then we can proceed backwards. We can use stack to implement DFS. There may be several.

Algorithm:-

1. Select any unvisited node in the graph. Mark this node as visited, push this onto the stack

2. Find the adjacent node to the node on top of the stack and which is not yet visited, Mark this new node as visited and push on to stack.

3. Repeat step(2) until no new adjacent node to top of stack. Node can be found, when no new adjacent node can be found, Pop Top of the stack.

4. Repeat step(2)&(3) till stack becomes empty.

5. Repeat step (1) till any more nodes which are still unvisited USE ADJACENCY MATRIX for finding adjacent nodes.

Consider the graph shown as in following figure Depth first search as follow:

Fig. Depth first search

1. PUSH A C G B E nodes on to the stack and then marks these nodes as visited.

Visited = [A C G B E]

|E |

|B |

|G |

|C |

|A |

We push all nodes which are adjacent to A, starting with C and all successors till there are no more successors.

2. New backtrack.

POP TOS. i. e. E as it does not have any more adjacent node or unprocessed node.

| |

|B |

|G |

|C |

|A |

TOS

3. POP B, it as unprocessed nodes so, push F on to the stack. PUSH B & F visited = [A C G B E F]

|F |

|B |

|G |

|C |

|A |

TOS

4. POP F it has so, unprocessed successors node so backtrack to node B.

| |

|B |

|G |

|C |

|A |

TOS

5. POP B , it has no unprocessed node H so, push H on to the stack. PUSH B & H. visited = [A C G B E F H]

| |

|H |

|B |

|G |

|C |

|A |

TOS

6. POP H, no unprocessed nodes are left so, backtrack to node B.

POP H, no unprocessed nodes are left so, backtrack to node G

| |

|G |

|`C |

|A |

TOS

7. POP G , no unprocessed nodes are left so, backtrack to node C.

| |

|C |

|A |

TOS

8. POP C no unprocessed node are left so, backtrack to node A.

| |

|A |

TOS

9. POP A

A has adjacent and unprocessed node D

PUSH A and B

Visited = [A C G B E F H D]

| |

|D |

|A |

TOS

10. POP D no unprocessed node are left so backtrack to node A

POP A. no unprocessed node are left. All the node are visited

Empty stack.

| |

So, the visited nodes are

A C G B E F D

Bredth First Search (BFS)

The breadth first search differs from depth first search.here all unisited vertices

Adjacent to v are visited after visiting the starting vertex v and marking it as visited.

Next the unvisited vertices adjacent to these vertices are visited and so on until the

Entire graph have been traversed.

This traversal algorithm uses queue to store the nodes of each level of the graph as and when they are visited and so n until all nodes have been visited. The algorithm

Terminates when the queue becomes empty.

Consider the graph shown in Fig 5.15. the breadth first search is carried out as Follows.

Fig. Depth first search (DFS)

Algorithm:

1) Select any unvisited node in the graph. Mark this node as visited. Insert this node into the queue.

2) Find all the adjacent nodes (one by one) or node present is the front end of queue & which is not yet visited, mark this new node as visited & insert it into the queue.

3) Repeat step (2), till queue become empty.

4) Repeat step (1), till any more nodes which are still unvisited.

Start at node A

1) Make this node as visited, and place its adjacent nodes i.e C & D in Queue

Visited – [A]

|C |D |

Front Rear

2) Now delete element from queue i.e. C Mark this node as visited and place its unprocessed adjacent nodes in queue i.e.G

|D |G |

Front Rear

3) Again delete element from queue, I.e. D. mark this node as visited, and place its unprocessed adjacent nodes in queue, here no nodes.

Visited = [A C D]

Front, Rear

4) Delete element from queue, i.e.G. mark this node as visited, and place its unprocessed adjacent nodes in queue. i.e.B.

Visited [A C D G]

Front, Rear

5) Delete element from queue i.e.b. mark this node as visited and place its unprocessed adjacent nodes in queue i.e.E,F and H.

Visited = [A C D G B]

|E |F |H |

Front Rear

6) Delete element from queue,i.e.E. Mark this node as visited, and place its unprocessed adjacent nodes in queue, no nodes.

Visited = [A C D G B E]

Front Rear

7) Delete element from queue,i.e.E. Mark this node as visited, and place its unprocessed adjacent nodes in queue, no nodes.

Visited =[A C D G B E F ]

Front, Rear

8) Delete element from queue, i.e.H. Mark this node as visited, and place its unprocessed adjacent nodes in queue, no nodes.

Visited = [A C D G B E F H] Now queue becomes empty

So, the visited nodes are

A C D G B E F H

Minimum Spanning Trees:-

A spanning tree of a graph is a tree that touches all the vertices (so, it only makes sense in

a connected graph). A minimum spanning tree (MST) is a spanning tree whose sum of edge lengths is as short as possible (there may be more than one). We will sometimes call the sum of edge lengths in a tree the size of the tree. For instance, imagine you are setting up a communication network among a set of sites and you want to use the least amount of wire possible. Note: our definition is only for undirected graphs.

1. Prim’s algorithm:-

Prim’s algorithm is an MST algorithm that works much like Dijkstra’s algorithm does for shortest path trees. In fact, it’s even simpler (though the correctness proof is a bit trickier).

Prim’s Algorithm:

1. Pick some arbitrary start node s. Initialize tree T = {s}.

2. Repeatedly add the shortest edge incident to T (the shortest edge having one vertex in

T and one vertex not in T) until the tree spans all the nodes.

So the algorithm is the same as Dijsktra’s algorithm, except you don’t add distance(v) to the length of the edge when deciding which edge to put in next. For instance, what does Prim’s algorithm do on the above graph?

Before proving correctness for the algorithm, we first need a useful fact about spanning trees: if you take any spanning tree and add a new edge to it, this creates a cycle. The reason is that there already was one path between the endpoints (since it’s a spanning tree), and now there are two. If you then remove any edge in the cycle, you get back a spanning tree (removing one edge from a cycle cannot disconnect a graph).

Theorem 13.2 Prim’s algorithm correctly finds a minimum spanning tree of the given graph. Proof: We will prove correctness by induction. Let G be the given graph. Our inductive hypothesis will be that the tree T constructed so far is consistent with (is a sub tree of) some minimum spanning tree M of G. This is certainly true at the start. Now, let e be the edge chosen by the algorithm.

We need to argue that the new tree, T ∪ {e} is also consistent with some minimum spanning tree M′ of G. If e ∈ M then we are done (M′ = M). Else, we argue as follows.

Consider adding e to M. As noted above, this creates a cycle. Since e has one endpoint in T and one outside T, if we trace around this cycle we must eventually get to an edge e′ that goes back in to T. We know len(e′) ≥ len(e) by definition of the algorithm. So, if we add e to M and remove e′, we get a new tree M′ that is no larger than M was and contains T ∪{e}, maintaining our induction and proving the theorem.

2. Kruskal’s algorithm:-

Sorts the edges and then puts them in one at a time so long as they don’t form

a cycle. So, first the AD and BE edges will be added, then the DE edge, and then the EF edge. The AB edge will be skipped over because it forms a cycle, and finally the CF edge will be added (at that point you can either notice that you have included n − 1 edges and therefore are done, or else keep going, skipping over all the remaining edges one at a time). Theorem 13.3 Kruskal’s algorithm correctly finds a minimum spanning tree of the given graph. Proof: We can use a similar argument to the one we used for Prim’s algorithm. Let G be the given graph, and let F be the forest we have constructed so far (initially, F consists of n trees of 1 node each, and at each step two trees get merged until finally F is just a single tree at the end). Assume by induction that there exists an MST M of G that is consistent with F, i.e., all edges in F are also in M; this is clearly true at the start when F has no edges. Let e be the next edge added by the algorithm. Our goal is to show that there exists an MST M′ of G consistent with F ∪ {e}. If e ∈ M then we are done (M′ = M). Else add e into M, creating a cycle. Since the two endpoints of e were in different trees of F, if you follow around the cycle you must eventually traverse some

edge e′ 6= e whose endpoints are also in two different trees of F (because you eventually have to get back to the node you started from). Now, both e and e′ were eligible to be added into F, which by definition of our algorithm means that len(e) ≤ len(e′). So, adding e and removing e′ from M creates a tree M′ that is also a MST and contains F ∪ {e}, as desired.

Program:

/*Program for creation of a graph using matrix representation */

#include

#include

int graph [10][10],vertex[10] ,n,e;

void main()

{

int i,j,k,l;

clrscr();

printf(“\n Enter no. of vertices of the graph :”);

scanf(“%d”,&n);

printf(“\n Enter no. of edges of the graph :”);

scanf(“%d”,&e);

printf(“\n Enter edges as pair of vertices :\n”);

for(k=l;k= ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download