使用链表在 C++ 中实现邻接表

Question

我见过很多邻接表的实现。在这里，我尝试使用c++实现它。从我的 c++ 结构可以看出，我是 c++ 的新手。在这里，我正在努力获取我的代码运行ning。我目前的问题是，它没有遍历整个图表。我得到了一个分段错误。结果：

顶点：0

1->

顶点：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;   
}

*

感谢您对 Whosebug 社区的帮助！

Answer 1

段错误来自 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 返回裸指针 newed 指针会导致内存泄漏；我建议使用 auto_ptr（unique_ptr 如果你使用的是 C++11）。

另一件事是，当 std::forward_list 可用时，您正在重新实现一个前向链表。

这些只是我通过查看您的代码发现的一些问题。我敢肯定还有更多，因为老实说，它看起来很糟糕（没有冒犯，我们都曾经是初学者）。我建议 @Beta 所说的：一次学习和练习一件事（建立一个顶点列表，当你对它感到满意时弄清楚如何表示边，然后尝试遍历它，建立一个简单的算法等）。

使用链表在 C++ 中实现邻接表

Adjacency List implementation in c++`using Linked List

c++

algorithm

linked-list

adjacency-list