Структура данных - структура данных графика
Граф - это графическое представление набора объектов, в котором некоторые пары объектов связаны ссылками. Взаимосвязанные объекты представлены точками, обозначенными какvertices, а связи, соединяющие вершины, называются edges.
Формально граф - это пара множеств (V, E), где V - множество вершин и E- множество ребер, соединяющих пары вершин. Взгляните на следующий график -
На приведенном выше графике
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Структура данных графика
Математические графики могут быть представлены в виде структуры данных. Мы можем представить граф, используя массив вершин и двумерный массив ребер. Прежде чем мы продолжим, давайте познакомимся с некоторыми важными терминами -
Vertex- Каждый узел графа представлен в виде вершины. В следующем примере отмеченный кружок представляет вершины. Таким образом, от A до G - вершины. Мы можем представить их с помощью массива, как показано на следующем изображении. Здесь A можно идентифицировать по индексу 0. B можно идентифицировать по индексу 1 и так далее.
Edge- Ребро представляет собой путь между двумя вершинами или линию между двумя вершинами. В следующем примере линии от A до B, от B до C и так далее представляют ребра. Мы можем использовать двумерный массив для представления массива, как показано на следующем изображении. Здесь AB может быть представлен как 1 в строке 0, столбце 1, BC как 1 в строке 1, столбце 2 и так далее, сохраняя другие комбинации как 0.
Adjacency- Два узла или вершины являются смежными, если они соединены друг с другом ребром. В следующем примере B находится рядом с A, C находится рядом с B и так далее.
Path- Путь представляет собой последовательность ребер между двумя вершинами. В следующем примере ABCD представляет путь от A до D.
Основные операции
Ниже приведены основные основные операции графа.
Add Vertex - Добавляет вершину к графу.
Add Edge - Добавляет ребро между двумя вершинами графа.
Display Vertex - Отображает вершину графа.
Чтобы узнать больше о Graph, прочтите Учебник по теории графов . Мы узнаем об обходе графа в следующих главах.