Форум программистов, компьютерный форум, киберфорум
Delphi для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
16 / 16 / 1
Регистрация: 29.11.2014
Сообщений: 227
1

Ориентированный граф через списки смежности

27.07.2017, 01:10. Просмотров 779. Ответов 3
Метки нет (Все метки)

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

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
unit uMain;
 
interface
 
uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs;
 
type TadjencyListElement=^AdjencyListElement;
 
   AdjencyListElement=record
 
   vertex:integer; // number of adjency vertex
   weight:integer;
   next:TadjencyListElement; // pointer to next vertex
 
end;
 
 
type
  TMain = class(TForm)
  private
    { Private declarations }
 
    procedure addEdge(AVertex1, AVertex2:integer);
 
  public
    { Public declarations }
  end;
 
const N=10;
var
  Main: TMain;
  Graph:Array [1..N] of TadjencyListElement;
 
implementation
 
{$R *.dfm}
 
{ TMain }
 
procedure TMain.addEdge(AVertex1, AVertex2:integer);
 
var newAdjencyListElement:TadjencyListElement;
      tempAdjencyListElement:TadjencyListElement;
 
begin
 
// will insert edge beetwen vertex 1 and 2
 
 if Graph[AVertex1]<>nil then begin // if TadjencyListElementin in vertex1 already exists , add to the end of adjency list
 
 
  New(newAdjencyListElement);
  newAdjencyListElement.Vertex:=AVertex2;
  newAdjencyListElement.next:=nil;
 
  tempAdjencyListElement:=Graph[AVertex1];
  while tempAdjencyListElement^.Next<>nil do
  tempAdjencyListElement:=tempAdjencyListElement^.next; // now tempAdjencyListElement is the last in adjency list
 
  tempAdjencyListElement^:=newAdjencyListElement; // now it points to the last added adjency element
 
 end else
 
 begin  // creating first new element of adjency list
 
    New(newAdjencyListElement);
    newAdjencyListElement^.Vertex:=AVertex2;
    newAdjencyListElement^.next:=nil;
 
 end;
 
 
end;
 
 
 
end.
Добавлено через 2 часа 15 минут
Ну в общем, всё очевидно, чистим память перед закрытием

Delphi
1
2
3
4
5
6
procedure TMain.clearMemory;
var
  i: Integer;
begin
 for i := 0 to High(Graph) do if Graph[i]<>nil then  Dispose(TadjencyListElement(Graph[i]));
end;
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.07.2017, 01:10
Ответы с готовыми решениями:

Дан ориентированный граф найти, возможно ли попасть из вершины К в вершину M
Дан ориентированный граф найти, возможно ли попасть из вершины К в вершину M ...

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

Граф задан матрицей смежности. Определите, существует ли в графе путь между двумя заданными вершинами(в делфи).
Помогите пожалуйста с Задачей, как ни пробовала - не получается... Граф задан матрицей смежности....

Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством пересечений
Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством...

3
4513 / 3737 / 1254
Регистрация: 14.04.2014
Сообщений: 17,381
Записей в блоге: 17
27.07.2017, 05:35 2
все что нужно делать с памятью, отлично делает система классов. сколько можно извращаться.
Delphi
1
2
3
4
5
6
7
8
9
10
11
TNode = class
  ID:integer;
end;
TEdge = class
  Node1,Node2:TNode;
  weight:integer;
end;
TNodeList=class(TObjectList<TNode>)
end;
TEdgeList=class(TObjectList<TEdge>)
end;
Заводим список вершин и ребер
Delphi
1
2
nodes:=TNodeList.Create;
edges:=TEdgeList.Create;
добавляем пару вершин и ребро, которое их соединяет
Delphi
1
2
3
4
5
6
7
8
9
10
11
node:=TNodeList.Create();
node.ID:=nodes.Count;
nodes.Add(Node);
node:=TNodeList.Create();
node.ID:=nodes.Count;
nodes.Add(Node);
 
edge:=TEdge.Create;
edge.node1:=nodes[0];
edge.node2:=nodes[1];
edges.add(Edge);
после работы при уничтожении списков уничтожатся и объекты
Delphi
1
2
edges.free;
nodes.free;
1
16 / 16 / 1
Регистрация: 29.11.2014
Сообщений: 227
27.07.2017, 09:33  [ТС] 3
Хм... гениально, krapotkin !
Маленькое ИМХО. Но зачем так делать?
Delphi
1
node:=TNodeList
понятнее ведь так?
Delphi
1
node:=TNode.Create
Добавлено через 20 секунд
Или это код на коленке?
0
4513 / 3737 / 1254
Регистрация: 14.04.2014
Сообщений: 17,381
Записей в блоге: 17
27.07.2017, 10:22 4
ессно опечатко
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.07.2017, 10:22

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Из матрицы смежности сделать ориентированный граф
Какаю библиотеку использовать что би нарисовать граф?Возможно есть готов код ,буду очень...

От матрицы смежности к списку ребер, ориентированный граф
Ориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер. ...

Ориентированный граф. Получить из списка рёбер матрицу смежности
Задача: Простой ориентированный граф задан списком ребер, выведите его представление в виде матрицы...

Как преобразовать неориентированный граф в ориентированный граф из матричной записи
Есть ли какой нибудь алгоритм преобразования Неориентированный графа в ориентированный граф из...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.