Scribd Logo
Upload

Welcome to Scribd!

  • 32 views

    DFS and BFS On Graph

    Uploaded by

    Khyathi Kiran
    The C program allows the user to create a graph using an adjacency matrix, and then performs breadth-first search (BFS) and depth-first search (DFS) on the graph to output the nodes reachable from a given source node.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    DFS and BFS On Graph

    Uploaded by

    Khyathi Kiran
    32 views4 pages
    The C program allows the user to create a graph using an adjacency matrix, and then performs breadth-first search (BFS) and depth-first search (DFS) on the graph to output the nodes reachable from a given source node.

    Original Title

    DFS and BFS on Graph (1)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The C program allows the user to create a graph using an adjacency matrix, and then performs breadth-first search (BFS) and depth-first search (DFS) on the graph to output the nodes reachable from a given source node.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    32 views4 pages

    DFS and BFS On Graph

    Uploaded by

    Khyathi Kiran
    The C program allows the user to create a graph using an adjacency matrix, and then performs breadth-first search (BFS) and depth-first search (DFS) on the graph to output the nodes reachable from a given source node.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 4

    11.

    Develop 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[10][10], n, i, j, source, queue[10];
    int visit_bfs[10], visit_dfs[10];

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

    void bfs(int source)


    {
    int u, front=0, rear=-1, k=1; //k is to hold sequence of vertices considered
    queue[++rear] = source;
    visit_bfs[source] = 1;
    printf("%d\t", source);
    while(front<=rear)
    {
    u = queue[front++];
    for(i=1; i<=n; i++)
    {
    if(a[u][i] == 1 && visit_bfs[i] == 0)
    {
    queue[++rear] = i;
    visit_bfs[i] = 1;
    printf("%d\t", i);
    }
    }
    }
    }

    void dfs(int source)


    {
    int v, top = -1, p=1;
    visit_dfs[source] = 1;
    printf("%d\t", source);
    for(v=1; v<=n; v++)
    {
    if(a[source][v] == 1 && visit_dfs[v] == 0)
    {

    dfs(v);
    }
    }
    }

    void main()
    {
    int ch;
    while(1)
    {
    printf("\n------------- GRAPH TRAVERSALS ---------------");
    printf("\n 1.Create Graph\n 2.BFS & DFS\n 3.Exit");
    printf("\nEnter your choice: ");
    scanf("%d", &ch);
    switch(ch)
    {
    case 1:
    create_graph();
    break;
    case 2:
    printf("\nEnter the source vertex to find other nodes reachable or not: ");
    scanf("%d", &source);
    printf("Nodes Reachable from Source Vertex using BFS\n");
    bfs(source);
    for(i=1; i<=n; i++)
    if(visit_bfs[i]==0)
    printf("\nThe vertex that is not reachable %d",i);

    printf("\nNodes Reachable from Source Vertex using DFS\n");


    dfs(source);

    break;
    default:
    exit(0);
    }
    }
    }

    Output:
    ------------- GRAPH TRAVERSALS ---------------
    1.Create Graph
    2.BFS & DFS
    3.Exit
    Enter your choice: 1

    Enter the number of vertices of the digraph: 4


    Enter the adjacency matrix of the graph:
    0011
    0000
    0100
    0100

    ------------- GRAPH TRAVERSALS ---------------


    1.Create Graph
    2.BFS & DFS
    3.Exit

    Enter your choice: 2


    Enter the source vertex to find other nodes reachable or not: 1
    Nodes Reachable from Source Vertex using BFS
    1342
    Nodes Reachable from Source Vertex using DFS
    1324

    ------------- GRAPH TRAVERSALS ---------------


    1.Create Graph
    2.BFS & DFS
    3.Exit
    Enter your choice: 3

    You might also like