c++ - 使用邻接表(使用和链接列表)的C++中的DFS实现

Question

我已经使用和链表制作了一个邻接表。在节点的结构中，我有下一个并已访问的数据。当我尝试在DFS函数中将visit访问设置为true时，该算法无法正常工作。仅当我创建一个存储 bool(boolean) 值的新数组并将该数组用于dfs算法时，它才起作用。我需要帮助让成员访问顶点结构才能工作。我不确定为什么它不起作用。

图

#ifndef GRAPH_H
#define GRAPH_H
#include <vector>

class Graph{
private:
    struct vertex{
        int data;
        bool visited;
        struct vertex* next;
    };

    struct adjList
    {
        struct vertex *head;
    };

    int V;
    bool visited[100];
    std::vector<adjList> G;
public:
    Graph(int vertices);
    vertex* addVertex(int data);
    void addEdge(int index, int data);
    void dfs(int vertex);
    void printGraph();
};

#endif

Graph.cpp

#include "Graph.h"
#include <iostream>
#include <cstdlib>
using namespace std;

Graph:: Graph(int vertices){
    this->V=vertices;
    for(int i=0; i<V; i++){
        //allocating space in G for V amount and using constructor of struct
        G.push_back(adjList());
        visited[i]=false;
    }
}
//create a node
Graph:: vertex* Graph::addVertex(int data){
    struct vertex* newNode= new vertex;
    newNode->data= data;
    newNode->next= NULL;
    newNode->visited=false;
    return newNode;
}
//add an Edge to the list
void Graph:: addEdge(int index, int data){
    struct vertex* cursor= G[index].head;
    while(cursor){
      if(cursor->data==data)
        return;
      cursor= cursor->next;
    }
    struct vertex* newVertex= addVertex(data);
    newVertex->next = G[index].head;
    G[index].head= newVertex;
    // this is undirected graph, so we are adding an edge from data to index;
    newVertex = addVertex(index);
    newVertex->next= G[data].head;
    G[data].head= newVertex;
}
// dfs algorithm
void Graph::dfs(int vertex){
    cout<<vertex<<", ";
    G[vertex].head->visited = true;
    visited[vertex]=true;
    struct vertex* cursor = G[vertex].head;
    while(cursor!=NULL){
      vertex=cursor->data;
      if(visited[vertex]==false)
          dfs(vertex);
      cursor= cursor->next;
    }
}

void Graph::printGraph(){
    for(int i=0; i<V; i++){
        struct vertex* cursor= G[i].head;
        cout<<"vertex: "<<i<<endl;
        while(cursor!=NULL){
            cout<<"->"<<cursor->data;
            cursor=cursor->next;
        }
        cout<<endl;
    }
}

int main(){
    Graph Graph(5);
    Graph.addEdge(0,1);
    Graph.addEdge(0,4);
    Graph.addEdge(1,2);
    Graph.addEdge(1,3);
    Graph.addEdge(1,4);
    Graph.addEdge(2,3);
    Graph.addEdge(3,4);

    Graph.printGraph();
    Graph.dfs(0);
    return 0;
}

Answer 1

首先清理数据结构，您过早弯曲它们以支持算法，这反而会引起困惑。确保首先有一个可靠的“模型”，不考虑任何算法，然后检查算法的需求，然后将其添加为算法内部的本地临时文件，或将某些缓存/扩展数据添加到模型中。但要保留核心模型。

我的意思是，让我向您展示DFS的效率低下但简单的实现，希望可以将其视为“现代C++”(但我也不是专家):

现场演示位于:http://cpp.sh/9fyw

#include <iostream>
#include <vector>
#include <string>

/**
 * Super naive and inefficient (but simple) implementation of Depth-first-search of graph
 * Just to show basic usage of std::vector, and how it helps to avoid new/delete
 **/

struct Vertex {
    // nothing at the moment
};

struct Edge {   // One-way edge, to make things intentionally harder
    size_t fromIndex, toIndex;

    Edge(const size_t _fromIndex, const size_t _toIndex)
        : fromIndex(_fromIndex), toIndex(_toIndex) {}
};

class Graph {
    std::vector<Vertex> vertices;
    std::vector<Edge> edges;

public:
    Graph(const size_t expectedVerticesCount = 20, const size_t expectedEdgesCount = 50) {
        if (expectedVerticesCount) vertices.reserve(expectedVerticesCount);
        if (expectedEdgesCount) edges.reserve(expectedEdgesCount);
    }

    void clear() {
        vertices.clear();
        edges.clear();
    }

    void initVertices(const size_t newVertexCount) {
        // A bit pointless function to set vertices, as vertices have no data
        // Storing the count itself inside Graph would suffice,
        // but let's demonstrate vector usage a bit more with N empty vertices
        clear();    // removes old vertices + edges
        vertices.resize(newVertexCount);
    }

    void addEdgeBiDirectional(const size_t v1Index, const size_t v2Index) {
        if (vertices.size() <= v1Index || vertices.size() <= v1Index) {
            std::cout << "Ups, unexpected vertex in edge: "
                << v1Index << " <-> " << v2Index << "\n";
            return;
        }
        if (v1Index == v2Index) {
            std::cout << "Ups, loop at vertex: " << v1Index << " - ignored\n";
            return;
        }
        // Add two one-way edges, to make this edge work in both directions
        edges.push_back(Edge(v1Index, v2Index));
        edges.push_back(Edge(v2Index, v1Index));
    }

    void printGraph() {
        for (size_t i = 0; i < vertices.size(); ++i) {
            std::cout << "Vertex " << i << " has edges to:";
            for (const auto & edge : edges) {
                if (edge.fromIndex == i) std::cout << " " << edge.toIndex;
            }
            std::cout << "\n";
        }
    }

private:
    void dfs(std::vector<size_t> & result, std::vector<bool> & visited, size_t v) {
        // It's important to pass vectors as references here (that "&")
        // so you don't fill stack space too quickly, and the modifications
        // done to them inside are propagated up into final result.
        // Without "&" a local copy of vector would be created.
        if (visited[v]) return;
        result.push_back(v);
        visited[v] = true;
        for (const auto edge : edges) {
            if (edge.fromIndex != v) continue;
            dfs(result, visited, edge.toIndex);
        }
    }

public:
    // Returns vector with vertex indices found
    std::vector<size_t> dfs(const size_t vertexIndex) {
        if (vertices.size() <= vertexIndex) {
            std::cout << "DSF: Ups, invalid starting vertex: "
                << vertexIndex << "\n";
            return std::vector<size_t>();
        }

        std::vector<bool> visited(vertices.size());
        std::vector<size_t> result;
        result.reserve(vertices.size());
        dfs(result, visited, vertexIndex);
        return result;
    }
};

int main()
{
    Graph g;
    // fill up graph data
    g.initVertices(5);
    g.addEdgeBiDirectional(0,1);
    g.addEdgeBiDirectional(0,4);
    g.addEdgeBiDirectional(1,2);
    g.addEdgeBiDirectional(1,3);
    g.addEdgeBiDirectional(1,4);
    g.addEdgeBiDirectional(2,3);
    g.addEdgeBiDirectional(3,4);
    // Show the validation works
    g.addEdgeBiDirectional(1,1);
    g.addEdgeBiDirectional(5,4);

    g.printGraph();

    auto dfsResult = g.dfs(2);
    std::cout << "DFS for 2 result:";
    for (const auto v : dfsResult) std::cout << " " << v;
    std::cout << "\n";
}

(现在我意识到，我的“addEdge”并不能防止像您一样添加重复的边缘，将其视为错误或功能)

如果选中它，您会发现性能很差，因为它每次都在搜索所有边缘。如何帮助呢？已经为每个顶点准备了邻居数据。

struct Vertex {
    std::vector<size_t> adjacency;
};

然后在 Graph中，可以为每个添加的边设置相邻的顶点:

void addAdjacency(const size_t v1Index, const size_t v2Index) {
    auto & adjacency = vertices[v1Index].adjacency;
    if (adjacency.end() != std::find(adjacency.begin(), adjacency.end(), v2Index)) return;
    adjacency.push_back(v2Index);
}

void addEdgeBiDirectional(const size_t v1Index, const size_t v2Index) {
    ...
    addAdjacency(v1Index, v2Index);
    addAdjacency(v2Index, v1Index);
}

现场演示: http://cpp.sh/4saoq

现在，它的效率要高得多(就深度优先而言是有效的，广度优先搜索在不使用大量堆栈空间进行递归的情况下将更容易编写)。

但是，如果DFS和printGraph是您的唯一目标，则可以通过完全删除 edges并仅保留 vertices并在其中保留 adjacency来重构此目标。您可以自己尝试一下，您将看到它只需进行一些更改。

但是 visited字段保留为 dfs临时拥有，IMO是最适合使用它的方式。

这已经很久了，花了很长时间，以至于我没有心情向您展示使用指针new和delete的东西。至少在您可以自己生成相似或更好的代码之前，向您展示如何避免它们仍然可能会带来更多好处。

学习裸露的指针/新内容/删除内容也很重要，但是...查看一些教程吗？

至少有一个提示“何时使用 delete”:在现代C++中，您可以在 范围中进行思考。就像所有东西都属于某个地方(在某个范围内)一样，然后在退出该范围时被释放。通过这种方式思考，您只需在类中实现构造函数+析构函数，即可完成清理工作。

就像我的示例中的 Graph g;是 main的局部变量一样，因此在范围内。退出 main时，会调用 g的析构函数(我没有写过，因为默认的析构函数是由编译器创建的，以调用 vertices和 edges析构函数，并且 Vertex析构函数由 vector析构函数调用，隐式调用 adjacency所以所有东西都被释放了，没有内存泄漏。

如果要在整个生命周期的 new中使用某些 Graph(在构造函数或某些函数中)，要么将指针放在某个Graph成员变量中，然后编写显式析构函数，检查是否为非nullptr值，然后将其删除，或在某些功能中尽快将其删除(并将存储设置为nullptr以避免对同一指针进行两次删除)。

因此，如果您确定类的设计是合理的，并且所有内容都属于某个合理的范围，则可以使用由构造函数/析构函数配对的 new/delete，并且您知道清除是在退出该范围时发生的，该范围确实拥有(负责)为了那一块。

还有其他技术，如何将指针(或实际上任何资源)从原始所有者传递到其他类……通常，我会尽力避免这种情况，但是如果您真的坚持这种应用程序结构，则可以使用围绕 std::unique_ptr。但是，这种设计很难保持整洁，难以追踪特定内存或资源的责任/所有权。例如，观看 this video，以了解一些如何以某种优雅的方式处理它的想法。

还有关于 new和指针以及链接列表的最后说明。您可能从Java到链表和哈希图之类的东西都被使用，在VM下这很有意义，因为您几乎无法控制内存管理，并且实例通常被对象元数据“压倒”。

在C++中，情况有所不同，通常开销几乎为零，因此 std::vector<uint32_t> millionIntegers(1e6);是一个连续的内存块，长度为400万字节，此外还有几个字节的 vector 元数据。

这意味着，我的第一个O(n * n)示例几乎每次都遍历所有边缘，可以用于具有100 + k个边缘的图形，在性能上非常接近您的O(n)指针，因为每个 new可能会结束在内存的不同部分，破坏了处理数据的局部性。当您尝试访问缓存的内存页面之外的内存时，这会带来巨大的性能损失。尽管CPU可以半睡不休，连续地处理10万个整数，但是却最大程度地提高了缓存吞吐量(不幸的是，深度优先也将其弄乱了)。

这就是为什么通常在编写第一个版本时不应该为容器类型所困扰。如果 vector适合，请使用它。然后，在使用经过测试的代码之后，可以对其进行概要分析，并尝试一些更智能的内存结构，最终甚至将 vector替换为某种链表。但是您不能仅依靠算法理论或“逻辑”。

当涉及到x86性能时，从真实的生产代码到真实的生产数据来配置硬数据是至关重要的，现代硬件可以在很多方面使人为逻辑惊奇，并以意想不到的方式挑战理论。为了获得最佳性能，您既需要合理的复杂(简单)算法，又需要具有可预测的常规访问模式的整齐排列的数据。仅拥有两者之一可能是不够的。