Поиск в глубину - C#
Формулировка задачи:
Есть граф, заданный матрицей смежности.
Нужно найти путь от указанной вершины до всех остальных.
Нашёл какую-то реализацию, но она просто помечает вершины постоянно увеличивающимся числом.
Т.е. можно только понять, в каком порядке эти вершины помечались.
Решение задачи: «Поиск в глубину»
textual
Листинг программы
public class dfs { Dictionary<int,bool> marks; Stack<int> path; //<-- это стек Graph source; //<-- это моя реализация графа, что там внутри - не важно public void FindPath(Graph gr, int start) //gr - граф, start - номер вершины, от которой нужно найти пути до остальных { marks = new Dictionary<int,bool>(); path = new Stack<int>(); source = gr; foreach (int i in gr.Keys) marks.Add(i, false); this.DFS(start); } //функция поиска public void DFS(int v) { marks[v] = true; path.Push(v); // сохраняем в стек текущую вершину foreach (int i in path) // выводим путь до текущей Console.Write(i.ToString()+" "); Console.WriteLine(); foreach (int i in source[v].NodeLinks) if (marks[i] == false) { DFS(i); path.Pop(); // не забываем извлекать уже проверенные вершины } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д