Графична структура на данните и Algorithms (Пример)

по: Сара Чен Сара Чен
Hours Обновено

Какво е графика в структурата на данните?

Графът е нелинейна структура от данни, която се състои от върхове и ръбове, където върховете съдържат информация или данни, а ръбовете работят като връзка между двойка върхове.

Използва се за решаване на реални текстови проблеми като намиране на най-добрия маршрут до местоназначението и маршрут за телекомуникации и социални мрежи. Потребителите се считат за възел в графиката, а проводниците са ръбовете, свързващи потребителите.

Ако ръбовете са представени като E и върховете са представени като V, тогава графът G може да бъде написан като набор от върхове и ръбове, като например G (V, E)

Пример за графика в структурата на данните

Ето прост пример за структура на данни от графика:

Пример за графика в структурата на данните

Това е проста неориентирана графика (един вид графика). Тук наборът от върхове е: {A, B, C, D, E, F}. Два върха създават ръб. Например A и B са свързани с ръб. Въпреки това A и F не са свързани с никакви ръбове.

Графични терминологии в структурата на данните

Следват някои важни термини, използвани в структурата на данните на графиката:

термин Descriptйон
Връх Всички елементи от данни се наричат ​​връх или възел. В горното изображение A, B, C, D & E са върховете.
Ръб (дъга) Свързващите връзки между два възела или върха се наричат ​​ръб (дъга). Той има два края и се представя като (startingVertex, endingVertex).
Ненасочен край Това е двупосочен ръб.
Directed Edge Това е еднопосочен ръб.
Weighted Edge Ръб със стойност върху него.
Степен В Graph броят на ръбовете, свързани с връх, се нарича степен.
Indegree Общият брой входящи ръбове, свързани с връх.
Извънстепенна Общият брой изходящи ръбове, свързани с връх.
Самостоятелен цикъл Едно ребро се нарича самопримка, ако двете му крайни точки съвпадат.
Съседство Казват, че върховете са съседни, ако ребро е свързано.

Типове графики в структурата на данните

Ето списъка с най-често срещаните типове графики в структурата на данните:

  • Насочена графика
  • Неориентирана графика
  • Претеглена графика
  • Двупосочна графика
  • Безкрайна графика
  • Нулева графика
  • Тривиална графика
  • Мулти графика
  • Пълна графика
  • Свързана графика
  • Циклична графика
  • Насочена ациклична графика (DAG)
  • Графика на цикъла
  • Двустранна графика
  • Графика на Ойлер
  • Графика на Хамилтън

Приложения на графична структура на данни

Една графика има много случаи на употреба. Има много алгоритми, които често използват Graphs. Ето някои от приложенията на Graph:

  • Google Maps използва графики, за да намери пресечната точка на два пътя и да изчисли разстоянието между две местоположения.
    Например, Дейкстра, за намиране на най-краткото разстояние между местоположението на източника и местоназначението.
  • Facebook използва Graphs, за да намери общия приятел на потребителите. Алгоритъмът му разглежда всеки потребител като възел на графика.
  • За разпределяне на ресурси се използва DAG (Direct Acyclic Graph). Той проверява зависимостта на ресурсите.
  • Търсачката на Google използва графики, за да създаде класиране на уебсайтове.
  • Устройството за картографиране използва структурата на данните на графиката.
  • рутер и протоколът на t използва Graph, за да научи пътя на пътя на местоназначението.