Понятие и представление графов. Матрица смежности как один из самых распространенных способов хранения графа. Расчеты временной сложности хранения графа списком дуг. Обходы и поиск кратчайшего пути в графах, алгоритмы Дейкстры и Флойда-Уоршелла.
Аннотация к работе
Как правило, наибольшего успеха добивается тот, кто располагает лучшей информацией.Итак, граф - это множество точек (вершин, объектов) и соединяющих их путей (линий, дуг, ребер). В строгом определении графом называется такая пара множеств G=(V,E), где V (множество вершин графа) есть подмножество любого счетного множества, а E (множество ребер графа, или множество неупорядоченных и упорядоченных пар вершин) - подмножество V?V. Взвешенным называется такой граф, для каждого ребра (дуги) которого определена некоторая функция. Пусть в нашем графе, который представлен на рисунке, нам нужно пройти из вершины 5 в вершину 2, а вес дуг - стоимость прохода по данному ребру (или время прохода по нему). Составим матрицу смежности для нашего графа: Если нам дан неориентированный граф, то ребро можно заменить двумя дугами, т.е. если у нас есть ребро (1,3), то мы можем заменить его на дуги (1,3) и (3,1) - так мы сможем пройти в любом направлении в любое время.