C++中使用邻接表的DFS实现（使用<vector>和链表）
DFS implementation in c++ using adjacency list (using <vector> and linked list)
我使用链表制作了一个邻接表。在节点的结构中，我有数据，下一个和访问过的。当我尝试在 DFS 函数中将 visited 设置为 true 时，该算法无法正常工作。它仅在我创建一个存储布尔值的新数组并将该数组用于 dfs 算法时才有效。我需要帮助让顶点结构的访问成员工作。我不确定为什么它不起作用。
Graph.h
#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;
}
首先清理你的数据结构，你过早地让它们偏向于你的算法，这适得其反，有点混乱。确保您首先有一些可靠的 "model"，没有考虑任何算法，然后检查算法需要什么，并将其作为本地临时内部算法添加，或者将一些 cached/extended 数据添加到模型中。但保留核心模型在其下。
我的意思是，让我向您展示 DFS 的超级低效但简单的实现，希望是可以考虑的东西 "modern 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
现在效率更高了（就深度优先效率而言，如果不使用大量堆栈进行递归，广度优先搜索会更容易编写）space。
但是如果 DFS 和 printGraph 是您的唯一目标，那么可以通过完全删除 edges 并仅保留 vertices 和其中的 adjacency 来重构。您可以自己尝试一下，您会发现只需稍作改动即可。
但 visited 字段仍由 dfs 临时拥有，IMO 最适合如何使用它。
这已经很长了，花了很长时间，我没有心情给你看一些有指针的东西，新的和删除的。向您展示如何避免它们可能还有更多好处，至少在您可以自己生成类似或更好的代码之前是这样。
学习裸体 pointer/new/delete 东西也很重要，但是...查看一些教程？
至少一个提示 "when to delete"：在现代 C++ 中，您可以在 范围 中思考。就像所有东西都属于某个地方（在某个范围内），然后在退出范围时被释放。通过这种方式思考，您只需在 类 中实现构造函数 + 析构函数，就可以完成清理工作。
就像我示例中的 Graph g; 是 main 的局部变量，因此在它的范围内。当 main 退出时，调用 g 的析构函数（我没有写，因为默认析构函数是由编译器创建的，用于调用 vertices 和 edges析构函数，并且 Vertex 析构函数被 vector 析构函数调用，后者隐式调用 adjacency 析构函数。所以一切都被释放，没有内存泄漏。
如果我要在 Graph 的生命周期中使用一些 new （在构造函数中，或者在某些函数中），要么我将指针放在一些 Graph 成员变量中，然后写显式析构函数检查非 nullptr 值，并删除它，或在某些函数中更快地删除它（并将存储设置为 nullptr 以避免在同一指针上重复删除）。
因此，如果您确保 类 的设计合理，并且所有内容都在某个合理的范围内，那么您可以使用 new/delete 与 constructor/destructor 配对，并且您知道干净-up 发生在退出范围时，该范围确实拥有（负责）该部分。
还有其他技术，如何将指针（或实际上的任何资源）从原始所有者传递给其他人 类 ... 通常我会非常努力地避免这种情况，但如果你真的坚持在这样的应用程序结构上，您可以使用 std::unique_ptr 周围的东西。但是这种设计有点难以保持清洁，并且难以追踪 responsibility/ownership 特定内存或资源。例如，观看 this video 了解如何以某种优雅的方式处理它的一些想法。
还有一些关于 new 以及指针和链表的最后说明。您可能从 Java 开始使用链表和哈希映射之类的东西，这在 VM 下很有意义，因为您几乎无法控制内存管理，并且实例通常 "crufted" 大量使用对象元数据。
在 C++ 中则不同，通常开销接近于零，因此 std::vector<uint32_t> millionIntegers(1e6); 是一个连续的内存块，长度为四百万字节，除此之外还有几个字节的向量元数据。
这意味着，我的第一个 O(n*n) 示例几乎每次都通过所有边，可以用于具有 100+k 边的图形，性能方面非常接近带有指针的 O(n)，如每个 new 都可能在内存的不同部分结束，从而破坏了处理数据的位置。当您尝试访问缓存内存页面之外的内存时，这会带来巨大的性能损失。虽然以连续的方式处理 100k 整数是 CPU 可以半睡半醒，最大化缓存吞吐量的事情（不幸的是，深度优先也把它搞砸了）。
这就是为什么通常在编写第一个版本时您不应该太在意容器类型的原因。如果 vector 适合，就使用它。然后在你有工作的、测试过的代码之后，你可以分析它，并尝试一些更智能的内存结构，最终甚至用某种链表替换 vector。但是你不能只依赖算法理论或"logic"。
当涉及到 x86 性能时，在实际生产数据上分析实际生产代码的硬数据至关重要，现代 HW 可以在许多方面给人类逻辑带来惊喜，并以意想不到的方式挑战理论。为了获得最佳性能，您需要相当复杂（简单）的算法，以及具有可预测的定期访问模式的整齐排列的数据。只有两者之一可能还不够。
我使用链表制作了一个邻接表。在节点的结构中，我有数据，下一个和访问过的。当我尝试在 DFS 函数中将 visited 设置为 true 时，该算法无法正常工作。它仅在我创建一个存储布尔值的新数组并将该数组用于 dfs 算法时才有效。我需要帮助让顶点结构的访问成员工作。我不确定为什么它不起作用。
Graph.h
#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;
}
首先清理你的数据结构，你过早地让它们偏向于你的算法，这适得其反，有点混乱。确保您首先有一些可靠的 "model"，没有考虑任何算法，然后检查算法需要什么，并将其作为本地临时内部算法添加，或者将一些 cached/extended 数据添加到模型中。但保留核心模型在其下。
我的意思是，让我向您展示 DFS 的超级低效但简单的实现，希望是可以考虑的东西 "modern 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
现在效率更高了（就深度优先效率而言，如果不使用大量堆栈进行递归，广度优先搜索会更容易编写）space。
但是如果 DFS 和 printGraph 是您的唯一目标，那么可以通过完全删除 edges 并仅保留 vertices 和其中的 adjacency 来重构。您可以自己尝试一下，您会发现只需稍作改动即可。
但 visited 字段仍由 dfs 临时拥有，IMO 最适合如何使用它。
这已经很长了，花了很长时间，我没有心情给你看一些有指针的东西，新的和删除的。向您展示如何避免它们可能还有更多好处，至少在您可以自己生成类似或更好的代码之前是这样。
学习裸体 pointer/new/delete 东西也很重要，但是...查看一些教程？
至少一个提示 "when to delete"：在现代 C++ 中，您可以在 范围 中思考。就像所有东西都属于某个地方（在某个范围内），然后在退出范围时被释放。通过这种方式思考，您只需在 类 中实现构造函数 + 析构函数，就可以完成清理工作。
就像我示例中的 Graph g; 是 main 的局部变量，因此在它的范围内。当 main 退出时，调用 g 的析构函数（我没有写，因为默认析构函数是由编译器创建的，用于调用 vertices 和 edges析构函数，并且 Vertex 析构函数被 vector 析构函数调用，后者隐式调用 adjacency 析构函数。所以一切都被释放，没有内存泄漏。
如果我要在 Graph 的生命周期中使用一些 new （在构造函数中，或者在某些函数中），要么我将指针放在一些 Graph 成员变量中，然后写显式析构函数检查非 nullptr 值，并删除它，或在某些函数中更快地删除它（并将存储设置为 nullptr 以避免在同一指针上重复删除）。
因此，如果您确保 类 的设计合理，并且所有内容都在某个合理的范围内，那么您可以使用 new/delete 与 constructor/destructor 配对，并且您知道干净-up 发生在退出范围时，该范围确实拥有（负责）该部分。
还有其他技术，如何将指针（或实际上的任何资源）从原始所有者传递给其他人 类 ... 通常我会非常努力地避免这种情况，但如果你真的坚持在这样的应用程序结构上，您可以使用 std::unique_ptr 周围的东西。但是这种设计有点难以保持清洁，并且难以追踪 responsibility/ownership 特定内存或资源。例如，观看 this video 了解如何以某种优雅的方式处理它的一些想法。
还有一些关于 new 以及指针和链表的最后说明。您可能从 Java 开始使用链表和哈希映射之类的东西，这在 VM 下很有意义，因为您几乎无法控制内存管理，并且实例通常 "crufted" 大量使用对象元数据。
在 C++ 中则不同，通常开销接近于零，因此 std::vector<uint32_t> millionIntegers(1e6); 是一个连续的内存块，长度为四百万字节，除此之外还有几个字节的向量元数据。
这意味着，我的第一个 O(n*n) 示例几乎每次都通过所有边，可以用于具有 100+k 边的图形，性能方面非常接近带有指针的 O(n)，如每个 new 都可能在内存的不同部分结束，从而破坏了处理数据的位置。当您尝试访问缓存内存页面之外的内存时，这会带来巨大的性能损失。虽然以连续的方式处理 100k 整数是 CPU 可以半睡半醒，最大化缓存吞吐量的事情（不幸的是，深度优先也把它搞砸了）。
这就是为什么通常在编写第一个版本时您不应该太在意容器类型的原因。如果 vector 适合，就使用它。然后在你有工作的、测试过的代码之后，你可以分析它，并尝试一些更智能的内存结构，最终甚至用某种链表替换 vector。但是你不能只依赖算法理论或"logic"。
当涉及到 x86 性能时，在实际生产数据上分析实际生产代码的硬数据至关重要，现代 HW 可以在许多方面给人类逻辑带来惊喜，并以意想不到的方式挑战理论。为了获得最佳性能，您需要相当复杂（简单）的算法，以及具有可预测的定期访问模式的整齐排列的数据。只有两者之一可能还不够。