Reputation: 311
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!
Upvotes: 0
Views: 1323
Reputation: 863
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).
Upvotes: 1