Представление графика с использованием связанного списка и матрицы

Question

Я знаю, как реализовать график, используя связанный список или матрицу. Но я хочу знать, когда использовать Связанный список и когда использовать матрицу для представления графа?

Answer 1

V = количество вершин в графе

Точки в пользу Матрицы:
1. Вы можете получить доступ к ребру (узнать, существует ли ребро между двумя вершинами), учитывая его конечные вершины в постоянном времени, тогда как онозанимает время O (степень (вершина)) при использовании списка смежности.
2. Матрица хороша, если ваш граф плотный.В противном случае он тратит пространство впустую, потому что использует пространство O (V * V).

Точки в пользу списка смежности:
1. Вам нужно время O (V) для итерации, чтобы получить соседей вершины, тогда как это занимает O(градус (вершина)), если вы используете список смежности.
2. Список смежности не занимает много места.

Answer 2

Обычно, когда ваш график плотный .Рекомендуется использовать матрицу, поскольку игнорируется «потеря» неиспользуемой памяти и ненужных чтений.
Обычно вы также используете матрицу, когда хотите быстро узнать, существует ли ребро, или вы хотите предварительно сформировать операции матрицы на графике [например, Page Rank ] (*)

Связанный список обычно предпочтительнее, если вы собираетесь использовать все ребра для каждой вершины, когда читаете его [например: на BFS].

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

Answer 3

Между этими двумя реализациями есть два фундаментальных различия с точки зрения потребления памяти и сложности.

1. Матричное представление допускает произвольный доступ к элементам, константа время вставка и удаление элементов, но (в общем) это потребляет больше пространства.
2. Связанный список в другой руке более дружественный памяти , но доступ к элементу и соседям может занять линейное время .

Answer 4

Вы всегда используете матрицу.

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

Answer 5

Это зависит от вашей проблемы и потребностей. Используйте матрицу, когда вам нужна скорость и большой объем памяти (если ваша матрица велика), используйте связанный список, если вам нужно сэкономить место с небольшим замедлением сделки.