hi im trying to make a program that will get a graph inputed from the the user and then checks if it has a cycle. i have written the program but for some reason i cant get it to check for the cycle it starts but somewhere it stops some help would be much appreciated :)
#include<iostream>
usingnamespace std;
int main()
{
int rows, columns, edges;
cout<<"Please enter the amount of vertices: ";
cin>>rows;
char** matrix; // makes this array into a pointer
matrix=newchar*[rows]; // to initialize the rows (1 dimensional array for now)
cout<<"please enter each vertex"<<endl;
columns=rows; // you cant have more edges than there are vertices so
// I made the matrix basicaly rows x rows size but named
//it columns to differentiate
//define the matrix
for(int i=0;i<rows;i++)//in order to go through the whole 2-d array need to account for every location
{
matrix[i]=newchar[columns]; //creating the 2-d part of the array or the columns
for(int j=0;j<columns;j++) // start at row 0, column 0 then goes to row 0, column 1.... etc.
{
cout<<"Enter the vertex "<<(i+1)<<": ";//enter a vertex(only one at a time) then follow below
cin>>matrix[i][j]; // inputs that vertex into the certain location (ex- when start first goes into row 0, column 0...etc.)
cout<<"how many edges: ";//each vertex can have 1 or more edges or 0
cin>>edges;
j++;// need to move down one row in order to put in the vertex corresponding edges
while(j<edges+1)// this loop is based on the amount of edges the user inputed and will repeat that many times
{
cout<<"what is edge "<<j<<": ";
cin>>matrix[i][j];
j++;//need to move down one row in order to put in the vertex corresponding edges
}
while(j<columns)//this loop is used to fill all other spots that are left in the matrix with 0's or empty spaces
{
matrix[i][j]=0;
j++;
}
cout<<"--------------------------------------------------------"<<endl;// seperate each set of vertices and their edges inputed. looks cleaner
}
}
// starting from here is to print out the matrix vetices are the first row and each column has vertex followed by edges
int i=0; //needed to initialize i and j since the for loop only initializes for the loop itself
int j=0;// this is out the loop
while(j<rows)//this loop is the same as the for loop above basically
{
cout<<matrix[i][j]<<" ";
i++;
while(i<rows)
{
cout<<matrix[i][j]<<" ";
i++;
}
j++;
i=0;// need to reset i in order to start from the very top
cout<<endl;
}
cout<<endl;
cout<<"**The first row is the vertices and under each vertex are the edges**";
cout<<"--------------------------------------------------------"<<endl;
// start of the cycle check
char check;// check is used to jump from vertex to next node and compare the next vertex with other nodes
char vertex;// the first vertex we start off with in position [0][0]
int exit=0;//use this in order to exit the while loop later in the program
cout<<"checking to see if cycle";
j=0;
for(i=0;i<columns;i++)//make the loop only go through the columns
{
vertex=matrix[i][j];
j++;
if(matrix[i][j]!='0')
{
check=matrix[i][j];
j=0;//reset for search
i=0;//reset for search
int count=1;// count is made in order to keep track how many jumps made from node to node (1 because first jump made)
while(exit<rows)
{
if(check==matrix[i][j])//this finds the edge node and goes down its edges
j++; //use this to go down from the vertex to its edges
else
i++;//use this to try the next vertex
if(vertex==matrix[i][j]&&count>1)
{
cout<<"this graph has a cycle!";
break;
}
if(vertex!=matrix[i][j]&&check!=matrix[i][j])// makes sure the next vertex choosen is different
{
check=matrix[i][j];//set that new vertex into check
j=0;//restart for search
i=0;//restart for search
count++;// another jump is made
}
exit++;
}
j=0;
}
else
j=0;
}
system("pause");
return 0;
}