Реализация Graph C++ (узлы символов)

Question

У меня есть два класса, один Graph.h и Vertex.h (Directed Graph)

#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'); 

I implementaion если набросал будет выглядеть как this

Мой вопрос заключается в том, как бы я выполнить DFS/BFS, чтобы увидеть, если есть существует между P- путь > Т.

Answer 1

Будет ли более широкий или глубокий, более эффективный, полностью зависеть от топологии вашего графика. В первом приближении найдется кратчайший маршрут к узлу (полезен в навигации, но не в pathExists), но не путайте это с поиском маршрута в кратчайшем количестве ходов.

В обоих случаях вы сохраняете запись о том, какие узлы были посещены, как правило, растровое изображение, если граф большой (std::vector<bool> обычно подходит).

И в обоих случаях вы сохраняете «список» того, какие вершины посещать дальше. Первоначально список содержит только начальную точку, но при посещении каждой вершины вы добавляете связанные вершины в список, если не были уже посещены.

В случае поиска по ширине список вершин работает как очередь, в которую новые вершины добавляются в хвост списка.

В случае поиска по глубине список вершин работает как стек, в который новые вершины добавляются в начало списка. Можно отказаться от явного списка и использовать стек вызовов через функцию рекурсии для неявного хранения списка.

Поиск завершен, когда вы находите целевую вершину или когда стек/очередь пуста (в этом случае нет маршрута).