Поиск двусвязных компонент. Граф задается матрицей смежности

@robert19 · Регистрация: 26.03.2010

Author24 — интернет-сервис помощи студентам

Всем доброе время суток. У меня такое задание.
Поиск двусвязных компонент. Граф задается матрицей смежности.
Матрицу смежности написал, там ничего сложного. А вот как найти двух связные компоненты, вообще понять не могу. Толи по матрице нужно создавать дерево, или прям из матрицы можно? Вообщем вообще понять не могу что это и с чем его кушать. Объясните пж!

@robert19 · 20.03.2012, 16:44 **[ТС]**

Написал функцию нахождения двухсвязных компонентов, но не могу правильно их вывести на экран, помогите плиз:

C#

 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) && (graf[curr][i] == 1))
                {
                    if (curr != i)
                        frame[curr][i] = 1;
                    if (curr == 1) myStack.Push(Convert.ToString(curr)); //клал корень в стек
 
                    myStack.Push(", "+Convert.ToString(i));
 
                    traversal(i, curr); //рекурсивно заходим
 
                    if (L[i] < L[curr]) { L[curr] = L[i]; }
 
                    if (L[i] >= number[curr])
                    { 
                        res += Convert.ToString(curr) + myStack.Pop();
                    }
                    else if (!(L[i] >= number[curr])) //избавлялся от пробела и запятой
                    {
                        char[] zap = ",".ToCharArray();
                        char[] prob = " ".ToCharArray();
                        char[] str = myStack.Pop().ToCharArray();
                        //res += "; " + myStack.Pop() + ", ";
                        for (int j = 0; j < str.Length; j++)
                        {
                            if (str[j] != zap[0] && str[j] != prob[0]) { res += "; " + str[j] + ", "; }
                        }
                    }
                }
                if ((visited[i] == 1) && (number[i] < number[curr]) && (i != prev))
                {
                    if ((L[curr] > number[i]))
                    {
                        if (graf[curr][i] == 1)
                        {
                            L[curr] = number[i];
                            if (!(L[curr] <= number[prev]))
                            {
                                res += myStack.Pop();
                            }
                        }
                    }
                }
            }
            return res;

int number[N] и int L[N], где N — количество вершин графа. Для каждой вершины v в number[v] будем хранить номер этой вершины в порядке обхода графа в глубину, а в L[v] запишем число number[w], где w — вершина, которая связана обратным ребром с v или каким-либо из потомков v в остовном дереве и имеет минимальный возможный номер number, либо number[v], если такой вершины w найти не удалось.

Добавлено через 1 минуту
Уже всяко перековеркал код, ничего не выходит(((

Добавлено через 9 минут
Делал по этому алгоритму, но вывести все равно не получается((
Сформулируем алгоритм поиска точек сочленения более строго. Реализуем рекурсивную функцию void go(int curr, int prev), где curr — текущая вершина, а prev — вершина, из которой мы попали в текущую. При первом вызове curr = r, prev = –1. В теле функции будут выполняться следующие шаги:

1. Запишем в number[curr] номер вершины curr в порядке обхода в глубину.
2. Запишем в L[curr] значение number[curr].
3. Переберем в цикле все вершины, в которые есть ребро из curr. Для каждой такой вершины i выполним следующие действия:
а) Если вершина i еще не посещена, вызовем рекурсивно функцию go с параметрами i, curr. Если после этого значение L[i] стало меньше, чем L[curr], присвоим L[curr] = L[i].
б) Если вершина i уже была посещена и ее номер number[i] < number[curr], и при этом i не равно prev (т.е. ребро (i, prev) обратное и возвращается в вершину с меньшим номером), то если L[curr] > number[i], присвоим L[curr] = number[i].

Данный алгоритм заполнит массивы L[N] и number[N] требуемым образом. Проверять, является ли вершина точкой сочленения, можно на шаге 3a. Также, если реализовать стек для хранения ребер, можно реализовать вывод самих двусвязных компонент: ребро нужно добавлять в стек на шагах 3a (перед рекурсивным вызовом) и 3b и выталкивать из стека в поток вывода все ребра вплоть до текущего (curr, i), если на шаге 3а выяснилось, что для текущей вершины curr выполняется условие теоремы.

Добавлено через 48 минут
Вроде так:

C#

public string traversal(int curr, int prev, bool flag)
        {
            number[curr] = curr;
            L[curr] = number[curr];
            visited[curr] = 1; /* помечаем текущую вершину как пройденную */
            for (int i = 1; i < visited.Length; i++)
            {
                if ((visited[i] == 0) && (graf[curr][i] == 1))
                {
                    if (curr != i)
                        frame[curr][i] = 1;
                    myStack.Push(Convert.ToString(curr) + " " + Convert.ToString(i));
                    traversal(i, curr, false); //рекурсивно заходим
                    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;
                        }
                        res += "; ";
                    }
                }
                if ((visited[i] == 1) && (number[i] < number[curr]) && (i != prev))
                {
                    if ((L[curr] > number[i]))
                    {
                        if (graf[curr][i] == 1)
                        {
                            L[curr] = number[i];
                            myStack.Push(Convert.ToString(curr) + " " + Convert.ToString(i));
                        }
                    }
                }
            }
            return res;
        }

Добавлено через 21 час 29 минут
Вот вроде выше написал, все нормально, но если допустим ввести граф
0010
0011
1100
0100
то ничего работать не будет, выдает ответ: 2 4 ; 3 2 , 1 3 ; А должен: 2 4; 3 2; 1 3;

C#

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));
                        }
                    }
                }
            }

Добавлено через 1 час 41 минуту
Поможет кто?

@robert19 29 / 29 / 7 Регистрация: 26.03.2010 Сообщений: 305
		1
	Поиск двусвязных компонент. Граф задается матрицей смежности 09.03.2012, 20:49. Показов 4996. Ответов 1 Метки нет (Все метки) Всем доброе время суток. У меня такое задание. *Поиск двусвязных компонент. Граф задается матрицей смежности.* Матрицу смежности написал, там ничего сложного. А вот как найти двух связные компоненты, вообще понять не могу. Толи по матрице нужно создавать дерево, или прям из матрицы можно? Вообщем вообще понять не могу что это и с чем его кушать. Объясните пж! 0

	20.03.2012, 16:44

Поиск двусвязных компонент. Граф задается матрицей смежности

Решение