我见过很多邻接表的实现。在这里,我尝试使用c++来实现它。从我的c++结构可以看出,我在c++方面完全是个新手。在这里,我正在努力让我的代码运行。我现在的问题是,它不能遍历整个图。就会出现分割错误。结果:
顶点:01 ->
顶点:1
2 -> 3 ->
顶点:2
顶点:3
顶点:4
段错误
我需要一些帮助让这个运行起来。我想实现DFS算法。任何建议都会很棒!!
标题:
#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文件:
#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;
}
* 感谢Stackoverflow社区的帮助!
区段故障来自printGraph
,它假设所有V
顶点都存在,这在您的情况下是不正确的。注意没有dfs.addEdge(4, ...)
初始化第5个顶点
一般来说,长度必须匹配稍后设置的元素数量的方法是自找麻烦,我将使用vector
来重构此代码用于存储。
另一个问题是addEdge
总是实例化一个新的vertex
,这意味着dfs.addEdge(1,3)
和dfs.addEdge(2,3)
之后,顶点1和2将指向顶点3的不同实例。
addEdge(1,2)
和addEdge(1,3)
将留给您边缘1->2和2->3。我假设结果应该是边1->2和1->3。更不用说从addVertex
返回一个裸new
ed指针是在请求内存泄漏;我建议使用auto_ptr
(unique_ptr
如果你是在c++ 11)。
另一件事是,当std::forward_list
可用时,你正在重新实现前向链表。
这些只是我通过查看您的代码发现的一些问题。我相信还有更多,因为老实说,它看起来很糟糕(无意冒犯,我们都曾经是初学者)。我建议@Beta说:一次学习和练习一件事(建立一个顶点列表,当你对如何表示边感到舒服时,然后尝试遍历它,建立一个简单的算法,等等)。