I need help with BFS traversal creating for main function : Here is the code tha

ID: 3818284 • Letter: I

Question

I need help with BFS traversal creating for main function :

Here is the code that i have been working with:

Graph.h :

#ifndef GRAPH_H
#define GRAPH_H

#include <string>
#include "Object.h"
#include "Decorator.h"
#include <list>

class Graph {
public:
class Edge;
class Vertex;
typedef std::list<Vertex*> VertexList;
typedef std::list<Edge*> EdgeList;
typedef std::list<Vertex*>::const_iterator VertexItor;
typedef std::list<Edge*>::const_iterator EdgeItor;

Graph(){}

class Edge
{
private:
  Decorator key;
  bool directed;
public:
  std::pair<Vertex*, Vertex*> pair;

Edge() {}

  void set(std::string _status, Object* yn) {
   key.set(_status, yn);
  }

  Object* get(std::string prop) {
   return key.get(prop);
  }

  Vertex* opposite(Vertex &v)
  {
   if (!directed)
   {
    if (&v == pair.first)
     return pair.second;
    else
     return pair.first;
   }
   else
    return NULL;
  }

  Vertex* origin()
  {
   if (directed)
    return pair.first;
   else
    return NULL;
  }

  Vertex* dest()
  {
   if (directed)
    return pair.second;
   else
    return NULL;
  }

  bool isDirected()
  {
   return directed;
  }

  void setIsDirected(bool value)
  {
   directed = value;
  }

  bool isVisited()
  {
   return directed;
  }
};

class Vertex
{
private:
Decorator key;
EdgeList edges;

public:
Vertex() {}

  EdgeList* getEdges() {
   return &edges;
  }

  void set(std::string _status, Object* yn) {
   key.set(_status, yn);
  }

  Object* get(std::string prop) {
   return key.get(prop);
  }

  void insertEdge(Edge& e)
  {
   edges.push_back(&e);
  }

  EdgeList* incidentEdges() {
   return getEdges();
  }
};

private:
VertexList m_Vertices;
EdgeList m_Edges;

public:
VertexList* vertices() {
return &m_Vertices;
}

EdgeList* edges() {
return &m_Edges;
}

void insertVertex(Vertex& a)
{
m_Vertices.push_back(&a);
}

void insertEdge(Vertex& origin, Vertex& end, Edge& edge)
{
  edge.setIsDirected(false);
  edge.pair.first = &origin;
  edge.pair.second = &end;

origin.insertEdge(edge);
end.insertEdge(edge);

m_Edges.push_back(&edge);
}

void insertDirectedEdge(Vertex& origin, Vertex& end, Edge& edge)
{
  edge.setIsDirected(true);
  edge.pair.first = &origin;
  edge.pair.second = &end;

origin.insertEdge(edge);
end.insertEdge(edge);

m_Edges.push_back(&edge);
}

void eraseVertex(Vertex& v) {
}

void eraseEdge(Edge& e) {
}
};

#endif

BFS.h :

#ifndef BFS_H
#define BFS_H

#include <list>
#include <string>
#include <Queue>
#include <algorithm>
#include "Object.h"
#include "Graph.h"

template <typename G>
class BFS
{      // generic DFS
protected:       // local types
typedef typename G::Vertex Vertex;   // vertex position
typedef typename G::Edge Edge;   // edge position
typedef typename std::queue<Vertex*> VertexQueue;
typedef typename std::list<Vertex*> VertexList;
typedef typename std::list<Edge*> EdgeList;
typedef typename std::list<Vertex*>::const_iterator VertexItor;
typedef typename std::list<Edge*>::const_iterator EdgeItor;

protected:
const G& graph;     // the graph
Vertex start;     // start vertex
Object *yes, *no;     // decorator values

public:
BFS(const G& g);
void initialize();
void bfsTraversal(Vertex& v);

virtual void startVisit(Vertex& v)
{
std::string n = v.get("node")->stringValue();
std::cout << "-> " << n ;
}

virtual void traverseDiscovery(Edge& e, Vertex& from)
{
  std::string edge = e.get("edge")->stringValue();
  std::string vertex = from.get("node")->stringValue();
  //std::cout << "Discovering " << vertex<< " from edge: " << edge << std::endl;
}
virtual void traverseBack(Edge& e, Vertex& from)
{
  std::string edge = e.get("edge")->stringValue();
  std::string vertex = from.get("node")->stringValue();
  //std::cout << "Go back to " << edge<< " from " << vertex << std::endl;
}
virtual void finishVisit(Vertex& v)
{
  std::string vertex = v.get("node")->stringValue();
  //std::cout << "Exit from node " << vertex<< std::endl;
}
virtual bool isDone()
{
  return false;
}
void visit(Vertex& v) {
  v.set("visited", yes);
}
void visit(Edge& e) {
  e.set("visited", yes);
}
void unvisit(Vertex& v) {
  v.set("visited", no);
}
void unvisit(Edge& e) {
  e.set("visited", no);
}
bool isVisited(Vertex& v) {
  return v.get("visited") == yes;
}
bool isVisited(Edge& e) {
  return e.get("visited") == yes;
}
};

template <typename G> // constructor
BFS<G>::BFS(const G& g)
: graph(g), yes(new Object), no(new Object) {}

template <typename G>     // initialize a new DFS
void BFS<G>::initialize() {
VertexList verts = graph.vertices();
for (VertexItor pv = verts.begin(); pv != verts.end(); ++pv)
  unvisit(*pv);     // mark vertices unvisited
EdgeList edges = graph.edges();
for (EdgeItor pe = edges.begin(); pe != edges.end(); ++pe)
  unvisit(*pe);     // mark edges unvisited
}

template <typename G>
void BFS<G>::bfsTraversal(Vertex& v)
{
VertexQueue vQueue;

visit(v);
vQueue.push(&v);

while (!vQueue.empty())
{
  Vertex* current = vQueue.front();
  startVisit(*current);
  EdgeList* incident = (*current).incidentEdges();
  EdgeItor pe = (*incident).begin();
  while (pe != (*incident).end())
  {
   Edge* e = *pe++;
   if (!isVisited(*e))
   {
    Vertex* w = NULL;
    if ((*e).isDirected() && current == (*e).origin())
     w = e->dest();
    else
     w = (*e).opposite(*current);

    if (w != NULL && !isVisited(*w))
    {
     visit(*w);
     traverseDiscovery(*e, *w);
     vQueue.push(w);
    }
   }
  }
  vQueue.pop();
  finishVisit(*current);
}
}

#endif

Here is the example of what i need to create for main function, anyone like to help me ? thank you

(a) F (c) (e) Figure 1 BFS Traversal Example (b) (d) (f

Explanation / Answer

Breadth First Traversal or BFS for a Graph

Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree (See method 2 of this post). The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Breadth First Traversal of the following graph is 2, 0, 3, 1.

// Program to print BFS traversal from a given source vertex. BFS(int s)

// traverses vertices reachable from s.

#include<iostream>

#include <list>

using namespace std;

// This class represents a directed graph using adjacency list representation

class Graph

{

int V; // No. of vertices

list<int> *adj; // Pointer to an array containing adjacency lists

public:

Graph(int V); // Constructor

void addEdge(int v, int w); // function to add an edge to graph

void BFS(int s); // prints BFS traversal from a given source s

};

Graph::Graph(int V)

{

this->V = V;

adj = new list<int>[V];

}

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

{

adj[v].push_back(w); // Add w to v’s list.

}

void Graph::BFS(int s)

{

// Mark all the vertices as not visited

bool *visited = new bool[V];

for(int i = 0; i < V; i++)

visited[i] = false;

// Create a queue for BFS

list<int> queue;

// Mark the current node as visited and enqueue it

visited[s] = true;

queue.push_back(s);

// 'i' will be used to get all adjacent vertices of a vertex

list<int>::iterator i;

while(!queue.empty())

{

// Dequeue a vertex from queue and print it

s = queue.front();

cout << s << " ";

queue.pop_front();

// Get all adjacent vertices of the dequeued vertex s

// If a adjacent has not been visited, then mark it visited

// and enqueue it

for(i = adj[s].begin(); i != adj[s].end(); ++i)

{

if(!visited[*i])

{

visited[*i] = true;

queue.push_back(*i);

}

// Driver program to test methods of graph class

int main()

{

// Create a graph given in the above diagram

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

g.BFS(2);

return 0;

}

Output: Copy

Following is Breadth First Traversal (starting from vertex 2)

2 0 3 1

Navigate

I need help with B, C, and D. Answer A is already correct if it is needed for ca

I need help with BFS traversal creating for main part : Here is the code that i

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

I need help with BFS traversal creating for main function : Here is the code tha

Question

Explanation / Answer

Related Questions

Navigate