DAA P4 bfs, dfs

-

BFS

#include <bits/stdc++.h>
using namespace std;
class Graph {
  int V;
  vector<list<int> > adj;

public:
  Graph(int V);
  void addEdge(int v, int w);
  void BFS(int s);
};

Graph::Graph(int V)
{
  this->V = V;
  adj.resize(V);
}

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

void Graph::BFS(int s)
{
  vector<bool> visited;
  visited.resize(V, false);

  list<int> queue;

  visited[s] = true;
  queue.push_back(s);

  while (!queue.empty()) {
   
    s = queue.front();
    cout << s << " ";
    queue.pop_front();

    for (auto adjacent : adj[s]) {
      if (!visited[adjacent]) {
        visited[adjacent] = true;
        queue.push_back(adjacent);
      }
    }
  }
}
int main()
{
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(3, 3);

  cout << "Following is Breadth First Traversal "
    << "(starting from vertex 2) \n";
  g.BFS(2);

  return 0;
}

DFS


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

class Graph {
public:
  map<int, bool> visited;
  map<int, list<int> > adj;
  void addEdge(int v, int w);
  void DFS(int v);
};

void Graph::addEdge(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;
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(3, 3);

  cout << "Following is Depth First Traversal"
      " (starting from vertex 2) \n";
  g.DFS(2);

  return 0;
}



Comments

Post a Comment

Popular posts from this blog

DAA P8 graph coloring

-
  Graph coloring // A C++ program to implement greedy algorithm for graph coloring #include < iostream > #include < list > using namespace std ; // A class that represents an undirected graph class Graph {   int V ; // No. of vertices   list <int> * adj ; // A dynamic array of adjacency lists public :   // Constructor and destructor   Graph ( int V ) { this -> V = V ; adj = new list <int> [ V ]; }   ~Graph ()   { delete [] adj ; }   // function to add an edge to graph   void addEdge ( int v , int w );   // Prints greedy coloring of the vertices   void greedyColoring (); }; void Graph :: addEdge ( int v , int w ) {   adj [ v ]. push_back ( w );   adj [ w ]. push_back ( v ); // Note: the graph is undirected } // Assigns colors (starting from 0) to all vertices and prints // the assignment of colors void Graph :: greedyColoring () {   int result [ V ];   //...
Read more

Practical 8 by Karan

-
 #include <stdio.h> struct emp { int no; int sal; char name[20]; };   int binarySearch(struct emp a[], int n, int x) {        int low=0, mid, high=n-1, count = 0;    while(low <= high)    {        count++;         mid = (low + high) / 2;         if (x < a[mid].no)             high = mid - 1;         else if (x > a[mid].no)          low = mid + 1;        else {         printf("no of search = %d\n",count);       return mid;        }    } return -1; }    void printArray(struct emp array[], int size) {   for (int i = 0; i < size; ++i) {      printf("name = %s\n",array[i].name);     printf(" salary = %d\n ", array[i].sal);      printf(" number = %d...
Read more