графы Опции

[Reflex]

как хранить граф ( самые малозанимающий по весу кб способ) не матрица смежности

[Reflex]

помогите дийстру не прошу писать, прошу тольоко написать тип граф

[Michael_Rybak]

Судя по всему, имеется ввиду представление в виде списка ребер.

Можно так. Берем из файла/генерим/читаем список (массив) всех ребер, т.е. пар вида (a, b). Если граф неориентированный, дублируем ребра, т.е. кроме (a, b) храним (b, a).

Сортируем этот список по a, т.е. по первому элементу пары. В результате получим, что сначала идут все ребра, исходящие из первой вершины, потом - из второй и т.д.

Теперь пробегаем по этому списку, и заполняем массивы first[] и last[], так, что first[i] - первое ребро в списке, исходящее из вершины i, а last[i] - последнее.

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


Итого, тип "граф" представляет из себя запись с пятью переменными:

//не тестил, не компилил

const MAX_N: longint = ???; //максимальное кол-во вершин
const MAX_EDGES: longint = ???; //максимальное количество ребер

type TEdge = record
       a, b: longint
     end;

type TGraph = record
       n: longint;
       n_edges: longint;
       edges: array [1 .. MAX_EDGES] of TEdge;
       first: array [1 .. MAX_N] of longint;
       last: array [1 .. MAX_N] of longint;
     end;

...

procedure FillFirstAndLast(var g: TGraph)
  var i: longint;
begin

  SortEdges(g);//сортировка ребер по a

  //считаем сначала, что все вершины - изолированные
  for i := 1 to g.n do begin
    g.first[i] := 0;
    g.last[i] := -1;
  end;

  //пробегаем по ребрам
  for i := 1 to g.n_edges do begin
    if g.first[g.edges[i].a] = 0 then
      g.first[g.edges[i].a] := i;
    g.last[g.edges[i].a] := i;
  end;
    
end;

...

procedure DijkstraRelax(a: longint; var g: TGraph);
  var b, edge_index: longint;
begin
  ...
  //релаксация вершины i
  //пробегаем по всем, достижимым из нее
  for edge_index := g.first[a] to g.last[a] do begin
    b := g.edges[edge_index].b;
    //делаем что-то с b
  end;
  ...
end;