Depth First Search : C program

consider the following graph and its adjacency matrix:









One of the DFS traversal of the graph is
0 1 2 3 4

Program :DFS
 
#include<stdio.h>

int a[20][20],q[20],visited[20],n;

void dfs(int v)
{
       int i;
       for (i=0;i<n;i++)                                // check all the vertices in the graph
       {
               if(a[v][i] != 0 && visited[i] == 0) // adjacent to v and not visited
              {
                       visited[i]=1;          // mark the vertex visited
                       printf("%d  ",i);
                       dfs(i);
              }
      }
}
int main()
{
    int v,i,j;
    printf("\n Enter the number of vertices:");
    scanf("%d",&n);
    for (i=0;i<n;i++)
    {
        visited[i]=0;
    }
    printf("\n Enter graph data in matrix form:\n");
    for (i=0;i<n;i++)
      for (j=0;j<n;j++)
       scanf("%d",&a[i][j]);
    printf("\n Enter the starting vertex:");
    scanf("%d",&v);
    printf("\n DFS traversal is:\n");
    visited[v]=1; // mark the starting vertex as visited
    printf("%d   ",v);
   
    dfs(v);
}

Output:

Output:

 Enter the number of vertices: 5

 Enter graph data in matrix form:
0 1 0 0 1
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
1 1 0 1 0

 Enter the starting vertex:0
 
DFS traversal is:
0   1  2  3  4

Breadth first search : C program

Algorithm for BFS:
Step 1: Start
Step 2: Choose the starting vertex and insert it into queue
Step 3: Find the vertices that have direct edges with the vertex (vertex which is at front of the queue)
Step 4: Insert all the vertices found in step 3 into queue
Step 5: Remove the first vertex in queue
Step 6: Continue this process until all the vertices are visited
Step 7: Stop


Consider the graph as shown and its adjacency matrix

One of the BFS traversal of the graph is
0 1 4 2 3












Program : BFS

#include<stdio.h>

int a[20][20],q[20],visited[20],n,f=-1,r=-1;

void bfs(int v) 
{
       int i;
       for (i=0;i<n;i++)                                // check all the vertices in the graph
       {
               if(a[v][i] != 0 && visited[i] == 0) // adjacent to v and not visited
              {
                       r=r+1;
                       q[r]=i;                       // insert them into queue
                       visited[i]=1;          // mark the vertex visited
                       printf("%d  ",i);
              }
      }
      f=f+1;                             // remove the vertex at front of the queue
      if(f<=r)                           // as long as there are elements in the queue
            bfs(q[f]);                  // peform bfs again on the vertex at front of the queue

}main()
{
    int v,i,j;
    printf("\n Enter the number of vertices:");
    scanf("%d",&n);
    for (i=0;i<n;i++)                   // mark all the vertices as not visited
    {
        visited[i]=0;
    }
    printf("\n Enter graph data in matrix form:\n");
    for (i=0;i<n;i++)
      for (j=0;j<n;j++)
       scanf("%d",&a[i][j]);
    printf("\n Enter the starting vertex:");
    scanf("%d",&v);
    f=r=0;
    q[r]=v;
    printf("\n BFS traversal is:\n");
    visited[v]=1;                                     // mark the starting vertex as visited
    printf("%d   ",v);
   
    bfs(v);
    if(r != n-1)
        printf("\n BFS is not possible");
}

Output:

 Enter the number of vertices: 5

 Enter graph data in matrix form:
0 1 0 0 1
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
1 1 0 1 0

 Enter the starting vertex:0

 BFS traversal is:
0   1  4  2  3 


 How to solve maze or shortest path grid problems using BFS 
https://www.youtube.com/watch?v=KiCBXu4P-2Y
https://www.youtube.com/watch?v=oDqjPvD54Ss

https://www.youtube.com/watch?v=OrS7PaJ-5ck

Python code to Read the data in first column in excel file (Text to speech using pyttsx )

import pyttsx

import openpyxl

import time

filename=str(raw_input('enter path to excel file: ')) # enter the complete path of excel file

wb = openpyxl.load_workbook(filename)

ws = wb.get_sheet_by_name('Sheet1') # gets Sheet1 in excel

rowcount=ws.max_row

def say(s):

       engine = pyttsx.init()

       engine.setProperty('volume', 0.2)

       engine.setProperty('rate', 100)

       voices= engine.getProperty('voices')                                                               

       engine.setProperty('voice', 'english-us')                 

       engine.say(s)

       a = engine.runAndWait()

if __name__== "__main__":

       for i in range(rowcount):              # loop through entire rows in excel

               mytext = str(ws.cell(row=i+1,column=1).value) # gets the first column data

               say(mytext)


Usage:
Create an excel file and write any text in the first column as shown below and save it. In this example, i have saved the file in Desktop with the name SEC8

Once u run the python code, you will be asked to
Enter the path where the excel file is
here i have saved the excel file at C:\Users\SARVANI\Desktop\SEC8.xlsx
The excel file name is SEC8.xlsx

C program Prims spanning tree

Prims Algorithm:
Step 1: Start
Step 2: Read a weighted Graph G(V, E)
Step 3: Let n be the number of vertices in the graph G
Step 4: Choose the starting vertex say V1 and add it to visited array
Step 5: Find the lowest cost edge coming out of Vertices in visited array
Step 6: if a cycle is formed if this lowest cost edge is drawn then
                Take the next lowest cost edge
Step 7: else
                 Draw the edge
                 Add the vertex to visited array 
Step 8: Go to step 3 until n-1 edges are drawn
Step 9: STOP

 ================================
Program:
 
#include<stdio.h>
int prims(int [][],int);
main()
{
  int n,cost[10][10];
  int mincost=0;
  printf("enter number of vertices\n");
  scanf("%d",&n);
  printf("enter cost of each edge\n");
  for(i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
     printf("enter %d%d edge cost\n",i,j);
    scanf("%d",&cost[i][j]);
    }
  }
    mincost=prims(cost,n);
    printf("the prim cost edge of given spanning tree is %d",mincost);
 }

    int prims(int cost [][],int n)
    {
       int mcost=0,mincostedge,t[20][20];
       mincostedge=cost[1][1];
       for(int i=1;i<=n;i++)
       {
         for(int j=1;j<=n;j++)
         {
           if(cost[i][j]<=mincostedge)
           {
             mincostedge=cost[i][j];
             k=i;
             l=j;
           }
        }
      }
       for(i=1;i<=n;i++)
       {
         if(cost[k][i]<cost[l][i])
             near[i]=k;
         else
            near[i]=l;
       }
       near[k]=0;
       near[l]=0;
       mincost=mincost+cost[k][l];
      t[1,1]=k;
      t[1,2]=l;
      for(int i=2;i<=n-1;i++)
      {
       for(b=1;b<=n;b++)
       {
         if(near[b]!=0)
         {
           min=cost[b][near[b]];
          
           t[i][1]=b;
           t[i][2]=near[j];
           mincost=mincost+cost[j][near[j]];
           near[j]=0;
      for(k=1;k<n;k++)
      {
        if(near[k]!=0&&cost[k][near[k]]>cost[j][k])
        {
          near[k]=j;
        }
      }
      return mincost;
  }
 
 
   
  

Krushkal Minimum spanning tree : C program

Krushkal Algorithm:
Step 1: Start
Step 2: Read a weighted Graph G(V, E)
Step 3: Let n be the number of vertices in the graph G
Step 4: Find the lowest cost edge and draw it
Step 5: Choose the next lowest cost edge 
Step 6: if a cycle is formed if this lowest cost edge is drawn then
                Take the next lowest cost edge
Step 7: else
                 Draw the edge
Step 8: Go to step 3 until n-1 edges are drawn
Step 9: STOP
 ===========================================================
 Program:

#include<stdio.h>
int find(int i);
void union1(int,int);
int parent[10];
struct sample
{
  int u;
  int v;
  int cost;
};
typedef struct sample krushkals;
int sample(krushkals[],int,int);
main()
{
  krushkals d[10];
  int n,e,i,mincost;
  printf("enter number of vertices\n");
  scanf("%d",&n);
  printf("enter number of edges\n");
  scanf("%d",&e);
  for(i=1;i<=e;i++)
  {
    printf("enter the starting vertex\n");
    scanf("%d",&d[i].u);
    printf("enter the ending vertex\n");
    scanf("%d",&d[i].v);
    printf("enter their costs\n");
    scanf("%d",&d[i].cost);
  }
   mincost=sample(d,e,n);
   printf("mincost of a spanning tree is %d",mincost);
}




int sample(krushkals d[10],int e,int n)
{
  int mincost=0;
  int j,l,k,u,v,i;
  int t[10][10];
  krushkals temp;
  for(i=1;i<e;i++)
  {
   for(j=i+1;j<=e;j++)
   {
     if(d[i].cost>d[j].cost)
     {
       temp=d[i];
       d[i]=d[j];
       d[j]=temp;
     }
   }
  }
  for(i=1;i<=n;i++)
 parent[i]=-1;
 i=1;
 l=1;
  while(i<=n-1&&l<=e)
  {
     j=find(d[l].u);
     k=find(d[l].v);
     if(j!=k)
     {
       t[i][1]=d[l].u;
       t[i][2]=d[l].v;
       printf("t[%d][1]=%d\n",i,d[l].u);
       printf("t[%d][2]=%d\n",i,d[l].v);
       printf("path is %d->%d\n",d[l].u,d[l].v);
       mincost=mincost+d[l].cost;
       i++;
       union1(j,k);
     }
     l++;
   }
   if(i!=n)
   printf("no spanning tree\n");
   else
   return mincost;
}



 int find(int i)
 {
   while(parent[i]!=-1)
   {
     i=parent[i];
   }
   return i;
}


void union1(int i,int j)
{
   parent[i]=j;
}