C ++: должен ли граф ADT иметь список вершин и список ребер или только вершины с указателями на другие вершины?
Я пытаюсь реализовать граф в C ++, я не уверен, есть ли «правильный» способ сделать это. должна ли каждая из моих вершин содержать список вершин, на которые она указывает, или объект графа должен содержать список вершин и список ребер.
Решение
Это зависит от того, с каким типом графика вы имеете дело,
Если ваш график является взвешенным, вы не можете просто иметь список указателей, потому что вы не сможете назначить вес для этого соединения.
В этом случае я бы предположил, что каждый узел будет содержать список ребер, которые связаны с ним. если граф не направлен, то для любых вершин i и j можно сохранить указатель на одно и то же ребро {i, j}, если он направлен, то ребро {i, j} и {j, i} — два разных объекта ,
Другой подход заключается в сохранении матрицы NxN, которая представляет соединения между всеми вершинами. если график не взвешен, то каждая ячейка [i, j] будет иметь 1, если существует ребро между вершиной i и вершиной j. если график взвешен, то ячейка [i, j] будет содержать расстояние от вершины i до вершины j и бесконечность или -1, если ребра не существуют.
Если ваш граф завершен (каждая вершина связана со всеми остальными вершинами), я настоятельно рекомендую использовать матричный метод, поскольку он очень прост в реализации, дает вам прямой доступ к любому значению и не требует дополнительной памяти или время выполнения (например, когда вы хотите перебрать все ребра, связанные с определенной вершиной), так как любая вершина в любом случае будет содержать список соединений со всеми остальными вершинами.
Другие решения
Это зависит от вашего доступа к данным графика. Вы можете определить двухмерный вектор следующим образом:
vector< vector<int> > nodes;
где идентификаторы узлов — от 0 до number_of_nodes -1;
Узел 6 будет храниться в узлах [6], и сын на.