Линейная алгебра и мат. Статистика
Матрица инцидентности (инциденции)
жүктеу/скачать 294.26 Kb.
|
- Бұл бет үшін навигация:
- Поиск в глубину
| Матрица инцидентности (инциденции) графа — это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер. В ней указываются связи между инцидентными элементами графа (ребро(дуга) и вершина).
В неориентированном графе если вершина инцидентна ребру то соответствующий элемент равен 1, в противном случае элемент равен 0. В ориентированном графе если ребро выходит из вершины, то соответствующий элемент равен 1, если ребро входит в вершину, то соответствующий элемент равен -1, если ребро отсутствует, то элемент равен 0. Матрица инцидентности для своего представления требует нумерации рёбер, что не всегда удобно. Список рёбер В списке рёбер в каждой строке записываются две смежные вершины и вес соединяющего их ребра (для взвешенного графа). Количество строк в списке ребер всегда должно быть равно величине, получающейся в результате сложения ориентированных рёбер с удвоенным количеством неориентированных рёбер. Наиболее распространенные операции над графами: Обход графа (в глубину и в ширину) Поиск в ширину подразумевает поуровневое исследование графа: вначале посещается корень – произвольно выбранный узел, затем – все потомки данного узла, после этого посещаются потомки потомков и т.д. Вершины просматриваются в порядке возрастания их расстояния от корня. Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения требуемого условия. Каждая вершина может находиться в одном из 3 состояний: 0 – необнаруженная вершина 1 – обнаруженная, но ещё не посещённая вершина 2 – обработанная вершина Применения алгоритма поиска в ширину: Поиск кратчайшего пути в невзвешенном графе (ориентированном или неориентированном) Поиск компонент связности Нахождения решения какой-либо задачи (игры) с наименьшим числом ходов Найти все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин Найти все вершины, лежащие на каком-либо кратчайшем пути между заданной парой вершин. Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах. Для реализации алгоритма удобно использовать очередь. Поиск в глубину – это алгоритм обхода вершин графа. Поиск в ширину производится симметрично (вершины графа просматриваются по уровням). Поиск в глубину предполагает продвижение вглубь до тех пор, пока это возможно. Невозможность продвижения означает, что следующим шагом будет переход на последний, имеющий несколько вариантов движения (один из которых исследован полностью), ранее посещенный узел (вершина). Отсутствие последнего свидетельствует об одной из двух возможных ситуаций: Все вершины графа уже просмотрены Просмотрены вершины, доступные из вершины, взятой в качестве начальной, но не все (несвязные и ориентированные графы допускают последний вариант) Каждая вершина может находиться в одном из 3 состояний: 0 – необнаруженная вершина 1 – обнаруженная, но ещё не посещённая вершина 2 – обработанная вершина жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу:
|