Breath First Search

BFS.cpp

/**Rodrigo Vazquez Espino
  *Luis Armando Arias Romero
  *Implementacion de BreathFirstSearch
  */
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int itemType;
/*
class TreeNode
{
private:
  itemType key;
  TreeNodeList* children;
  TreeNode* pi;//father
};

class TreeNodeList
{
private:
  TreeNode node;
  TreeNode* nextChild;
};*/


/*class AdjList//grafo, lista de nodos
{
private:
  GraphNode node;
  AdjList* adj;
};*/
class GraphNode//nodo
{
private:
  itemType key;
  int distance;
  short color; // 0 blanco, 1 gris, 2 Negro
  GraphNode* pi;//padre
  GraphNode* adjList;//lista de nodos adyacentes

public:
  GraphNode(int);
  GraphNode* getAdjList(void);
  itemType getKey();
  void setPi(GraphNode*);
  void setAdjList(GraphNode*);

};
GraphNode::GraphNode(int key)
{
  this->key = key;
  distance = -1;//infinito
  color = 0;//white
  pi = NULL;
  adjList = NULL;
}

GraphNode* GraphNode::getAdjList()
{
  return adjList;
}

itemType GraphNode::getKey()
{
  return key;
}

void GraphNode::setPi(GraphNode* pi)
{
  this->pi = pi;
}
void GraphNode::setAdjList(GraphNode* list)
{
  adjList = list;
}

//----------------------------------------------------------

class Graph
{
private:
  GraphNode** graph;//apuntador a arreglo de apuntadores
  int size;//cardinalidad de los nodos
public:
  Graph(int);//numero de nodos del grafo
  void setAdjacency();//se escribe la lista de adyacencias
  void addNodeToAdjList(int,int);
  void printGraph();
};

Graph::Graph(int N)
{
  size = N;
  graph = (GraphNode**) calloc (N,sizeof(GraphNode*));//se crea el arreglo de apuntadores
  if(graph == NULL)
    cout << "ERROR: No se crearon los nodos\n";
  else
  {
    for(int i = 0; i < N; i++)
    {
      graph[i] = new GraphNode(i+1);
    }
  }
}
void Graph::setAdjacency()
{
  int input,i;
  cout << "Ingresa los nodos que tienen enlace con los siguentes:\n";
  cout << "Para saltar al siguente nodo, ingresa -1\n";
  for(i = 0; i < size; i++)
  {
    input = 0;
    while(input > -1)
    {
      cout << "|" << i+1 << "|:";
      scanf("%d", &input);
      if(input > -1)
      {
        addNodeToAdjList(input, i);
      }
    }
  }
}

void Graph::addNodeToAdjList(int input, int sourceNode)//agrega un nodo a la lista de adyacencia de otro nodo
{
  GraphNode* newNode = new GraphNode(input);
  newNode->setPi(graph[sourceNode]);
  newNode->setAdjList(graph[sourceNode]->getAdjList());
  graph[sourceNode]->setAdjList(newNode);//se agrega parecido a stack, para evitar loops
}

void Graph::printGraph()
{
  GraphNode** aux = graph;
  for(int i = 0; i < size;i++)
  {
    cout << "|" << graph[i]->getKey() <<"|";
    while(aux[i]->getAdjList() != NULL)
    {
      aux[i] = aux[i]->getAdjList();
      cout << aux[i]->getKey() << " -> ";

    }
    cout << "\n";
  }
}

//-----------------------------------------------

class BfsTree
{
private:
  GraphNode* root;

public:
  BfsTree(Graph,GraphNode);
  void printBFS(BfsTree);
};
BfsTree::BfsTree(Graph* graph, GraphNode* s)
{
  root = s;
}


//-------------------------------------------------
int main()
{
  Graph* graph = new Graph(5);
  graph->setAdjacency();
  cout << "\n\n";
  graph->printGraph();
  return 0;
}
//Matriz2List




//List2Matriz

//bfs pending