Поиск всех точек сочленения заданного графа

Министерство образования и науки Российской Федерации

Новосибирский Государственный Технический Университет

Кафедра прикладной математики

Курсовая работа по практикуму на ЭВМ:

структуры данных и алгоритмы

Факультет:                прикладной математики и информатики

Группа:                     

Студент:                   

Преподаватель:        

Новосибирск 2010

1. Условие

Вершина графа называется точкой сочленения, если её удаление приводит к увеличению числа компонент связанности. Найти все точки сочленения заданного графа.

2. Анализ задачи

2.1. Исходные данные задачи:

n – количество вершин в графе,

m – количество рёбер в графе,

E – множество рёбер графа,

2.2. Результат:

        – множество точек сочленения графа

2.3. Решение:

// tin[v] – время захода поиска в глубину в вершину v

// fup[v] = min(

//     tin[v],

//     tin[p], // (v,p) – обратное ребро

//     fup[to], // (v,to) – ребро дерева поиска в глубину

// )

ПоискВГлубину(v, p = -1)

{

    Пометить вершину v

    tin[v] = fup[v] = ВремяЗахода

    ВремяЗахода = ВремяЗахода + 1

    КоличествоПотомков = 0

    Для каждой вершины to, смежной с v

    {

        Если (to помечена)

        {

            fup[v] = min(fup[v], tin[to])

        }

        иначе

        {

            КоличествоПотомков = КоличествоПотомков + 1

            ПоискВГлубину(to, v)

            fup[v] = min(fup[v], fup[to])

            Если (fup[to] >= tin[v])

            {

                v – точка сочленения

            }

        }

    }

    Если (p == -1)

    {

        Если (КоличествоПотомков > 1)

        {

            v – точка сочленения

        }

        иначе

        {

            v – не точка сочленения

        }

    }

}

Для каждой вершины v

{

    Если (v не помечена)

    {

        ПоискВГлубину(v, -1)

    }

}

Формальная постановка задачи

Запустим обход в глубину из произвольной вершины графа, обозначив её через root. Заметим два следующих факта:

1) Пусть v – вершина графа, v ≠ root. Тогда, если найдётся такой потомок t вершины v в дереве поиска, что ни из него, ни из какого-либо его потомка нет ребра (обратного) в предка вершины v, то вершина v будет являться точкой сочленения. В противном случае, вершина v не является точкой сочленения.

2) Рассмотрим теперь корень root дерева поиска. Тогда он является точкой сочленения тогда и только тогда, когда он имеет как минимум двух потомков в дереве поиска.

Таким образом, пользуясь вышеописанным критерием, необходимо для каждой вершины графа показать, является она точкой сочленения или нет. Следует учесть, что если граф несвязный, поиск в глубину необходимо запускать из вершин каждой компоненты связности.

3. Структуры данных, используемые для представления исходных данных и результатов задачи

3.1. Входные данные

Внешнее представление неориентированного графа:

<ребро-графа> ::= <вершина-графа> пробел <вершина-графа>

<вершина-графа> ::= число

Внутреннее представление неориентированного графа: массив списков смежности (такое представление позволяет быстро найти вершины, смежные с данной, при небольшом расходе памяти)

list** G;

3.2. Выходные данные

Внешнее представление: список вершин графа, являющихся точками сочленения, или текстовое сообщения «Graph has no cutpoints».

Внутреннее представление:

bool* cutpoints;

4. Укрупнённый алгоритм решения задачи

4.1.

{

    Граф = ВводГрафа

    ПоискТочекСочленения(Граф)

}

4.2. Алгоритм поиска точек сочленения

for (i = 0..n-1)

{

      ТочкаСочленения[i] = 0

}

for (i = 0..n-1)

{

      Пометка [i] = 0

}

for (i = 0..n-1)

{

    Если (!Пометка[i])

    {

        ВремяЗахода = 0;

        ПоискВГлубину(i, -1)

    }

}

ПоискВГлубину(v, p)

{

    Пометка[v] = 1

    tin[v] = fup[v] = ВремяЗахода

    ВремяЗахода = ВремяЗахода + 1

    КоличествоПотомков = 0

    Для каждой вершины to, смежной с v

    {

        Если (Пометка[to])

        {

            fup[v] = min(fup[v], tin[to])

        }

        иначе

        {

            КоличествоПотомков = КоличествоПотомков + 1

            ПоискВГлубину(to, v)

            fup[v] = min(fup[v], fup[to])

            Если (fup[to] >= tin[v])

            {

                ТочкаСочленения[v] = 1

            }

        }

    }

    Если (p == -1)

    {

        Если (КоличествоПотомков > 1)

        {

            ТочкаСочленения[v] = 1

        }

        иначе

        {

            ТочкаСочленения[v] = 0

        }

    }

}

ПоискВГлубину(0, -1)

5. Структура программы

Текст программы разбит на три модуля.

Модуль 1 содержит основную подпрограмму, осуществляющую ввод графа, поиск точек сочленения и вывод текстового результата.

Модуль 2 содержит подпрограмму поиска точек сочленения.

Модуль 3 содержит подпрограммы для работы с двунаправленным связным списком, используемым при хранении графа.

5.1. Состав модуля 1:

Главная функция main:

Назначение: ввод графа, вызов функции поиска, вывод результата

Прототип: int main()

5.2. Состав модуля 2:

Функция find_cutpoints:

Назначение: поиск точек сочленения. Возвращает true, если такие точки были найдены, false – если не были найдены.

Прототип: bool find_cutpoints(list** G, int n, bool* dst_array)

Параметры: G – массив списков смежности графа, n – количество вершин графа, dst_array – массив, dst_array[i] = true, если вершина i является точкой сочленения.