БФТ/ТФП/топологические график реализации


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

Исходный код

#include <iostream>
using namespace std;

#include <list>
#include <queue>
#include <map>

Класс Edge

class Edge
{
public:
  int dest;
  int weight;

  Edge(int dest) : dest(dest), weight(0) {}
};

Класс Вершинного

class Vertex
{
public:
    int orig;
    std::list<Edge> adjList;
    bool visited;
    int indegree;

    Vertex() : orig(-1), visited(false), indegree(0) {}
    Vertex(int v) : orig(v), visited(false), indegree(0) {}

    friend bool operator==(const Vertex & v, int data);
    friend std::ostream & operator<<(std::ostream & os, const Vertex & v);
};

bool operator==(const Vertex & v, int data)
{
  if (v.orig == data) return true;
  return false;
}

std::ostream & operator<<(std::ostream & os, const Vertex & v)
{
  os << v.orig << ":";
  std::list<Edge>::const_iterator iter = v.adjList.begin();
  for(; iter != v.adjList.end(); ++iter)
    {
      os << " " << iter->dest;
    }

  return os;
}

Графа Класс

class Graph
{
private:
    typedef std::map<int, Vertex> VertexMap;
    typedef std::map<int, Vertex>::iterator VertexIterator;
    typedef std::map<int, Vertex>::const_iterator VertexConstIterator;
    bool visit(int v, std::list<int> & sortedList);

    VertexMap vertices;
public:
    void addVertex(int v);
    void addEdge(int v1, int v2);
    void print();
    void BreadthFirstTour(int v);
    void DepthFirstTour(int v);
    void TopologicalSort();
    void resetStates();
};

void Graph::addVertex(int v) 
{
  vertices.insert( std::make_pair(v, Vertex(v)) );
}

void Graph::addEdge(int v1, int v2)
{
    VertexIterator iter = vertices.find(v1);

    if (iter != vertices.end())
    {
        Edge edge(v2);
        iter->second.adjList.push_back(edge);
    }

    iter = vertices.find(v2);
    iter->second.indegree++;
}

void Graph::print()
{
    VertexConstIterator iter = vertices.begin();
    for (; iter != vertices.end(); ++iter)
    {
        cout << iter->second << "\n";
    }
}

void Graph::BreadthFirstTour(int v)
{
  cout << "BFS BEGIN\n";

  std::queue<int> q;
  VertexConstIterator iter = vertices.find(v);
  if (iter != vertices.end())
  {
      q.push(iter->first);
  }
  else
  {
      cout << "BFS END\n";
      return;
  }

  VertexIterator iter1;
  while (!q.empty())
  {
      int vtx = q.front();
      q.pop();

      Vertex & v = vertices[vtx];
      if (v.visited == false )
      {
          v.visited = true;
          cout << v.orig << " ";

          std::list<Edge>::const_iterator iter = v.adjList.begin();
          while (iter != v.adjList.end())
            {
                //cout << "dest " << iter->dest << endl;
                VertexConstIterator citer = vertices.find(iter->dest);
                if (citer != vertices.end())
                {
                    q.push(citer->first);
                    //cout << "pushing " << citer->orig << endl;
                }
                ++iter;
            }
      }
  }

  cout << "\nBFS END" << endl;

  resetStates();
}

void Graph::resetStates()
{
    VertexIterator iter = vertices.begin();
    for (; iter != vertices.end(); ++iter)
    {
        iter->second.visited = false;
    }
}

void Graph::DepthFirstTour(int v)
{
    VertexIterator iter = vertices.find(v);
    if (iter != vertices.end())
    {
        if (iter->second.visited == false)
        {
            iter->second.visited = true;

            std::list<Edge>::iterator liter = iter->second.adjList.begin();
            for (; liter != iter->second.adjList.end(); ++liter)
            {
                DepthFirstTour(liter->dest);
            }

            cout << iter->second.orig << " ";
        }
    }
}

void Graph::TopologicalSort()
{
    VertexConstIterator iter = vertices.begin();
    std::list<int> sortedList;
    bool cycle = false;
    for (; iter != vertices.end(); ++iter)
    {
        if (iter->second.indegree == 0) 
        {
            if (!visit(iter->first, sortedList))
            {
                cycle = true;
                break;
            }
        }
    }

    if (cycle || sortedList.size() != vertices.size())
    {
        cout << "CYCLE";
        return;
    }

    std::list<int>::const_iterator liter = sortedList.begin();
    for (; liter != sortedList.end(); ++liter)
    {
        cout << *liter << " ";
    }
}

bool Graph::visit(int v, std::list<int> & sortedList)
{
    VertexIterator iter = vertices.find(v);
    if (iter != vertices.end())
    {
        if (iter->second.visited == false)
        {
            iter->second.visited = true;

            std::list<Edge>::const_iterator liter = iter->second.adjList.begin();
            for (; liter != iter->second.adjList.end(); ++liter)
            {
                if (!visit(liter->dest, sortedList))
                {
                    return false;
                }
            }
            sortedList.push_front(iter->first);
        }
        else
        {
            return false;
        }
    }
    return true;
}

главная()

int main()
{
    Graph g;

    g.addVertex(1);
    g.addVertex(2);
    g.addVertex(3);
    g.addVertex(4);
    g.addVertex(5);
    g.addVertex(6);
    g.addVertex(7);
    g.addVertex(8);

    g.addEdge(1,2);
    g.addEdge(1,3);
    g.addEdge(2,4);
    g.addEdge(2,5);
    g.addEdge(3,6);
    g.addEdge(3,7);
    //g.addEdge(5,8); //disjoint node 8

    //g.addEdge(6,3); //this is forming cycle

    g.print();

    g.BreadthFirstTour(1);

    cout << "DFS START\n";
    g.DepthFirstTour(1);
    g.resetStates();
    cout << "\nDFS END" << endl;

    cout << "TOPOLOGICAL SORT START\n";
    g.TopologicalSort();
    g.resetStates();
    cout << "\nTOPOLOGICAL SORT END\n";

    return 0;
}


1369
2
задан 3 сентября 2011 в 06:09 Источник Поделиться
Комментарии
1 ответ

Не ставьте с помощью пространства имен std
перед тем как включать в себя другие заголовочные файлы
Если вы должны делать это тогда, после того как все вошли. Но желательно не использовать его вообще.

#include <iostream>
using namespace std;

#include <list>
#include <queue>
#include <map>

Вы действительно хотите, чтобы все члены вершина стала публичной?

public:
int orig;
std::list<Edge> adjList;
bool visited;
int indegree;

Тест равенства верны:

if (v.orig == data) return true;
return false;

Но это легче читать, когда написано вот так:

return v.orig == data;

Если у вас есть оператор << это обычно хорошая идея, чтобы реализовать >> (в долгосрочной перспективе вы, вероятно, будет). Таким образом, при написании свой выходной поток вы хотите написать его таким образом, что делает чтение его обратно в легкие. Поэтому, когда вы класса содержит такие вещи, как векторы полезно префикса, число элементов (не маркер завершения). Также любой субэлементы должны быть напечатаны с собственными оператор потока << так что вы, вероятно, следует написать для края, а также.

Определение типа итераторы с точки зрения контейнера. Таким образом, если вы меняете контейнер, вам нужно всего лишь сделать одно изменение (не каскад изменений).

typedef std::map<int, Vertex> VertexMap;
typedef std::map<int, Vertex>::iterator VertexIterator;
typedef std::map<int, Vertex>::const_iterator VertexConstIterator;

может быть записано как:

typedef std::map<int, Vertex>     VertexMap;
typedef VertexMap::iterator VertexIterator;
typedef VertexMap::const_iterator VertexConstIterator;
// ^^^^^^^^^ Use the container type we just defined.

Здесь вы члены Общественной намерены преследовать вас.

    iter->second.adjList.push_back(edge);

Вы связываете ваши представления вершин всегда содержит список ребер в этой усадьбе. Вы действительно должны задать более абстрактный интерфейс класса, который позволит вам изменить внутренние представления, не влияя на выполнение графика.

При добавлении ребра в графе.
Вы убедитесь, что источник там. Но вы не убедитесь, что узел назначения был создан. Я ожидал бы это, чтобы быть более симметричными.

Является ничтожным resetStates метод '()' действительно член Общественной интерфейс?

В вашем BreadthFirstTour/DepthFirstTour обхода графа. Его не поиск в ширину/глубину первого тура (как это предполагает широту или глубину), а график чуть менее симметрична, чем (тем более, что ребра имеют вес и графа не может быть полностью подключен).

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

Вы можете де-пару, как график пересекается с осуществлением график с помощью шаблона Visitor. Это также соответствует открытости/закрытости, сделав свой класс открыт для расширения, но закрыты для изменения, позволяя механизм перемещения должен быть указан вне графика.

2
ответ дан 3 сентября 2011 в 06:09 Источник Поделиться