Showing posts with label 15CSL38. Show all posts
Showing posts with label 15CSL38. Show all posts

Monday 31 October 2016

Lab Program 11 DFS BFS 15CSL38 Data Structures in C Lab

Lab Program 11

Design, Develop and Implement a Program in C for the
following operations on Graph(G) of Cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a digraph using DFS/BFS method

#include<stdio.h>
#include<stdlib.h>

 int a[50][50], n, visited[50];
int q[20], front = -1,rear = -1;
int s[20], top = -1, count=0;

void bfs(int v)
{
int i, cur;
visited[v] = 1;
q[++rear] = v;
while(front!=rear)
{
                cur = q[++front];
for(i=1;i<=n;i++)
{
if((a[cur][i]==1)&&(visited[i]==0))
{
                               q[++rear] = i;
                                visited[i] = 1;
                              printf("%d ", i);
}
}
}
}

 void dfs(int v)
{
         int i;
visited[v]=1;
s[++top] = v;
for(i=1;i<=n;i++)
{
if(a[v][i] == 1&& visited[i] == 0 )
{
                           printf("%d ", i);
                          dfs(i);
}
}
}

 int main()
{

          int ch, start, i,j;
         printf("\nEnter the number of vertices in graph:  ");
         scanf("%d",&n);
         printf("\nEnter the adjacency matrix:\n");
         for(i=1; i<=n; i++)
         {
                for(j=1;j<=n;j++)
                        scanf("%d",&a[i][j]);
          }

     for(i=1;i<=n;i++)
           visited[i]=0;
    printf("\nEnter the starting vertex: ");
    scanf("%d",&start);

         printf("\n==>1. BFS: Print all nodes reachable from a given starting node");
        printf("\n==>2. DFS: Print all nodes reachable from a given starting node");
        printf("\n==>3:Exit");
        printf("\nEnter your choice: ");
        scanf("%d", &ch);
        switch(ch)
        {
            case 1: printf("\nNodes reachable from starting vertex %d are: ", start);
                    bfs(start);
                    for(i=1;i<=n;i++)
                    {
                        if(visited[i]==0)
                            printf("\nThe vertex that is not reachable is %d" ,i);
                    }
                    break;
            case 2: printf("\nNodes reachable from starting vertex %d are:\n",start);
                    dfs(start);
                    break;
           case 3: exit(0);
           default: printf("\nPlease enter valid choice:");
        }
}
Output:




Case 1:
Enter the number of vertices in graph:  4
Enter the adjacency matrix:
0          1          0          1
0          0          1          0
0          0          0          1
0          0          0          0


~~~Menu~~~~
==>1. BFS: Print all nodes reachable from a given starting node
==>2. DFS: Print all nodes reachable from a given starting node
==>3:Exit
Enter your choice: 1
Enter the starting vertex: 1
Nodes reachable from starting vertex 1 are: 2       4          3

Case 2:
Enter the number of vertices in graph:  4
Enter the adjacency matrix:
0          1          0          1
0          0          1          0
0          0          0          1
0          0          0          0
~~~Menu~~~~
==>1. BFS: Print all nodes reachable from a given starting node
==>2. DFS: Print all nodes reachable from a given starting node
==>3:Exit
Enter your choice: 1
Enter the starting vertex: 2
Nodes reachable from starting vertex 2 are:  3      4
The vertex that is not reachable is 1

Case 3:
Enter the number of vertices in graph:  4
Enter the adjacency matrix:
0          1          0          1
0          0          1          0
0          0          0          1
0          0          0          0
~~~Menu~~~~
==>1. BFS: Print all nodes reachable from a given starting node
==>2. DFS: Print all nodes reachable from a given starting node
==>3:Exit
Enter your choice: 2
Enter the starting vertex:     1
Nodes reachable from starting vertex 1 are:  2       3       4

Case 4:
Enter the number of vertices in graph:  4
Enter the adjacency matrix:
0          1          0          1
0          0          1          0
0          0          0          1
0          0          0          0
~~~Menu~~~~
==>1. BFS: Print all nodes reachable from a given starting node
==>2. DFS: Print all nodes reachable from a given starting node
==>3:Exit
Enter your choice: 2
Enter the starting vertex:     2
Nodes reachable from starting vertex 2 are:   3       4
Posted by at No comments:
Labels: , , , , ,

Friday 30 September 2016

Lab Program 10 Binary Search Tree 15CSL38 Data Structures in C Lab

Lab Program 10:

Design, Develop and Implement a menu driven Program in C for the following operations on Binary Search Tree (BST) of Integers
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate messaged.
d. Exit











#include<stdio.h>
#include<stdlib.h> 

struct BST
{
            int data;
            struct BST *lchild;
            struct BST *rchild;
};
typedef struct BST * NODE;

NODE create()
{
            NODE temp;
            temp = (NODE) malloc(sizeof(struct BST));
            printf("\nEnter The value: ");
            scanf("%d", &temp->data);


            temp->lchild = NULL;
            temp->rchild = NULL;
            return temp;
}

void insert(NODE root, NODE newnode);
void inorder(NODE root);
void preorder(NODE root);
void postorder(NODE root);
void search(NODE root);

void insert(NODE root, NODE newnode)
{
    /*Note: if newnode->data ==  root->data it will be skipped. No duplicate nodes are allowed */
           
            if (newnode->data < root->data)
            {
                        if (root->lchild == NULL)
                                    root->lchild = newnode;
                        else
                                    insert(root->lchild, newnode);
            }
            if (newnode->data > root->data)
            {
                        if (root->rchild == NULL)
                                    root->rchild = newnode;
                        else
                                    insert(root->rchild, newnode);
            }
}


void search(NODE root)
{
            int key;
            NODE cur;
            if(root == NULL)
            {
                        printf("\nBST is empty.");
                        return;
            }
            printf("\nEnter Element to be searched: ");
            scanf("%d", &key);
            cur = root;
            while (cur != NULL)
            {
                        if (cur->data == key)
                        {
                                    printf("\nKey element is present in BST");
                                    return;
                        }
                        if (key < cur->data)
                                    cur = cur->lchild;
                        else
                                    cur = cur->rchild;
            }
            printf("\nKey element is not found in the BST");
}

void inorder(NODE root)
{
            if(root != NULL)
            {
                        inorder(root->lchild);
                        printf("%d ", root->data);
                        inorder(root->rchild);
            }
}

void preorder(NODE root)
{
            if (root != NULL)
            {
                        printf("%d ", root->data);
                        preorder(root->lchild);
                        preorder(root->rchild);
            }
}

void postorder(NODE root)
{
            if (root != NULL)
            {
                        postorder(root->lchild);
                        postorder(root->rchild);
                        printf("%d ", root->data);
            }
}


void main()
{
            int ch, key, val, i, n;
            NODE root = NULL, newnode;
            while(1)
            {
                        printf("\n~~~~BST MENU~~~~");
                        printf("\n1.Create a BST");
                        printf("\n2.Search");
                        printf("\n3.BST Traversals: ");
                        printf("\n4.Exit");
                        printf("\nEnter your choice: ");
                        scanf("%d", &ch);
                        switch(ch)
                        {
                                    case 1:             printf("\nEnter the number of elements: ");
                                                            scanf("%d", &n);
                                                            for(i=1;i<=n;i++)
                                                            {
                                                                        newnode = create();
                                                                        if (root == NULL)
                                                                                    root = newnode;
                                                                        else
                                                                                    insert(root, newnode);
                                                            }
                                                            break;
                                     case 2:             if (root == NULL)
                                                                       printf("\nTree Is Not Created");
                                                            else
                                                            {
                                                                        printf("\nThe Preorder display : ");
                                                                        preorder(root);
                                                                        printf("\nThe Inorder display : ");
                                                                        inorder(root);
                                                                        printf("\nThe Postorder display : ");
                                                                        postorder(root);
                                                            }

                                                            break;
                                     case 3:            search(root);
                                                            break;
                                     
                                    case 4:     exit(0);
                        }
            }
}

Output:
~~~~BST MENU~~~~
1.Create a BST
2.Search
3.BST Traversals:
4.Exit
Enter your choice: 1

Enter the number of elements: 12
Enter The value: 6
Enter The value: 9
Enter The value: 5
Enter The value: 2
Enter The value: 8
Enter The value: 15
Enter The value: 24
Enter The value: 14
Enter The value: 7
Enter The value: 8
Enter The value: 5
Enter The value: 2

~~~~BST MENU~~~~
1.Create a BST
2.Search
3.BST Traversals:
4.Exit
Enter your choice: 3

The Preorder display:           6          5          2          9          8          7          15        14        24
The Inorder display:             2          5          6          7          8          9          14        15        24
The Postorder display:         2          5          7          8          14        24        15        9          6

~~~~BST MENU~~~~
1.Create a BST
2.Search
3.BST Traversals:
4.Exit
Enter your choice: 2

Enter Element to be searched: 66
Key element is not found in the BST

~~~~BST MENU~~~~
1.Create a BST
2.Search
3.BST Traversals:
4.Exit
Enter your choice: 2

Enter Element to be searched: 14
Key element is present in BST

~~~~BST MENU~~~~
1.Create a BST
2.Search
3.BST Traversals:
4.Exit
Enter your choice: 4

Posted by at No comments:
Labels: , ,
Subscribe to: Posts (Atom)