График::Делает поиск в ширину в графике.
Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.
Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразовывают Notebook MuPAD в Live скрипты MATLAB.
Graph::breadthFirstSearch(G, <StartVertex = v>)
Graph::breadthFirstSearch пересекает через график через поиск в ширину. Вывод показывает в первый раз идентификации и предшественник каждой вершины. Если вершина является одной вершиной без предшественника, ее предшественником является infinity.
Graph::breadthFirstSearch(G, StartVertex = v) пересекает через график через поиск в ширину, начинающий с вершины v. Вывод показывает в первый раз идентификации и предшественник каждой вершины. Если вершина является одной вершиной без предшественника, ее предшественником является infinity.
Типичное дерево создается и чертится для лучшего понимания алгоритма:
G := Graph([a, b, c, d, e, f, g, h, i, j, k, l],
[[a, b], [a, c], [b, d], [b, e], [c, f], [c, g],
[d, h], [e, i], [e, j], [f, k], [g, l]],
Directed):
plot(
Graph::plotGridGraph(G, VerticesPerLine = [12, 12, 12, 12],
VertexOrder = [
None, None, None, None, None, None,
a, None, None, None, None, None,
None, None, b, None, None, None,
None, None, None, c, None, None,
None, d, None, None, e, None,
None, f, None, None, g, None,
h, None, None, i, None, j,
None, None, k, None, None, l
]
)
)
Теперь мы вызываем breadthFirstSearch, чтобы узнать время начала и предшественников
Graph::breadthFirstSearch(G)
Вершина a обнаружена сначала, затем вершина b и так далее. Правильная таблица показывает предшественника каждой вершины. Отслеживание в обратном порядке от одной вершины поэтому действительно просто. a как первая вершина, обнаруженная в ее компоненте, не может быть отслежен в обратном порядке дальше. Расстояние каждой вершины в ее компоненте может быть считано в средней таблице. Корневые вершины всегда имеют значение 0 (они are корни).
Что происходит теперь, если там существуют вершина, которая не имеет никакой связи ни с какой другой вершиной. Верхний пример взят, и одна вершина добавлена, не изменяя ничто больше. Затем поиск в ширину вызывается на график:
G := Graph([a, b, c, d, e, f, g, h, i, j, k, l],
[[a, b], [a, c], [b, d], [b, e], [c, f], [c, g],
[d, h], [e, i], [e, j], [f, k], [g, l]],
Directed):G2 := Graph::addVertices(G, [m]): Graph::breadthFirstSearch(G2, StartVertex = [a])
Недавно вставленная вершина m не имеет никакого предшественника. Предшественник поэтому содержит значение infinity.
Если мы запускаем где-нибудь в графике, не зная корень DAG, результаты, конечно, отличаются:
G := Graph([a, b, c, d, e, f, g, h, i, j, k, l],
[[a, b], [a, c], [b, d], [b, e], [c, f], [c, g],
[d, h], [e, i], [e, j], [f, k], [g, l]],
Directed):Graph::breadthFirstSearch(G, StartVertex = [c])
Предшественником c является c, но если мы смотрим на график, это должен быть a. Это, тем не менее, не совсем правильно. Поиск в ширину берет данную вершину и использует это в качестве корня графика (не в вершинах!). Это объясняет также, почему следующий вызов показывает infinity предшественником к l.
| |
|
Перечислите содержащий одну вершину. |
|
Задает вершину, с которой можно запустить обход вершин в ширину. |
Перечислите содержащий три таблицы. Первая таблица содержит метку времени открытия. Второе расстояние до корневой вершины. Последняя таблица содержит вершины-предшественников.