Basic operation performed in graph

/*Basic operation performed in graph*/

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

// A structure to represent an adjacency list node
struct AdjListNode
{
    int dest;
    struct AdjListNode* next;
};

// A structure to represent an adjacency list
struct AdjList
{
    struct AdjListNode *head;
};

// A structure to represent a graph. A graph
// is an array of adjacency lists.
// Size of array will be V (number of vertices
// in graph)
struct Graph
{
    int V;
    struct AdjList* array;
};

// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
    struct AdjListNode* newNode =
     (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
    struct Graph* graph =
        (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;

    // Create an array of adjacency lists.  Size of
    // array will be V
    graph->array =
      (struct AdjList*) malloc(V * sizeof(struct AdjList));

    // Initialize each adjacency list as empty by
    // making head as NULL
    int i;
    for (i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{

    // Add an edge from src to dest.  A new node is  
        // added to the adjacency list of src.  The node
    // is added at the begining
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // Since graph is undirected, add an edge from
    // dest to src also
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// A utility function to print the adjacency list
// representation of graph
void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->V; ++v)
    {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl)
        {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

// Driver program to test above functions
int main()
{
    // create the graph given in above fugure
    int V = 5;
    struct Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    // print the adjacency list representation of the above graph
    printGraph(graph);

    return 0;
}

----------------------------------------------------------
OUTPUT:-
   

sk.

Depth First Search (DFS) Program in C

/*Depth First Search (DFS) Program in C */

#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);

}

----------------------------------------------------------
OUTPUT:-

sk.

C programming code for binary search

/*C programming code for binary search*/

#include <stdio.h>

 

int main()

{

   int c, first, last, middle, n, search, array[100];

 

   printf("Enter number of elements\n");

   scanf("%d",&n);

 

   printf("Enter %d integers\n", n);

 

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

      scanf("%d",&array[c]);

 

   printf("Enter value to find\n");

   scanf("%d", &search);

 

   first = 0;

   last = n - 1;

   middle = (first+last)/2;

 

   while (first <= last) {

      if (array[middle] < search)

         first = middle + 1;    

      else if (array[middle] == search) {

         printf("%d found at location    %d.\n", search, middle+1);

         break;

      }

      else

         last = middle - 1;

 

      middle = (first + last)/2;

   }

   if (first > last)

      printf("Not found! %d isn't present in the list.\n", search);

 

   return 0;  

}

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

OUTPUT:-

sk.

Binary search tree

/*Binary search tree*/    


#include<stdio.h>
#include<stdlib.h> 
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* createNode(value){
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
} 
struct node* insert(struct node* root, int data)
{
    if (root == NULL) return createNode(data);
    if (data < root->data)
        root->left  = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data); 
    return root;

}
void inorder(struct node* root){
    if(root == NULL) return;
    inorder(root->left);
    printf("%d ->", root->data);
    inorder(root->right);
}
int main(){
    struct node *root = NULL;
    root = insert(root, 8);
    insert(root, 3);
    insert(root, 1);
    insert(root, 6);
    insert(root, 7);
    insert(root, 10);
    insert(root, 14);
    insert(root, 4);
    inorder(root);
}

----------------------------------------------------------
OUTPUT:-

sk.

Insertion sort algorithm implementation in C

/*Insertion sort algorithm implementation in C*/

/* Insertion sort ascending order */

 

#include <stdio.h>

 

int main()

{

  int n, array[1000], c, d, t;

 

  printf("Enter number of elements\n");

  scanf("%d", &n);

 

  printf("Enter %d integers\n", n);

 

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

    scanf("%d", &array[c]);

 

  for (c = 1 ; c <= n - 1; c++) {

    d = c;

 

    while ( d > 0 && array[d-1] > array[d]) {

      t          = array[d];

      array[d]   = array[d-1];

      array[d-1] = t;

 

      d--;

    }

  }

 

  printf("Sorted list in ascending order:\n");

 

  for (c = 0; c <= n - 1; c++) {

    printf("%d\n", array[c]);

  }

 

  return 0;

}

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

OUTPUT:-

sk.

Merge Sort Program in C

/*Merge Sort Program in C*/

#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
   int l1, l2, i;
   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   while(l1 <= mid)   
      b[i++] = a[l1++];
   while(l2 <= high) 
      b[i++] = a[l2++];
   for(i = low; i <= high; i++)
      a[i] = b[i];
}
void sort(int low, int high) {
   int mid;
 
   if(low < high) {
      mid = (low + high) / 2;
      sort(low, mid);
      sort(mid+1, high);
      merging(low, mid, high);
   } else {
      return;
   } 
}

int main()
{
     int i;
   printf("List before sorting\n");
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
   sort(0, max);
   printf("\nList after sorting\n");
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
}

----------------------------------------------------------
OUTPUT:-

sk.

Selection sort algorithm implementation in C

/*Selection sort algorithm implementation in C*/

#include <stdio.h>

 

int main()

{

  int array[100], n, c, d, position, swap;

 

  printf("Enter number of elements\n");

  scanf("%d", &n);

 

  printf("Enter %d integers\n", n);

 

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

    scanf("%d", &array[c]);

 

  for (c = 0; c < (n - 1); c++)

  {

    position = c;

   

    for (d = c + 1; d < n; d++)

    {

      if (array[position] > array[d])

        position = d;

    }

    if (position != c)

    {

      swap = array[c];

      array[c] = array[position];

      array[position] = swap;

    }

  }

 

  printf("Sorted list in ascending order:\n");

 

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

    printf("%d\n", array[c]);

 

  return 0;

}

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

OUTPUT:-

sk.