Jose Ortiz - 4 months ago 95

C++ Question

I have seen many implementations of the adjacency list. Here, I try to implement it using c++. As you can tell from my c++ structure, I am a total newbie in c++. Here i am struggling trying to get my code running. My current problem is, it does not go through the whole graph. and I get a segmentation fault.

Result:

vertex: 0

1->

vertex: 1

2->3->

vertex: 2

vertex: 3

vertex: 4

Segmentation fault

I need some help getting this to run. I want to implement DFS algorithm. Any tips would be great!!!

Here is Header:

`#ifndef DFS_H`

#define DFS_H

class DFS{

private:

struct vertex{

int data;

bool visited;

struct vertex* next;

};

int V;

struct vertex* G[20];

public:

DFS(int vertices);

vertex* addVertex(int data);

void addEdge(int index, int data);

void dfs(int vertex);

void printGraph();

};

#endif

cpp file:

`#include "DFS.h"`

#include <iostream>

#include <cstdlib>

using namespace std;

DFS:: DFS(int vertices){

this->V=vertices;

for(int i=0; i<V; i++){

G[i]= NULL;

}

}

DFS::vertex* DFS::addVertex(int data){

struct vertex* newNode= new vertex;

newNode->data= data;

newNode->next= NULL;

newNode->visited=false;

return newNode;

}

void DFS:: addEdge(int index, int data){

struct vertex* cursor;

struct vertex* newVertex= addVertex(data);

if(G[index]==NULL)

G[index]=newVertex;

else{

cursor=G[index];

while(cursor->next!=NULL)

cursor=cursor->next;

cursor->next= newVertex;

}

}

void DFS::printGraph(){

for(int i=0; i<V; i++){

struct vertex* cursor= G[i];

cout<<"vertex: "<<i<<endl;

while(cursor->next!=NULL){

cout<<cursor->data<<"->";

cursor=cursor->next;

}

cout<<endl;

}

}

void DFS:: dfs(int vertex){

}

int main(){

DFS dfs(5);

dfs.addEdge(0,1);

dfs.addEdge(0,4);

dfs.addEdge(1,2);

dfs.addEdge(1,3);

dfs.addEdge(1,4);

dfs.addEdge(2,3);

dfs.addEdge(3,4);

dfs.printGraph();

return 0;

}

*

Thanks for your help Stackoverflow community!

Answer

The segfault comes from `printGraph`

which assumes all `V`

vertices are present, which is not true in your case. Notice there is no `dfs.addEdge(4, ...)`

initializing the 5th vertex.

In general that approach that the length must match the number of elements set later on is asking for trouble, I'd refactor this code using a `vector`

for storage.

Another problem is that `addEdge`

always instantiates a new `vertex`

which means after `dfs.addEdge(1,3)`

and `dfs.addEdge(2,3)`

vertices 1 and 2 will point to different instances of vertex 3.

Another thing: `addEdge(1,2)`

and `addEdge(1,3)`

will leave you with edges *1->2* and *2->3*. I assume the result should be edges *1->2* and *1->3*.

Not to mention that returning a bare `new`

ed pointer from `addVertex`

is asking for a memory leak; I'd suggest using an `auto_ptr`

(`unique_ptr`

if you're on C++11).

Another thing is you are reimplementing a forward-linked list when `std::forward_list`

is available.

These are just a few problems I spotted just by looking at your code. I'm sure there are more because, to be honest, it looks pretty bad (no offense, we all used to be beginners). I suggest what @Beta said: learning and practicing one thing at a time (build a vertex list, when you're comfortable with that figure out how to represent edges, then try to traverse it, build a simple algorithm, etc).