Мне нужно реализовать орграф (направленный граф) на С++ как часть домашнего задания, и у меня возникли некоторые проблемы с представлением типов данных вершин и ребер.
Может ли кто-нибудь указать мне пример или простой С++ класс, который реализует это, чтобы я мог изучить его и расширить оттуда?
Я немного погуглил, но нашел только результаты об использовании Boost или других библиотек, мне просто нужно что-то простое, что не зависит от какой-либо библиотеки.
Спасибо.
Существует два основных способа представления орграфов со структурами данных:
Ориентирован на узлы. Этот метод представляет каждый узел как объект в вашей программе, и каждый узел содержит информацию о других узлах, на которые он ссылается. Другие узлы могут быть такими же простыми, как список узлов, где существует направленное ребро между текущим узлом и целевым узлом.
Ориентирован на край. Этот метод представляет каждое ребро как объект в вашей программе, и каждое ребро содержит информацию о том, какие узлы оно соединяет. В орграфе каждое ребро будет иметь ровно один узел «источник» и «назначение» (который может быть одним и тем же узлом, если вы рассматриваете циклы). Этот метод по существу представляет собой список упорядоченных пар.
В зависимости от проблемы, которую вы решаете, одна из этих двух основных форм окажется наиболее подходящей. Для более конкретных алгоритмов может потребоваться добавить дополнительную информацию к вышеуказанным базовым структурам, например, список всех узлов, доступных из текущего узла.
Грубо говоря, есть 2 простых способа представления графиков:
У каждого есть свои преимущества/недостатки, в зависимости от приложения.
# 2 потребует много возни с указателем.
№ 1 часто проще использовать при преобразовании графов.
В любом случае у вас будет что-то вроде этого:
template<typename T>
class node
{
public:
T data;
};
А матрица и список классов списка будут указывать на динамически выделяемые node.
Подразумевается, что у вас будет класс graph и класс node.
Попробуйте 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;
}
Этот университетский документ может вам помочь.
Это не самое полное, но, возможно, дает вам представление. Я нашел это довольно полезным, это также для лекции, поэтому нет риска скопировать что-то, что не следует.
template<class T>
class node
{
public:
T data;
vector<node<T>*> edges;
}
Скорее всего, вы также захотите сохранить list<node<dataType>*> всех узлов.
