Реализация графа в C

Question

Я хочу знать, как лучше и быстрее реализовать структуру данных графа и связанные с ней алгоритмы.

1. Список смежности предлагается книгой.

Но я не могу понять для большого графа, когда хочу найти ребро между двумя вершинами v1 и v2

Мне придется пройти через массив, который будет O(n).

Правильно ли мое понимание или есть лучший подход для достижения этой цели.

Answer 1

Прежде всего, это не O (n).Сохраняйте списки отсортированными, и это будет O (logN).Список смежности не обязательно должен быть реализован связанным списком.Более обычно иметь массив.

Другой очень популярный подход - это матрица смежности n x n, где a [i] [j] равно 1 (или весу ребра), если i иJ связаны и 0 в противном случае.Этот подход оптимален для плотных графов, у которых много ребер.Для разреженных графов список смежности имеет тенденцию быть лучше

Answer 2

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

a) Глобальный список узлов и ребер.

b) Глобальный список узлов, список ребер для каждого узла.

c) Матрица смежности (A [i][j] = w (ребро, соединяющее Vi-Vj, если оно существует), 0 в противном случае)

d) Краевая матрица (A [i] [j] = 1, если Ei соединяет узел Vj)

Answer 3

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