Как представить граф с фиктивными вершинами, используя список смежности? - PullRequest
Новая
       62

Как представить граф с фиктивными вершинами, используя список смежности?

0 голосов
/ 20 января 2019

Dummy vertex

Этот граф содержит фиктивные вершины. Как сохранить информацию о состоянии вершин, используя список смежности? Исходящие ребра должны быть сохранены для каждой вершины.

Я использовал простой список смежности. Но здесь, например, v14 имеет два разных набора исходящих ребер (один без исходящего ребра и другой с двумя исходящими). Какую структуру данных я должен использовать для представления таких фиктивных узлов.

1 Ответ

0 голосов
/ 20 января 2019

Поскольку у вас нет ограничений на реализацию, подойдет простой класс. Здесь мы храним (совместно используемые) указатели на детей в векторе. (Перегружено) addChild методы возвращают ссылку на добавленный дочерний элемент, поэтому проще связать вместе addChild s. Использовать перегрузку оператора приятно, но не обязательно, и вы можете удалить их, если хотите. Вот код: 

#include <utility>
#include <iostream>
#include <string>
#include <vector>
#include <memory>

using std::vector;
using std::string;
using std::size_t;
using std::shared_ptr;
using std::make_shared;
using std::ostream;
using std::cout;
using std::endl;

class Node {
public:
  using child_ptr_type = shared_ptr<Node>;
  using contaner_type = vector<child_ptr_type >;

  explicit Node(string lab = "Default", contaner_type ch = {})
  : label(std::move(lab))
  , children(std::move(ch))
  {}

  const string &getLabel() const
  { return label; }

  void setLabel(const string &label)
  { Node::label = label; }

  const contaner_type &getChildren() const
  { return children; }

  const Node& getChild(size_t indx) const
  { return *children[indx]; }

  Node& getChild(size_t indx)
  { return *children[indx]; }

  Node& addChild(const string& lab = "Default", const contaner_type & ch = {})
  {
    children.push_back(make_shared<Node>(lab, ch));
    return *children.back();
  }

  Node& addChild(const child_ptr_type &child)
  {
    children.push_back(child);
    return *children.back();
  }

  Node& addChild(const Node& node)
  {
    children.push_back(make_shared<Node>(node));
    return *children.back();
  }

  friend ostream& operator<<(ostream& os, const Node &node)
  {
    node.print(os);
    return os;
  }

  Node&operator[](size_t indx)
  {
    return getChild(indx);
  }

  const Node&operator[](size_t indx) const
  {
    return getChild(indx);
  }



private:
  string label;
  contaner_type children;
  void print(ostream& os, size_t level = 0) const
  {
    for (size_t i = 0; i != level; ++i) {
      os << "|----";
    }
    os << label << '\n';
    for (const auto& child : children) {
      child->print(os, level + 1);
    }
  }
};

int main()
{
  Node V1("V1");

  V1.addChild("V2").addChild("V5").addChild("V7").addChild("V10");
  V1[0].addChild("V6").addChild("V8").addChild("V10");

  V1[0][1][0].addChild("V11").addChild("V13");
  V1[0][1][0].addChild("V14");

  V1.addChild("V3").addChild("V12").addChild("V14").addChild("V6");
  V1[1][0][0].addChild("V10");

  V1.addChild("V4").addChild("V13").addChild("V8");

  cout << V1 << endl;
  return 0;
}

Дерево в main - ваш пример на картинке. Вот вывод: 

V1
|----V2
|----|----V5
|----|----|----V7
|----|----|----|----V10
|----|----V6
|----|----|----V8
|----|----|----|----V10
|----|----|----|----V11
|----|----|----|----|----V13
|----|----|----|----V14
|----V3
|----|----V12
|----|----|----V14
|----|----|----|----V6
|----|----|----|----V10
|----V4
|----|----V13
|----|----|----V8
...