Scribd Logo
Upload

Welcome to Scribd!

  • 19 views

    19BCS2206 (Worksheet 3.1)

    Uploaded by

    NIKHIL SHARMA
    The document contains code to perform depth-first search (DFS) and topological sorting on graphs. For DFS, it creates a recursive function that marks nodes as visited and prints each node while traversing all unvisited adjacent nodes. For topological sorting, it creates a directed acyclic graph using edges, marks all vertices as unvisited, and calls a recursive utility function to store the sorted vertices in a stack. The code includes classes to represent graphs and functions for DFS, adding edges, and topological sorting traversal.

    Copyright:

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

    19BCS2206 (Worksheet 3.1)

    Uploaded by

    NIKHIL SHARMA
    19 views5 pages
    The document contains code to perform depth-first search (DFS) and topological sorting on graphs. For DFS, it creates a recursive function that marks nodes as visited and prints each node while traversing all unvisited adjacent nodes. For topological sorting, it creates a directed acyclic graph using edges, marks all vertices as unvisited, and calls a recursive utility function to store the sorted vertices in a stack. The code includes classes to represent graphs and functions for DFS, adding edges, and topological sorting traversal.

    Original Description:

    cse

    Original Title

    19BCS2206 (Worksheet 3.1) Converted

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains code to perform depth-first search (DFS) and topological sorting on graphs. For DFS, it creates a recursive function that marks nodes as visited and prints each node while traversing all unvisited adjacent nodes. For topological sorting, it creates a directed acyclic graph using edges, marks all vertices as unvisited, and calls a recursive utility function to store the sorted vertices in a stack. The code includes classes to represent graphs and functions for DFS, adding edges, and topological sorting traversal.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    19 views5 pages

    19BCS2206 (Worksheet 3.1)

    Uploaded by

    NIKHIL SHARMA
    The document contains code to perform depth-first search (DFS) and topological sorting on graphs. For DFS, it creates a recursive function that marks nodes as visited and prints each node while traversing all unvisited adjacent nodes. For topological sorting, it creates a directed acyclic graph using edges, marks all vertices as unvisited, and calls a recursive utility function to store the sorted vertices in a stack. The code includes classes to represent graphs and functions for DFS, adding edges, and topological sorting traversal.

    Copyright:

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

    Worksheet 3.

    Student name: Yash Kumar UID: 19BCS2206

    Branch: BE-CSE Section/group: CSE-8 / C


    Semester: 5th Date: 10-11-2021

    Subject name: Design & Analysis of Algo. Lab Subject code: CSP-309

    Aim:
    Code to analyze to do a depth-first search (DFS) on an undirected graph. Implementing
    an application of DFS such as:
    a) To find the topological sort of directed acyclic graph, OR
    b) To find a path from source to goal in a maze.

    Algorithm:

    (Depth First Search)


    Step 1: Create a recursive function that takes the index of the node and a visited array.
    Step 2: Mark the current node as visited and print the node.
    Step 3: Traverse all the adjacent & unmarked nodes and call the recursive function with
    the index of the adjacent nodes.
    Step 4: Run a loop from 0 to the number of vertices and check if the node is unvisited in
    the previous DFS, call the recursive function with the current node.

    Algorithm:

    (Topology Sort)
    Step 1: Create the graph by calling addEdge(a,b).
    Step 2: Call the topologicalSort( )
    Step 3: Create a stack and a Boolean array named as visited [ ];
    Step 4: Mark all the vertices as not visited i.e. initialize visited [ ] with 'false' value.
    Step 5: Call the recursive helper function topologicalSortUtil() to store Topological Sort
    starting from all vertices one by one.
    Step 6: def topologicalSortUtil(int v, bool visited[],stack<int> &Stack):
    Step 7: Mark the current node as visited.
    Step 8: Recur for all the vertices adjacent to this vertex.
    Step 9: Push current vertex to stack which stores result.
    Step 10: At last, after return from the utility function, print contents of stack.

    Worksheet 3.1 1
    Cod
    (Depth First Search)

    #include <bits/stdc++.h>
    using namespace std;
    class Graph
    {
    public:
    map<int, bool> visited;
    map<int, list<int>> adj;
    void add(int v, int w);
    void DFS(int v);
    };

    void Graph::add(int v, int w)


    {
    adj[v].push_back(w);
    }

    void Graph::DFS(int v)
    {
    visited[v] = true;
    cout << v << " ";
    list<int>::iterator
    I;
    for (i = adj[v].begin(); i != adj[v].end(); +
    +i) if (!visited[*i])
    DFS(*i);
    }

    int main()
    {
    Graph g;
    int n,a,b
    cout<<"Enter number of adjacent pair of
    nodes:"; cin>>n;

    cout<<"Enter Pair: \n";

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

    cout<<"Pair"<<i<<":";
    cin>>a>>b;

    g.add(a,b);
    }

    int s;
    cout<<"Enter Starting node(root):";
    cin>>s;

    cout<<"/nFollowing is Depth First Traversal starting from


    vertex"<<s<<"/n";

    g. DFS(s);
    return 0;
    }

    Worksheet 2
    OUTPU

    (Depth First Search)

    Worksheet 3
    Cod
    (Topology Sorting)

    #include <bits/stdc++.h>
    using namespace std;

    Class Graph{

    Int V;
    List<int>*adj;
    Void topological Sort Util(int v,bool visited[],stack<int>&
    Stack); public:
    Graph(int V);
    void add(int v, int w); void topological Sort();
    };

    Graph::Graph(int V){
    this->V = V;
    adj = new list<int>[V];

    }
    void Graph::add(int v, int w)
    { adj[v].push_back(w);
    }

    Void Graph::topological Sort Util(int v, bool visited[],


    stack<int>&Stack){

    Visited[v] = true
    List<int>::iterator i;
    for (i = adj[v].begin(); i ! =adj[v].end(); +
    +i) if (!visited [*i])
    topological Sort Util(*i, visited ,Stack);
    Stack.push(v);
    }

    void Graph:: topological Sort()


    { stack<int>Stack;
    bool* visited = new bool [V];
    for (int i = 0; i< V; i++)
    visited[i] = false;
    for (int i = 0; i < V; i++)
    if (visited[i] == false)
    topologicalSortUtil(i, visited, Stack);
    while (Stack.empty() == false){
    cout << Stack.top() << "
    "; Stack.pop();
    }
    }
    int main()
    { int n, a,
    b;
    cout<<"Enter Stack Size for Topology: ";
    cin>>n; Graph g(n);
    cout<<"Enter Adjecent pairs: \n"; for(int i=1;i<=n;i++)
    { cout<<"Enter Pair "<<i<<" :"; cin>>a>>b;
    g.a dd(a, b);
    }
    cout << "Topological Sort of the given graph \n";
    g.topologicalSort();
    return 0;
    }

    Worksheet 4
    OUTPU

    (Topology Sorting)

    Learning Outcomes:
    a) I learnt how to perform depth first traversal.
    b) I learnt how to perform traversing in a graph
    c) I learnt how topological sorting is done.

    Worksheet 5

    You might also like