Как я могу представить ребра для графа в виде списка?

Question

Как мы можем представить график в виде списка ребер?

Answer 1

Есть три распространенных способа сделать это:

1. Матрица смежности: таблица весов ребер V * V, где i-й столбец в j-й строке - это вес ребра между вершинами i и j. Если ребро отсутствует, часто используется бесконечность (или вы можете использовать некоторое значение часового, например, -1).

2. Списки смежности: Массив V связанных списков. Каждый i-й список в массиве - это список ребер, выходящих из i-й вершины.

3. Список ребер: просто список кортежей (u, v) ребер.

Разные подходят для разных целей. Лично я считаю списки смежности наиболее полезными, но если у вас очень плотный граф, то матрица смежности может улучшить производительность и использование памяти.

Answer 2

Если вы хотите хранить ровно ребра, используйте матрицу весов: int** M;, где M[i][t] - длина ребра между вершинами i и t.

Если ребра графа имеют вес 1,Вы можете хранить граф в матрице смежности, где M[i][t] равно:

• 0 , если между вершинами i и t нет ребер
• 1 если есть ребро от i до t
• alpha если i == t и в вершине i (или t) есть петля

Если вам требуется структура, критичная для использования памяти, сохраните свой график в связанном списке, где каждая вершина имеет структуру:

struct Vertex
{
  int N;
  Vertex* next;
};

Таким образом, вы получите массив структур Vertex, каждая из которых содержит указатель на следующийсвязан с.Например, вот некоторый график связанных списков:

• 1 -> 3 -> 4
• 2 -> 5
• 3 -> 4
• 4 -> 3
• 5 -> 2

Answer 3

Если вы действительно не хотите реализовать представление самостоятельно, как учебное упражнение или иметь больший контроль, подумайте об использовании библиотеки, такой как igraph , которая является библиотекой C для представления и управления графами.Или спуститесь на один уровень абстракции вниз - создайте списки смежности или списки границ самостоятельно, но используйте возможности построения списков glib вместо того, чтобы свернуть свои собственные.