DAA: Program to study and implement Depth first search.

No: 11

1. vision:

2. OBJECTIVE: Program to implement Depth first search in c programming.

3. THEORY:

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. DFS is typically used to traverse an entire graph, For applications of DFS in relation to specific domains, such as searching for solutions in artificial intelligence or web-crawling, the graph to be traversed is often either too large to visit in its entirety or infinite.

1.      PROGRAM:

#include<stdio.h>

void DFS(int);

int G[10][10],visited[10],n;    //n is no of vertices and graph is sorted in array G[10][10]

void main()

{

    int i,j;

    printf("Enter number of vertices:");

  

    scanf("%d",&n);

    //read the adjecency matrix

    printf("\nEnter adjecency matrix of the graph:");

  

    for(i=0;i<n;i++)

       for(j=0;j<n;j++)

            scanf("%d",&G[i][j]);

    //visited is initialized to zero

   for(i=0;i<n;i++)

        visited[i]=0;

    DFS(0);

}

void DFS(int i)

{

    int j;

    printf("\n%d",i);

    visited[i]=1;

   

    for(j=0;j<n;j++)

       if(!visited[j]&&G[i][j]==1)

            DFS(j);

}

5. OUTPUT:

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

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

6. conclusion:

Thus we studied Depth first search program and executed successfully.

7. Discussion Questions:

1) what is Depth first search?

_________________________________________________________________________________________________________________________________________________________

2)   What is difference between BFS and DFS?

______________________________________________________________________________________________________________________________________________________

3)   What is the complexity of DFS?

______________________________________________________________________________________________________________________________________________________

DAA: program to Implement minimum spanning tree using Kruskal’s algorithm.

No: 10

1. Experiment vision: Write a program to study and implement minimum spanning tree    using Kruskal’s algorithm.

2. OBJECTIVE: Program to implement minimum spanning tree from prim’s algorithm and   connected node to each other in such way that not become a cycle.  

3. THEORY:

Prim's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a sub set of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it will only find a minimum spanning tree for one of the connected components.

It works as follows:

• create a tree containing a single vertex, chosen arbitrarily from the graph

• create a set containing all the edges in the graph

• loop until every edge in the set connects two vertices in the tree

Ø  remove from the set an edge with minimum weight that connects a vertex in the tree   with a vertex not in the tree

Ø  Add that edge to the tree

4.  PROGRAM:

#include<stdio.h>

#include<conio.h>

int a,b,u,v,n,i,j,ne=1;

int visited[10]={0},min,mincost=0,cost[10][10];

void main()

{

 clrscr();

 printf("\n Enter the number of nodes:");

 scanf("%d",&n);

 printf("\n Enter the adjacency matrix:\n");

 for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  {

   scanf("%d",&cost[i][j]);

   if(cost[i][j]==0)

    cost[i][j]=999;

  }

 visited[1]=1;

 printf("\n");

 while(ne<n)

 {

  for(i=1,min=999;i<=n;i++)

   for(j=1;j<=n;j++)

    if(cost[i][j]<min)

     if(visited[i]!=0)

     {

      min=cost[i][j];

      a=u=i;

      b=v=j;

     }

  if(visited[u]==0 || visited[v]==0)

  {

   printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);

   mincost+=min;

   visited[b]=1;

  }

  cost[a][b]=cost[b][a]=999;

 }

 printf("\n Minimun cost=%d",mincost);

 getch();

}

5. OUTPUT:

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

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

6. conclusion:

Thus a C program for prim’s algorithm has been implemented and executed successfully.

7.  REMARK:

                        In this algorithm, we find the minimum path from source to destination and measure that path. Source path must be start with first node of that graph.

8. Discussion Questions:

1) what is prims algorithm?

_________________________________________________________________________________________________________________________________________________________

2)   what is the difference between prims algorithm and kruskal algorithm.

________________________________________________________________________________________________________________________________________________________

DAA: PRACTICAL MANUAL: PRACTICAL 9

Experiment No: 9

1. Experiment vision:Write a program to study and implement Floyd’s algorithm.

2. OBJECTIVE: Program for computing all pairs shortest path.

3. THEORY:

 Used to find shortest paths in a weighted graph

 • Travel maps containing driving distance from one point to another – Represented by tables – Shortest distance from point A to point B given by intersection of row and column – Route may pass through other cities represented in the table

• Navigation systems All-pairs shortest-path problem • Graph G = (V, E) • Weighted and directed graph

• Problem: Find the length of the shortest path between every pair of vertices – Length of the path is strictly determined by the weight of its edges – It is not based on the number of edges traversed

4. PROGRAM:

#include<stdio.h>

#include<conio.h>

int min(int,int);

void floyds(int p[10][10],int n)

{

 int i,j,k;

 for(k=1;k<=n;k++)

  for(i=1;i<=n;i++)

   for(j=1;j<=n;j++)

    if(i==j)

     p[i][j]=0;

    else

     p[i][j]=min(p[i][j],p[i][k]+p[k][j]);

}

int min(int a,int b)

{

 if(a<b)

  return(a);

 else

  return(b);

}

void main()

{

 int p[10][10],w,n,e,u,v,i,j;;

 clrscr();

 printf("\n Enter the number of vertices:");

 scanf("%d",&n);

 printf("\n Enter the number of edges:\n");

 scanf("%d",&e);

 for(i=1;i<=n;i++)

 {

  for(j=1;j<=n;j++)

   p[i][j]=999;

 }

 for(i=1;i<=e;i++)

 {

  printf("\n Enter the end vertices of edge%d with its weight \n",i);

  scanf("%d%d%d",&u,&v,&w);

  p[u][v]=w;

 }

 printf("\n Matrix of input data:\n");

 for(i=1;i<=n;i++)

 {

  for(j=1;j<=n;j++)

   printf("%d \t",p[i][j]);

  printf("\n");

 }

 floyds(p,n);

 printf("\n Transitive closure:\n");

 for(i=1;i<=n;i++)

 {

  for(j=1;j<=n;j++)

   printf("%d \t",p[i][j]);

  printf("\n");

 }

 printf("\n The shortest paths are:\n");

 for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

  {

   if(i!=j)

    printf("\n <%d,%d>=%d",i,j,p[i][j]);

  }

 getch();

}

5. OUTPUT:

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

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

6. conclusion:

Thus a C program for Floyd’s algorithm has been implemented and executed successfully.

8. Discussion Questions:

1) what is Floyd’s algorithm?

_________________________________________________________________________________________________________________________________________________________

2)   Briefly give the difference between Floyd’s algorithm and Warshall algorithm.

________________________________________________________________________________________________________________________________________________________