Реализация обхода графа в глубину (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;
        }

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


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

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

5   голосов , оценка 4.2 из 5