Реализация направленного графа

Question

Мне нужно реализовать диграф (Направленный граф) в c ++ как часть домашнего задания, и у меня возникли некоторые проблемы с представлением типов данных вершин и ребер.
Кто-нибудь может указать мне пример или простой класс C ++, который реализует это, чтобы я мог изучить его и расширить оттуда?

Я немного погуглил, но я нашел только результаты об использовании Boost или других библиотек, мне просто нужно что-то простое, не зависящее ни от какой библиотеки.

Спасибо.

Answer 1

Существует два основных способа представления орграфов со структурами данных:

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

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

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

Answer 2

В общем, есть 2 простых способа представления графиков:

1. Матрица соединений
2. Список списков.

Каждый имеет свои преимущества / недостатки,в зависимости от приложения.

# 2 потребует большого количества манипуляций с указателями.

# 1 часто проще использовать при выполнении преобразования графа.

В любом из них выу вас будет что-то вроде этого:

template<typename T>
class node
{
   public:
   T data;
};

И матрица, и список классов списков будут указывать на динамически распределяемые node.

Смысл в том, что вы будетеиметь класс graph и класс node.

Answer 3

Попробуйте vector< NodeType > с multimap< NodeType *, EdgeType>.

multimap не поддерживает подписку [ x ], поэтому вам нужно будет использовать edges.lower_bound().

В качестве альтернативы, map< pair< NodeType *, NodeType * >, EdgeType > может помочь найти ребро, заданное двумя узлами. Я использовал именно это в одной довольно тяжелой программе.

Вот пример для первого предложения:

struct NodeType {
    int distance;
    NodeType( int d ) { distance = d; }
};
struct EdgeType  {
    int weight;
    NodeType *link;
    EdgeType( int w, NodeType *l ) { weight = w; link = l }
};

vector< NodeType > nodes;
nodes.reserve( 3 );
nodes.push_back( NodeType( 0 ) );
nodes.push_back( NodeType( 0 ) );
nodes.push_back( NodeType( 0 ) );

multimap< NodeType *, EdgeType > edges;
edges.insert( make_pair( &nodes[0], EdgeType( 4, &nodes[2] ) ) );
edges.insert( make_pair( &nodes[0], EdgeType( 1, &nodes[1] ) ) );
edges.insert( make_pair( &nodes[2], EdgeType( 2, &nodes[0] ) ) );

for ( multimap< NodeType *, EdgeType >::iterator iter = edges.lower_bound( &nodes[1] ),
  end = edges.upper_bound( &nodes[1] ); iter != end; ++ iter ) {
    cerr << "1 connects to " << iter->second.link - nodes.begin() << endl;
}

Answer 4

template<class T>
class node
{
public:
    T data;
    vector<node<T>*> edges;
}

Скорее всего, вы также захотите сохранить list<node<dataType>*> всех узлов.

Answer 5

Эта университетская газета может вам помочь.

Это не самое полное, но, возможно, дает вам представление. Я нашел это довольно полезным, это также для лекции, так что нет риска скопировать то, что не следует.