Форум программистов, компьютерный форум, киберфорум
Delphi для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.92/26: Рейтинг темы: голосов - 26, средняя оценка - 4.92
 Аватар для RandomCat
3 / 3 / 2
Регистрация: 15.06.2011
Сообщений: 42

Списки смежности графа

05.11.2011, 12:37. Показов 5499. Ответов 5
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Помогите оптимизировать\исправить мои функции пожалуйста.
Задание такое: найти все сильные компоненты орграфа. Граф должен быть задан списками смежности.
Вот как это делаю я:
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
type  List = ^Vertex;
 
      Vertex = record
      Ver: integer;
      next: List;
  end;
 
var
  N,R,ch:integer;
  Graph:array [1..10] of List;
 
function CreateVertex(v,k:integer):integer; //создание вершины
begin
if (Graph[k]=nil) then
  begin
  end
else
  begin
  end;
end;
 
procedure Add(v1,m,v2,n: integer);  // Äîáàâëÿåì ðåáðî
var tmp:List;
    i,j:integer;
begin
    i:=CreateVertex(v1,m); //âîçâðàùàåò íîìåð âåðøèíû â âåêòîðå
    j:=CreateVertex(v2,n);
    new(tmp);
    tmp^.ver := v1;
    tmp^.next := j;
    i := tmp;
end;
 
function CreateVertex(v,k:integer):integer;
var
begin
if (Graph[k]=nil) then
  begin
    new(tmp);
    tmp^.ver := v1;
  end
else
  begin
  end;
end;
 
procedure MakeGraph(n:integer);
// Ïîñòðîåíèå ñïèñêîâ ñìåæíîñòè ãðàôà.
var m,n,x,y,i:integer;
begin
  m:=0;
  n:=1
  for i:=1 to n do
  begin
  WriteLn('Vvedite nachalo dugi: ');
  ReadLn(x);
  WriteLn('Vvedite konec dugi: ');
  ReadLn(y);
  m:=m+1;
  n:=n+1;
  Add(x,m,y,n);
  end;
end;
 
//Âûâîä ñîäåðæèìîãî ñïèñêîâ ñìåæíîñòè, ñîîòâåòñòâóþùèõ îðèåíòèðîâàííîìó ãðàôó.
procedure PrintGraph();
var
  i:integer;
  u:List; //Ðàáî÷èé óêàçàòåëü.
begin
clrscr;
  for i:=1 to N do
  begin
    u:=Graph[i];
    if (u.next=nil) then
      begin
      Write(u.ver);
      WriteLn('--X');
      end
    else
      begin
      while (u<>nil) do
        begin
          Write(u.ver);
          Write('--->');
          u := u.next;
        end;
        WriteLn;
      end;
  end;
end;
Правильно ли я реализовала списки смежности? Если да, то помогите закончить функцию создания вершины (CreateVertex) так, чтобы можно было использовать ее потом в создании ребра (Add).
Я пытаюсь оптимизировать программу так, чтобы можно было вводить вершины разные, не в определенном порядке (не 1,2,3... а 4,27,52,1..., т.е. название вершины <> ее порядковому номеру).
Буду признательна за любую помощь или подсказку.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
05.11.2011, 12:37
Ответы с готовыми решениями:

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

По матрице смежности графа составить матрицу инциденций
По матрице смежности графа составить матрицу инциденций

Вывод матрицы смежности с файла в stringGrid и построение графа
В файле находится матрица смежности, ее нужно ввести и вывести на экран в stringGrid Например 7 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0...

5
 Аватар для RandomCat
3 / 3 / 2
Регистрация: 15.06.2011
Сообщений: 42
05.11.2011, 12:50  [ТС]
Вот сама программа, если понадобится.
Вложения
Тип файла: rar граф.rar (25.8 Кб, 200 просмотров)
0
 Аватар для RandomCat
3 / 3 / 2
Регистрация: 15.06.2011
Сообщений: 42
06.11.2011, 13:49  [ТС]
http://ric.uni-altai.ru/Fundam... eor3-1.htm - что такое списки смежности.

Добавлено через 22 часа 47 минут
Похоже, что лучше вообще без указателей обойтись. Буду все переделывать
0
446 / 374 / 133
Регистрация: 09.09.2011
Сообщений: 1,346
06.11.2011, 18:29
списки смежности без указателей не сделать. Плохо, что вводишь новый тип с именем как у встроенного типа делфи - List. лучше другое имя использовать.

Добавлено через 5 минут
есть книга, где задачки с графами на паскале подробно разобраны (и вообще 90% всех алгоритмических задач которые дают младшим студентам/школьникам) - "Алгоритмы и программы решение олимпиадных задач" И.Н. Порублёв, А.Б. Ставровский. рекомендую. есть и на рутрекере.
http://rutracker.org/forum/viewtopic.php?t=1035916
1
 Аватар для RandomCat
3 / 3 / 2
Регистрация: 15.06.2011
Сообщений: 42
06.11.2011, 19:19  [ТС]
Kitayets, Я где-то прочла, что можно просто сделать двумерный массив для списков смежности, если знаешь, что граф не будет изменяться в процессе работы программы. Вот так и делаю.
За книгу - спасибо. Почитаю.
0
446 / 374 / 133
Регистрация: 09.09.2011
Сообщений: 1,346
06.11.2011, 19:38
как раз в этой книги и описывается что для представления графа "обычно" используют либо с помощью матриц (двумерных массивов) - матрица смежности, либо с помощью массивов в сочетании со связными списками - структура смежности. далее цитата: "Выбор представления зависит от числа вершин и рёбер, а также особенностей конкретных алгоритмов и задач."
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
06.11.2011, 19:38
Помогаю со студенческими работами здесь

Ориентированный граф через списки смежности
Повторяю для себя очевидные вещи, перевожу с C++ на Дельфи, но тень сомнения затмила мой разум) Ниже код добавления ребра в представление...

Списки смежности дуг ориентированного графа
По заданию нужно представить орграф списками смежности дуг, вида {LIST}^{+}_{b},{LIST}^{-}_{b},{LIST}^{+}_{B},{LIST}^{-}_{B}, но, к...

Из списка смежности в матрицу смежности. Выполнить обход графа глубину
Помогите пожалуйста с программой: Дан список смежности. Преобразовать в матрицу смежности. Выполнить обход графа в глубину. Заранее...

Вывести матрицу смежности и список смежности графа
Всем привет!! Уважаемые форумчане, помогите плиз с заданием! Я написала код в Си по которому вводим матрицу инцидентности и выводим...

По заданной матрице смежности простого графа построить каркас этого графа с использованием поиска в ширину
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь. Помогите написать...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Новые блоги и статьи
Модель заражения группы наркоманов
alhaos 17.04.2026
Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .
Мысли в слух. Про "навсегда".
kumehtar 16.04.2026
Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .
My Business CRM
MaGz GoLd 16.04.2026
Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .
Знаешь почему 90% людей редко бывают счастливыми?
kumehtar 14.04.2026
Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД
Maks 14.04.2026
Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code
Loafer 13.04.2026
{ "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы
Maks 13.04.2026
Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений
Maks 12.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru