Поиск в ширину поиск с помощью списка смежности


Я хочу улучшить этот код с использованием STL. Дайте мне знать, если я должен добавить любой другой функции в этом коде.

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <limits>

class Graph
{
  int vertex_count;
  enum Color {WHITE, GRAY, BLACK};

  enum { INFINITY = std::numeric_limits<int>::max() };

  struct Vertex
  {
     int id;
     int distance;
     Color color;

     Vertex(int _id) : id(_id),
                       color(Color::WHITE),
                       distance(INFINITY)
                       {}
  };

public:

  std::vector<Vertex> vertices;
  std::vector< std::list<int> > adjList;

  Graph(int);
  void addEdge(int, int);
  void breadthFirstSearch(int);
};

Graph::Graph(int v)
{
   vertex_count = v;
   adjList.resize(vertex_count);
   for (int i = 0; i < vertex_count; i++)
   {
       vertices.push_back( Vertex(i) );
   }
}

void Graph::addEdge(int src, int dest)
{
  //undirected graph
   adjList[src].push_back(dest);
   adjList[dest].push_back(src);
}

void Graph::breadthFirstSearch(int s)
{
   vertices[s].color = GRAY;
   vertices[s].distance = 0;
   std::queue<Vertex> q;
   q.push(vertices[s]);
   while (!q.empty())
   {
      auto u = q.front();
      q.pop();
      for (auto v = adjList[u.id].begin(); v != adjList[u.id].end(); v++)
      {
         if (vertices[*v].color == WHITE)
         {
            vertices[*v].color = GRAY;
            vertices[*v].distance = u.distance + 1;
            q.push(vertices[*v]);
         }
      }
      u.color = BLACK;
      std::cout << vertices[u.id].id << " at level " << vertices[u.id].distance <<'\n';
   }
}

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


2189
4
задан 25 февраля 2018 в 02:02 Источник Поделиться
Комментарии
3 ответа

Будет исправлена в ближайшее время

Совет 1

В BfS, вы действительно не нужно цветов. (См. альтернативная реализация.)

Совет 2 (обнажая внутренности)

public:

std::vector<Vertex> vertices;
std::vector< std::list<int> > adjList;

Я предлагаю вам поставить два поля под private:.

Совет 3

Так как неориентированный граф является частным случаем ориентированного графа (в котором каждое ребро \$\{U, В\}\$ может быть смоделировано две направленные дуги \$(U, В), (В, У)\$), Я предлагаю вам реализовать это в виде ориентированного графа, но добавьте метод, который вставляет неориентированное ребро по две направленные дуги.

Совет 4

Я бы обдирать фактическое BFS из Graph. Однако это дело вкуса.

Совет 5

Graph::Graph(int v)
{
vertex_count = v;
adjList.resize(vertex_count);
for (int i = 0; i < vertex_count; i++)
{
vertices.push_back( Vertex(i) );
}
}

Почему не имя int v int vertex_count в первую очередь? Кроме того, я бы пошел, например, std::unordered_map<int, list<int>> поскольку она не ограничивается неотрицательных целых чисел.

Альтернативная реализация

Это не означает наилучшего выполнения, но он демонстрирует общую структуру я имел в виду:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iterator>

class Graph
{
public:
void addEdge(int node1, int node2);
void addArc(int tailNode, int headNode);
std::unordered_set<int>& getChildNodesOf(int node);

private:
std::unordered_map<int, std::unordered_set<int>> m_adjacency_list;
};

void Graph::addArc(int tail, int head)
{
m_adjacency_list[tail].insert(head);
}

void Graph::addEdge(int tail, int head)
{
// Simulate an undirected edge via two bidirectional arcs:
addArc(tail, head);
addArc(head, tail);
}

std::unordered_set<int>& Graph::getChildNodesOf(int node)
{
return m_adjacency_list[node];
}

std::unordered_map<int, int*>
computeUnweightedShortestPathTree(Graph& graph, int sourceNode)
{
std::unordered_map<int, int*> parentMap = { { sourceNode, nullptr }};
std::queue<int> open;
open.push(sourceNode);

while (!open.empty())
{
int currentNode = open.front();
open.pop();
int* parentNode = new int{currentNode};

for (int childNode : graph.getChildNodesOf(currentNode))
{
if (parentMap.find(childNode) == parentMap.end())
{
parentMap[childNode] = parentNode;
open.push(childNode);
}
}
}

return parentMap;
}

std::vector<int> tracebackPath(int targetNode,
std::unordered_map<int, int*>& shortestPathTree)
{
std::vector<int> path;
int currentNode = targetNode;
int* nextNode = shortestPathTree[currentNode];

while (true) {
path.push_back(currentNode);
nextNode = shortestPathTree[currentNode];

if (nextNode == nullptr)
{
break;
}

currentNode = *nextNode;
}

std::reverse(path.begin(), path.end());
return path;
}

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

for (int sourceNode : { 0, 1, 2, 3, 4 })
{
std::unordered_map<int, int*> shortestPathTree =
computeUnweightedShortestPathTree(graph, sourceNode);

for (int targetNode : { 0, 1, 2, 3, 4 })
{
std::cout << "Shortest path from " << sourceNode << " to " << targetNode << ": ";
std::vector<int> path = tracebackPath(targetNode, shortestPathTree);

std::copy(path.cbegin(),
path.cend(),
std::ostream_iterator<int>(std::cout, " "));

std::cout << "\n";

}
}
}

7
ответ дан 25 февраля 2018 в 04:02 Источник Поделиться

Одна маленькая вещь, которую я хотел бы упомянуть это в C++11 вводит синтаксис, известный как диапазон на основе цикла for, который позволяет перебрать контейнер, без необходимости иметь дело с итераторами. Таким образом, вы можете заменить:

 for (auto v = adjList[u.id].begin(); v != adjList[u.id].end(); v++)
{
if (vertices[*v].color == WHITE)
{
vertices[*v].color = GRAY;
vertices[*v].distance = u.distance + 1;
q.push(vertices[*v]);
}
}

с:

for (const auto& v : adjList[u.id])
{
if (vertices[v].color == WHITE)
{
vertices[v].color = GRAY;
vertices[v].distance = u.distance + 1;
q.push(vertices[v]);
}
}

Я лично считаю этот синтаксис легче читать, чем другие, поскольку он является более компактной по горизонтали, и разыменования оператор (*) полностью удаляется.

2
ответ дан 26 февраля 2018 в 12:02 Источник Поделиться

Что я всегда нахожу полезным при использовании перечислений является эта библиотека

0
ответ дан 1 марта 2018 в 09:03 Источник Поделиться