Проверить достижимость в графе одной вершины из другой - C#

Узнай цену своей работы

Формулировка задачи:

Проверить достижимость в графе одной вершины из другой. Граф задан списком ребер. Примеры: в графе ((1 2)(2 3)(3 4)(1 5)) вершина 4 достижима из вершины 2, а 5 – нет.

Решение задачи: «Проверить достижимость в графе одной вершины из другой»

textual
Листинг программы
bool Find(int start, int finish, List<KeyValuePair<int, int>> ds, bool isDirect = false)
{
    if (finish == start)
    {
        return true;
    }
 
    var newDs = new List<KeyValuePair<int, int>>(ds);
 
    if (isDirect)
    {
        for (int i = newDs.Count - 1; i >= 0; i--)
            newDs.Add(new KeyValuePair<int, int>(newDs[i].Value, newDs[i].Key));
    }
 
    bool findResult = false;
 
    for (int i = 0; i < newDs.Count; i++)
    {
        if (start == newDs[i].Key)
        {
            var currKeyPair = newDs[i];
            var curr = newDs[i].Value;
            newDs.RemoveAt(i);
            findResult = Find(curr, finish, newDs);
            newDs.Insert(i, currKeyPair);
        }
 
        if (findResult)
            return true;
    }
    return false;
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

10   голосов , оценка 4 из 5
Похожие ответы