Witajcie, napisałem program- generalnie wyszukujący " sprawdzający" czy podany graf zawiera cykl.
Dla grafu skierowanego. W oparciu o materiały z geek'a
generalnie, nie moge znaleźć przyczyny dlaczego dla grafu nr g1. Zwraca cykl, mimo iż tego cyklu tam nie ma.
#include <iostream>
#include<list>
#include<string>
#include<vector>
using namespace std;
enum Color {BIALY, SZARY, CZARNY};
class DirectedGraph {
int vertex; // wierzcholek
list<int> *neighbourList; // lista wierzcholkow po koleji ( z racji grafu skierowanego )
//czasomierz
double time; // zmienna czasowa
double *d; // czas 1 odwiedzin
double *f; // czas 2 odwiedzin
public:
DirectedGraph(int numVertex); // construktor
void createEdge(int strV, int endV ); // tworzenie krawedzi
bool DFSsolve(int numVertex,int colorType[]);
bool startDFS();
};
// tworzymy graf
DirectedGraph::DirectedGraph(int numVertex) {
this->vertex=numVertex; // bo dla kazdego obiektu, instancji
// d= new double[numVertex]; // czas 1 odwiedzin
// f= new double [numVertex];
this-> neighbourList= new list<int>[numVertex];
}
// dodawanie krawedzi
void DirectedGraph::createEdge(int strV, int endV) {
this-> neighbourList[strV].push_back(endV); // back, zeby kazdy kolejny byl w odpowiedniej kolejnosci
}
bool DirectedGraph::startDFS() {
time=0;
int *colorType = new int[vertex];
for(int i=0;i<vertex;i++){
colorType[i]=BIALY;
}
for(int i=0;i<vertex;i++){
if(colorType[i]==BIALY)
if(DFSsolve(i,colorType)== true )
return true;
}
return false;
}
bool DirectedGraph::DFSsolve(int ver, int colorType[]){
colorType[ver]=SZARY;
// time+=1;
// d[ver]=time;
list<int>::iterator j;
for(j=neighbourList[ver].begin(); j!=neighbourList[ver].end();++j){
int inner=*j;
if (colorType[inner] == SZARY)
return true;
if(colorType[inner]==BIALY && DFSsolve(inner,colorType) ){
return true;
}
}
colorType[ver]==CZARNY;
// time=time+1;
// f[ver]=time;
return false;
}
int main (){
DirectedGraph g1(7);
g1.createEdge(0, 1);
g1.createEdge(2, 4);
g1.createEdge(1, 2);
g1.createEdge(2, 3);
g1.createEdge(4, 5);
g1.createEdge(6, 5);
g1.createEdge(3, 5);
g1.createEdge(6, 0);
g1.createEdge(1, 4);
DirectedGraph g(4);
g.createEdge(1, 2);
g.createEdge(2, 3);
g.createEdge(3, 4);
DirectedGraph g3(6);
g3.createEdge(0, 1);
g3.createEdge(2, 0);
g3.createEdge(2, 1);
g3.createEdge(3, 2);
g3.createEdge(4, 2);
g3.createEdge(4, 3);
g3.createEdge(3, 5);
g3.createEdge(5, 4);
if (g1.startDFS() )
cout << "Graph contains cycle \n";
else
cout << "Graph doesn't contain cycle\n";
if (g3.startDFS() )
cout << "Graph contains cycle \n";
else
cout << "Graph doesn't contain cycle\n";
if (g.startDFS() )
cout << "Graph contains cycle";
else
cout << "Graph doesn't contain cycle";
return 0;
}
Jakaś sugestia, nawet nie wiem jakby to debugować.
