Graph C++的实现（节点是字符）

Question

我有两个类，一个是Graph.h和Vertex.h（有向图）

#ifndef VERTEX_H                              #ifndef GRAPH_H
#define VERTEX_H                              #define GRAPH_H


#include <iostream>                          #include "vertex.h"
#include <vector>                            using namespace std;

using namespace std;                         class Graph {

class Vertex {                               private:

private:                                     vector<Vertex> vertices;
vector<char> edges;                          
char label;

public:                                     public:

Vertex(char);                               void addEdge(char,char);
void addEdge(char);                         int vertexCount();
char getLabel();                            bool vertexExists( char );
const vector<char> getEdges();              bool pathExists( char, char );

};                                          };

#endif /* vertex_h */                       #endif /* graph_h */

我已经使用 bfs 解决了它，但我认为使用 dfs 会有更有效的解决方案。我插入了一些节点进行测试，

graph = new Graph();

graph->addEdge( 'P', 'R' );
graph->addEdge( 'P', 'W' );
graph->addEdge( 'Q', 'X' );
graph->addEdge( 'R', 'X' );
graph->addEdge( 'S', 'T' );
graph->addEdge( 'T', 'W' );
graph->addEdge( 'W', 'S' );
graph->addEdge( 'W', 'Y' );
graph->addEdge( 'Y', 'R' );
graph->addEdge( 'R', 'Z' );

我的实现如果草图看起来像 this

我的问题是如何执行 DFS/BFS 以查看 P->T 之间是否存在路径。

Answer 1

广度优先还是深度优先更有效将完全取决于你的图的拓扑结构。广度优先方法将找到到节点的最短路径（在导航中有用，但在 pathExists 中没有用），但不要将其与在最短移动次数中找到路径混淆。

在这两种情况下，您都会记录已访问的节点，如果图很大，通常是位图（std::vector<bool> 通常是合适的）。

并且，在这两种情况下，您都会维护 "list" 接下来要访问的顶点。最初列表仅包含起点，但当您访问每个顶点时，您将连接的顶点添加到列表中（如果尚未访问）。

在广度优先搜索的情况下，顶点列表作为队列运行，其中新顶点被添加到列表的尾部。

在深度优先搜索的情况下，顶点列表作为堆栈运行，其中新顶点被添加到列表的头部。可以省去显式列表，并通过函数递归使用调用堆栈来隐式保存列表。

当您找到目标顶点时，或者当stack/queue为空时（在这种情况下没有路线），搜索结束。

Graph C++的实现（节点是字符）

Implementation of Graph C++ (nodes are characters)

c++

stl

graph

breadth-first-search

depth-first-search