Поиск двусвязных компонент. Граф задается матрицей смежности - C#
Формулировка задачи:
Всем доброе время суток. У меня такое задание.
Поиск двусвязных компонент. Граф задается матрицей смежности.
Матрицу смежности написал, там ничего сложного. А вот как найти двух связные компоненты, вообще понять не могу. Толи по матрице нужно создавать дерево, или прям из матрицы можно? Вообщем вообще понять не могу что это и с чем его кушать. Объясните пж!Решение задачи: «Поиск двусвязных компонент. Граф задается матрицей смежности»
textual
Листинг программы
public string traversal(int curr, int prev) { number[curr] = curr; L[curr] = number[curr]; visited[curr] = 1; /* помечаем текущую вершину как пройденную */ for (int i = 1; i < visited.Length; i++) { if ((visited[i] == 0) && (graph[curr][i] == 1)) { myStack.Push(Convert.ToString(curr) + " " + Convert.ToString(i)); traversal(i, curr); //рекурсивно заходим if (L[i] < L[curr]) { L[curr] = L[i]; } //здесь какая то херня if (L[i] >= number[curr]) { //res += Convert.ToString(curr); //если вершина точка сочления string str = Convert.ToString(curr) + " " + Convert.ToString(i); while (true) { string strr = myStack.Pop(); res += strr + " "; if (strr == str) break; else res += ", "; } res += "; \n"; } } if ((visited[i] == 1) && (number[i] < number[curr]) && (i != prev)) { if ((L[curr] > number[i])) { if (graph[curr][i] == 1) { L[curr] = number[i]; myStack.Push(Convert.ToString(curr) + " " + Convert.ToString(i)); } } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д