Направленный сбой ациклического графа

Так что у меня проблемы с моим кодом, и я не могу точно понять, в чем проблема. Я должен взять в текстовом файле, где первая строка показывает количество вершин, а вторая строка показывает количество ребер. Из этого текстового файла, который я пытаюсь взять в показанные значения, затем построить график и определить, или нет, он содержит цикл. Затем отобразите узлы, у которых нет входящих ребер.
t1.txt

3
2
1,2,
2,3

Я не уверен точно, где я иду не так, как надо здесь.

t2.txt

5
5
3,4,
4,5,
2,3,
1,3,
3,5

//

#include <iostream>
#include <fstream>
#include <sstream>
#include<string>
#include<list>
#include <limits.h>
#include <stack>
#include<stdlib.h>
#include <cstdlib>using namespace std;class Graph
{
int V;    // No. of vertices
list<int> *adj;    // Pointer to an array containing adjacency lists
bool isCyclicUtil(int v, bool visited[], bool *rs);  // used by isCyclic()
public:
Graph(int V);   // Constructor
void addEdge(int v, int w);   // to add an edge to graph
bool isCyclic();    // returns true if there is a cycle in this graph
};

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.
}bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recStack[v] = true;

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
return true;
else if (recStack[*i])
return true;
}

}
recStack[v] = false;  // remove the vertex from recursion stack
return false;
}

// Returns true if the graph contains a cycle, else false.
bool Graph::isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
visited[i] = false;
recStack[i] = false;
}

// Call the recursive helper function to detect cycle in different
// DFS trees
for(int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, recStack))
return true;

return false;
}

int main()
{
float n ,n2;

string filename,line;
cout << "Enter filename: ";
cin >> filename;
fstream file;
file.open(filename.c_str());
file >> n;
file >> n2;
int num = n;
cout << num << " ";
int num2 = n2;
cout << num2 << " ";
string matrix[num2][2];
//int ** mat = new int*[num2];
int mat[num2][2];
Graph g(num);

while(!file.eof())
{
for(int i = 0; i < num2; i++)
{
//mat[i] = new int[num];
for(int j = 0; j < 2; j++)
{
if(getline(file,line,','))
{
matrix[i][j] = line; // read file into string matrix
istringstream(line) >> mat[i][j]; //convert to int and store in dynamic 2d array
}
}
}
}
cout << endl << "TEST " <<  mat[0][0] << " "  << mat[0][1] << " " << mat[1][0]<< " " << mat[1][1];
for(int i = 0; i <num2-1; i++)
{
int temp1,temp2;
temp1 = mat[i][0];
temp2 = mat[i][1];
g.addEdge(temp1,temp2);
}
if(g.isCyclic())//Here is where the program crashes for input t2.txt
cout << "Graph is not DAG";
else
cout << "Graph is DAG";

return 0;
}

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector