#data-structures #graph #graph-theory #directed-graph #representation
#структуры данных #График #теория графов #ориентированный граф #представление
Вопрос:
Утром это был один из моих экзаменационных вопросов по структурам данных и алгоритмам.
Я должен нарисовать график на бумаге на основе приведенного ниже массива списков: 
Проблема, с которой я столкнулся, например:
0->1->4->3
Что именно это означает? Означает ли это, что 0 имеет 3 ребра к 1 и 4 и 3, или это просто набор ребер, например, 0 имеет ребро к 1, 1 имеет ребро к 4, 4 имеет ребро к 3 и так далее. Я был бы признателен за любую помощь в этом.
Ответ №1:
В основном то, о чем вы говорите, называется «Связанным представлением» в теории графов.
0->1->4->3 означает, что вершина 0 связана с 1 и 4 и 3 направленным образом (означает, что стрелка направлена от 0 к вершине 1, вершине 4 и вершине 3 соответственно).Это означает, что есть три направленных ребра, выходящих из вершины 0 в вершины 1,4 и 3 соответственно (ПОЖАЛУЙСТА, ИМЕЙТЕ В ВИДУ, ЧТО ЭТИ РЕБРА НАПРАВЛЕНЫ В СООТВЕТСТВИИ С ВАШИМ ВЫСКАЗЫВАНИЕМ)!
Аналогично, 1 просто подчеркивает, что нет направленного ребра из вершины 1 в любые другие вершины.
Аналогично, 2->1 означает, что существует ребро, направленное из вершины 2 в вершину 1.
И, 3->0->4 означает, что вершина 3 направляет ребра как к вершине 0, так и к вершине 4.
Наконец, 4->2->0 означает, что существует ребро, направленное из вершины 4 как в вершину 2, так и в вершину 0 каждая.