Я только начал с теории графов. Я не могу понять, как кодировать список смежности, используя связанные списки. например, если у меня есть этот график (ненаправленный):
A--------B
| /|\
| / | \
| / | \
| / | \
| / | \
| / | \
| / | \
C E-------D
Как мне это кодировать? Я знаю, как сделать это, используя матрицу смежности, но как закодировать это, используя список смежности и связанные списки (c ++)?
Список смежности — это просто вектор / массив списков. Каждый элемент в графе является элементом в массиве, и любое ребро добавляется в список смежности. Таким образом это выглядит примерно так:
A -> {B, C}
B -> {A, C, D, E}
C -> {A, B}
D -> {B, E}
E -> {B, D}
Итак, мы начинаем с чего-то вроде std::vector<std::list<vertex>>
, Однако мы можем добиться большего, чем это, потому что вершины уникальны, поэтому мы можем использовать map
, Кроме того, вершина может появиться в списке ребер только один раз, поэтому мы изменим ее на std::map<vertex, std::set<vertex>>
,
Итак, для начала, что-то вроде:
struct vertex
{
//
};
class undirected_graph
{
private:
std::map<vertex, std::set<vertex>> graph_container;
public:
void add_vertex(const vertex& v) { //add a vertex to the map }
void add_edge(const vertex& v, const vertex& u) { //look up vertex in map and add to the vertex adjacency list }
//Other methods
//...
};
Список смежности будет просто набором объектов, представляющих ребра графа.
struct edge {
node *nodes[2];
edge( node *a, node *b ) {
if ( a < b ) { // define canonical order of edges for undirected graph
nodes[0] = a;
nodes[1] = b;
} else {
nodes[0] = b;
nodes[1] = a;
}
}
};
Связанный список не кажется особенно практичным; обычно вы определяете порядок ребер и помещаете их в std::set
или же std::map
,
bool operator< ( edge const &lhs, edge const &rhs ) {
if ( lhs.nodes[0] < rhs.nodes[0] ) return true;
if ( rhs.nodes[0] < lhs.nodes[0] ) return false;
return lhs.nodes[1] < rhs.nodes[1];
}
typedef std::set< edge > graph;
Есть много способов сделать это, трудно предложить что-то еще, не зная, что вы собираетесь делать с графиком.