История изменений
Исправление den73, (текущая версия) :
В общем, если брать дуболомный способ, то это называется «орграф», где стрелки указывают отношение «следующий». Если записать это в виде матрицы, где по столбцам и строкам идут вершины, а в ячейках - единицы там, где есть стрелка, то это будет матрица смежности.
Её за время О(число_вершин^3) можно достроить до матрицы достижимости, которая как раз и даёт то, что я просил - это «алгоритм Флойда - Уоршелла», который придумал и опубликовал первым, как ни странно, Бернард Рой :)
Есть и другие алгоритмы вычисления матрицы достижимости (находим по википедии), которые в каких-то случаях работают быстрее.
Накопал в ходе поисков сайт e-maxx.ru с описанием алгоритмов
Но, как оказалось, мне нужно не совсем это... А целая куча всяких действий над графами. Тем не менее, вопрос решён. Ещё была полезной книжка Новиков «дискретная математика для программистов».
Исправление den73, :
В общем, если брать дуболомный способ, то это называется «орграф», где стрелки указывают отношение «следующий». Если записать это в виде матрицы, где по столбцам и строкам идут вершины, а в ячейках - единицы там, где есть стрелка, то это будет матрица смежности.
Её можно достроить до матрицы достижимости, которая как раз и даёт то, что я просил, за время О(число_вершин^3) - «алгоритм Флойда - Уоршелла», который придумал и опубликовал первым Бернард Рой :)
Есть и другие алгоритмы вычисления матрицы достижимости (находим по википедии), которые в каких-то случаях работают быстрее.
Накопал в ходе поисков сайт e-maxx.ru с описанием алгоритмов
Но, как оказалось, мне нужно не совсем это... А целая куча всяких действий над графами. Тем не менее, вопрос решён. Ещё была полезной книжка Новиков «дискретная математика для программистов».
Исправление den73, :
В общем, если брать дуболомный способ, то это называется «орграф», где стрелки указывают отношение «следующий». Если записать это в виде матрицы, где по столбцам и строкам идут вершины, а в ячейках - единицы там, где есть стрелка, то это будет матрица смежности.
Её можно достроить до матрицы достижимости, которая как раз и даёт то, что я просил, за время О(число_вершин^3) - «алгоритм Флойда - Уоршелла», который придумал и опубликовал первым Бернард Рой :)
Есть и другие алгоритмы вычисления матрицы достижимости (находим по википедии), которые в каких-то случаях работают быстрее.
Накопал в ходе поисков сайт e-maxx.ru с описанием алгоритмов
Но, как оказалось, мне нужно не совсем это... А целая куча всяких действий над графами. Тем не менее, вопрос решён. Ещё была полезной книжка Новиков «дискретная математика для программистов».
Исходная версия den73, :
В общем, если брать дуболомный способ, то это называется «орграф», где стрелки указывают отношение «следующий». Если записать это в виде матрицы, где по столбцам и строкам идут вершины, а в ячейках - единицы там, где есть стрелка, то это будет матрица смежности.
Её можно достроить до матрицы достижимости, которая как раз и даёт то, что я просил, за время О(число-ребёр^3) - «алгоритм Флойда - Уоршелла», который придумал и опубликовал первым Бернард Рой :)
Есть и другие алгоритмы вычисления матрицы достижимости (находим по википедии), которые в каких-то случаях работают быстрее.
Накопал в ходе поисков сайт e-maxx.ru с описанием алгоритмов
Но, как оказалось, мне нужно не совсем это... А целая куча всяких действий над графами. Тем не менее, вопрос решён. Ещё была полезной книжка Новиков «дискретная математика для программистов».