Реализация обхода графа в глубину (DFS) - C#
Формулировка задачи:
Всем здравствуйте! Задача такова реализация обхода не взвешенного дерева, который задан матрицей смежности и поиск высоты дерева.
Пыталась реализовать, но идет путаница в цикле. Помогите пожалуйста исправить код:
Это фрагмент класса с методами, лишнее убрала. Возможно вы сможете предложить более оптимальный код. Буду благодарна. Итог компиляции этого кода во вложении
class Graff { public int[,] tree; // Матрица смежности неориентированного дерева } public Graff() // Конструктор: задаем дерево матрицей смежности { int[,] tree = new int[a, b]; } public static void SearchDeep(ref int[,] tree) // Метод поиска в глубину и высота дерева { int height1 = 0; int height2 = 0; List<int> nodeDFS = new List<int>(); // создаем пустой список для перечисления вершин обхода в глубину nodeDFS.Add(0); // Добавляем корневую вершину, с которой начинается обход - вершина 0 int[,] assist = (int[,])tree.Clone(); // копируем матрицу смежности во вспомогательный массив int var = 0; int a, b; for (a = var; a < assist.GetLength(0); a++) // !!!здесь идет сбой цикла когда var=b { if (height2 < height1) { height2 = height1; height1 = 0; } for (b = a + 1; b < assist.GetLength(1); b++) { if (assist[a, b] == 1) { height1++; nodeDFS.Add(b); assist[a, b] = 0; var = b; break; } else if (a != 0) { var = 0; } } } Console.WriteLine("Выведем список вершин при обходе дерева в глубину:"); for (int i = 0; i < nodeDFS.Count; i++) { Console.WriteLine("\t" + nodeDFS[i]); } Console.WriteLine("Высота дерева:" + height2); } class Program { static void Main() { int[,] tree = new int[8, 8]{{0,1,1,1,0,0,0,0}, {0,0,0,0,1,0,0,0}, {1,0,0,0,0,0,0,0}, {1,0,0,0,0,1,1,0}, {1,0,0,0,0,0,0,0}, {0,0,0,1,0,0,0,1}, {0,0,0,1,0,0,0,0}, {0,0,0,0,0,1,0,0}}; SearchDeep(ref tree); } }
Решение задачи: «Реализация обхода графа в глубину (DFS)»
textual
Листинг программы
Stack<int> st = new Stack<int>(); // поиск в глубину bool DFS(int v) { if (ListVer[v].TyepVer == Vertex.TyepVerFoSoet.Black) return false; if (ListVer[v].TyepVer == Vertex.TyepVerFoSoet.Gray) return true; // при переходе на вершину красим ее в серый ListVer[v].TyepVer = Vertex.TyepVerFoSoet.Gray; for (int i = 0; i < ListVer.Count; i++) { if (AdjacencyMatrix[v, i]) { if (DFS(i)) return true; } } st.Push(v); ListVer[v].TyepVer = Vertex.TyepVerFoSoet.Black; return false; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д