графы Опции

[Reflex]

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

[volvo]

Ну, кроме матрицы смежностей есть еще и матрицы инцидентности, достижимости...

См. здесь: "Представление графов с помощью матриц"

[Reflex]

а как ни буть не матрицей?
у меня вершин <=1 000 000

Сообщение отредактировано: Reflex - 15.10.2006 22:16

[Reflex]

не знаете?

[volvo]

у меня вершин <=1 000 000

Ты на чем это собралась программировать? Смотри:
граничный случай - 1 000 000 вершин. Допустим, что для описания одной вершины тебе нужен 1 байт... Миллион байт - 976К... У тебя в Турбо-Паскале размер кучи ограничен 640К... Понимаешь, в чем дело?

[Reflex]

на делфях

[volvo]

Тогда чего ты волнуешься за размерность матрицы? Дельфи и больше способна переварить, чем несколько мегабайт.. Хотя, с другой стороны, может ты и права...

Кстати, загляни сюда:
11. Лекция: Графы и деревья - еще 3 способа представления графов, более экономичные, чем матричные... Выбирай...

[Reflex]

1 000 000 * 1 000 000 of longint превышает 2 гб а меня по условия задачи максимум 64 мб

списки смежности - то что нужно но как реализовать?

вы не думайте что я все задачи спрашиваю пока получились все (13 ) кроме вот этой

[Michael_Rybak]

А с какого сайта решаешь, если не секрет?

[Reflex]

я не с сайта, просто лектор раздает задачи . И чтоб не вылететь надо сделать 99%. А пока только начало не хочется пропускать задачи, ведь дальше еще сложнее будет!

[Michael_Rybak]

Запугивает ;)
Так а в чем задача, собственно? С графом которая.

[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;

[мисс_граффити]

ох ни фига себе ты его обозвала!
бедный мужик.
в общем, вот нужный тебе алгоритм:
алголист - алгоритм Дейкстры

[Reflex]

Помогите, пожалуйста. кто знает указатели, можите сделать граф с помощью указателей ... больше всего мнен подходит спискок смежности. Пожалуйста помогтие гибну...

[volvo]

больше всего мнен подходит спискок смежности.

Ну, так это же обычный односвязный список, каждый элемент которого состоит из информационного поля и указателя на следующий элемент...

Вот тут: FAQ: Все о динамических структурах данных -> Списки
все написано...

[Reflex]

Читала, не получается реализовать а факю форума почти все прошерстила.

[volvo]

Представление графов с помощью динамических структур данных

(смотри "Теоретические сведения" №1 и №2, и, соответственно, для них же Демонстрационные примеры №1 и №2)

[мисс_граффити]

так. стоп.
надо хранить как-нибудь или по алгоритму Дейкстры?