0 / 0 / 0
Регистрация: 21.04.2015
Сообщений: 8
1

Удалить недостижимые вершины ориентированного графа

18.12.2015, 19:25. Показов 1884. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Помогите пожалуйста реализовать программный код из консоли в ооп. Задача такая: из ориентированного графа удалить все вершины, от которых недостижима заданная. Знаю как представить граф в image, связи задать, матрицу смежности, не могу сам алгоритм нахождения недостижимых вершин описать. Ниже программа в ооп
Вот код консоли
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 Type Uk=^Rebro; //тип указателя на ребро
        Rebro=Record   //тип описывающий ребро графа
     Ver1, Ver2 : Integer;      //вершины графа
     Next: Uk;             //указатель на следующее ребро
     Bool: Boolean;     //признак прохождения по ребру
        end;
Var  P, P1:Uk;
     N, M, i, j, a : Word;
     Way : Set of Byte; //множество достижимых вершин
 
 
Procedure Input;
var i:word;
  Begin
    Write(' Vvedite colichectvo verhin :  ');  ReadLn(N);
    Write(' Vvedite colichectvo reber:  ');      ReadLn(M);
    P:=nil;  //цепочка ребер пуста
    For i:= 1 to M do
       begin New(P1); //создание нового ребра
        Write ('Vvedite 1-u verhinu ',i,'-go rebra:  ');  Read(P1^.Ver1);
        Write ('Vvedite 2-u verhinu ',i,'-go rebra:  ');  Read(P1^.Ver2);
        P1^.Bool :=TRUE;  P1^.Next :=P; //прикрепляем новое ребро кначалу
        P:=P1;  //новое ребро становится началом цепочки
         end;
End;
 
Procedure Poisk (i:Byte);
    Var tt:Uk;     //указатель на текущее ребро
Begin
 Way:=Way+[i];  //добавляем вершину во множество достихнутых
 tt:=p;         //перемещаем указатель на начало цепочки
 While tt <> nil do // пока не конец цепочки
  begin If (i=tt^.Ver1) and tt^.Bool    //находим ребро которое выходит
    then    //из i-ой вершины в которой не были
    begin tt^.Bool := FALSE; //отмечаем что прошли
     Poisk(tt^.Ver2);   //уходим на вторую вершину
     tt^.Bool := TRUE;  //снимает отметку о прохождении
    end;
    tt:=tt^.Next;
  end;
end;
 
begin
    Input; //ввод графа
Write('zadaite verhinu dla cotoroi ihutca nedoctigimii verdhini: '); ReadLn(A);
    Way:=[];    //обнуляем множество достижимых вершин
    Poisk(A);   //процедура обхода графа
    for j:=1 to N do
      if not (j in Way) then WriteLn( j, '-ia verhina nedoctigima iz verhini ',  A);
    if Way = [1 .. N] then WriteLn('Vce verhini doctigimi iz verhini ', A);
    ReadLn
  end.
Вложения
Тип файла: 7z орграф.7z (188.8 Кб, 11 просмотров)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.12.2015, 19:25
Ответы с готовыми решениями:

Найти все вершины графа, недостижимые из заданной вершины
Найти все вершины графа, недостижимые из заданной вершины. Нужен алгоритм!! Я запутался!

Автоматическое построение ориентированного графа
Сломал себе мозг, но не могу решить проблему! Необходимо на основе таблицы построить...

Из графа удалить все вершины, от которых недостижима заданная
Задание: из графа удалить все вершины, от которых недостижима заданная. Все удаляется, кроме...

Найти все вершины заданного графа, недостижимые от заданной его вершины
Прошу помощи в написании программы с использованием обхода в глубину. Условие задачи: Найти все...

0
18.12.2015, 19:25
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.12.2015, 19:25
Помогаю со студенческими работами здесь

Найти все вершины заданного графа, недостижимые от заданной его вершины
Помогите написать программу. Условие: Найти все вершины заданного графа, недостижимые от заданной...

Графы. Найти все вершины заданного графа, недостижимые от заданной его вершины
Найти все вершины заданного графа, недостижимые от заданной его вершины. Помогите решить...

Найти все пути, соединяющие две вершины ориентированного графа.
Помогите дописать программу. #include&lt;stdio.h&gt; #include&lt;conio.h&gt; int visited; int A; void...

Поиск самого длинного пути от первой до последней вершины ацикличного ориентированного невзвешенного графа
Здравствуйте! Есть задача найти самый длинный путь от первой до последней вершины ацикличного...

Найти все вершины графа, к которым существует путь заданной длины от выделенной вершины графа
Написать программу на prologuse на русском языке как на примере(Определить, является ли связным...

Найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа
Пользуясь алгоритмом Дейкстры, найти кратчайшее расстояние из вершины v1 неориентированного...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru