Смежность
Говорят, что вершина смежна с другой вершиной, если есть ребро, соединяющее их.
Путь
Последовательность ребер, которая позволяет вам перейти от вершины A к вершине B, называется путем.
Цикл
Группа вершин, связанных вместе в замкнутую цепь
Связный граф
Граф, в котором между любой парой вершин имеется один путь
Дерево
Связный граф, не содержащий цикла
Неориентированный граф
Граф, в котором рёбра не имеют направления. В таком неориентированном графе можно перемещаться вдоль ребра в любом из двух направлений;
Ориентированный граф
Граф, в котором есть ребро , не обязательно означает, что также имеется ребро . Ребра в таком графике представлены стрелками, чтобы показать направление ребра.
Способы представления графа:
Матрица смежности
Матрица смежности — это двумерный массив вершин. Каждая строка и столбец представляют вершину.
Если значение любого элемента равно 1, это означает, что существует ребро, соединяющее вершину i и вершину j.
Поиск ребер (проверка, существует ли ребро между вершиной A и вершиной B), чрезвычайно быстр в представлении матрицы смежности, но мы должны зарезервировать пространство для каждой возможной связи между всеми вершинами ( ), поэтому для этого требуется больше места.
Список смежности
Список смежности представляет собой граф в виде массива связанного списка.
Индекс массива представляет вершину, и каждый элемент в его связанном списке представляет другие вершины, которые образуют ребро с вершиной.
Список смежности эффективен с точки зрения хранения, потому что нам нужно хранить только значения для ребер. Для графа с миллионами вершин это может означать много сэкономленного пространства.
Матрица инцидентности (инциденции)
Достарыңызбен бөлісу: |
