-
Notifications
You must be signed in to change notification settings - Fork 0
/
Graph.h
44 lines (39 loc) · 1.53 KB
/
Graph.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#ifndef GRAPH_H
#define GRAPH_H
#include <set>
#include <vector>
//------------------------------------------------------------------------------
class Graph{
/* Cantidad de vertices. */
int V;
/* Vector de array donde se guarda el grafo. */
std::vector<int> *adj;
/* Container de nodos "con color" blanco. */
std::set<int> white;
/* Container de nodos "con color" gris. */
std::set<int> grey;
/* Container de nodos "con color" negro. */
std::set<int> black;
public:
/* Constructor */
explicit Graph(int V);
/* Destructor */
~Graph();
/* Recibe dos nodos y crea una arista del nodo v
hacia el nodo w. */
void addEdge(int v,int w);
/* Va recibiendo nodos para chequear si el grafo
contiene ciclos. Todos los nodos se inicializa en
el set blanco, cuando entra a la funcion isCyclic
se elimina del set blanco y se inserta en el set gris.
Para cada uno de los nodos adjacentes al que se esta procesando
se chequea: si esta en el set blanco se corre nuevamenta la
funcion isCyclic(), si esta en el set gris devuelve true porque
significa que encontro un ciclo. Cuando termina de procesar
el nodo lo borra del set gris y lo ubica en el set negro. */
bool isCyclic(int v);
/* Chequea si quedo algun nodo sin visitar. Si quedo un nodo
en el set blanco devuelve true, en otro caso devuelve false. */
bool unusedInstruction();
};
#endif