shpori (1) / shpori (1)

8. Графы. Структуры данных для представления графов

Граф – это пара (V,E), где V – это некоторое конечное множество, E – подмножество множества двухэлементных подмножеств множества V. V – вершины, E – ребра.

Способы представления.

Пусть n – число вершин графа, m – число ребер графа.

	Занимаемое место в памяти	Узнать, смежны ли две вершины u и v
матрица смежности	ⁿ²	¹
списки смежности	^2m	max(deg(u),deg(v))
список ребер	^m	^m

Содержание