Входные и выходные данные - Формирование списка окрестностей вершин ориентированного графа по заданной матрице инцидентности

Программа получает данные из файла (по умолчанию course. txt), в котором хранится матрица инцидентности ориентированного графа. На основе считанных из файла данных строится динамический линейный список, хранящий список окрестностей ориентированного графа.

На выходе выводятся:

    - список окрестностей вершин, которым задан данный граф; - максимальная степень захода вершины ориентированного графа; - список окрестностей вершин графа после удаления вершины с максимальной степенью захода

Компоненты списка имеют следующую структуру:

Struct comp {

Int name;

Int okr[100];

Comp* next;

};

Алгоритм функции int search (dyn_list l)

Параметры, принимаемые функцией:

Dyn_list l - список переданный по значению

Рисунок 2.2 (Приложение)

Алгоритм основной функции

Анализ временной и емкостной сложности

Анализ временной сложности

N - количество вершин, m количество ребер

Void out_file (dyn_list l)

F1=1+5Q(n)

Void comp_del (dyn_list &;l, comp* c)

F2=4+2(Q(m))^2*Q(n)+Q(n)

Void print_list (dyn_list l)

F3=1+3Q(m)*Q(n)

Void constr_list (dyn_list &;l)

F4=1

Bool chk_empty (dyn_list l)

F5=1

Void comp_in(dyn_list &;l, int n, int **ptarray, int V, int K)

F6=6+2*Q(m)*(Q(n)+1)

Int search (dyn_list l)

F7=2+(4+2*Q(m))Q(n)

Int search1 (dyn_list l, int n)

F8=(Q(m)^2+3)*Q(n)

Int main

F=5+n*m+11Q(n)+F1+F2+F3+F4+F5+F6+F7+F8

Похожие статьи




Входные и выходные данные - Формирование списка окрестностей вершин ориентированного графа по заданной матрице инцидентности

Предыдущая | Следующая