0
У меня есть ориентированный граф. С (точно) одним началом и одним концом. Мне нужно найти те вершины, которые каждый Возможный путь от начала до конца.Найти все вершины, которые посещают каждый путь
Медленный подход будет проходить через все возможные пути и +1 каждую вершину, которую я посещаю. Все вершины, которые имеют одинаковые общие посещения, чем начало (или конец), - это вершины, которые я ищу.
Мне нужно знать это для оптимизации в компиляторе, который я пишу. Я хочу знать, где все пути потока управления сливаются.
Если кто-то может указать мне на правильное название такого алгоритма, это уже поможет. (Поскольку мои знания теории графов не очень хорошие)
Найти все узлы, которые доминируют над выходным узлом. Анализ доминирования - это хорошо известный и тривиальный алгоритм. https://en.wikipedia.org/wiki/Dominator_(graph_theory) –
Большое спасибо. Это имя, которое я искал! –