Версия для печати темы

Автор: Reflex 15.10.2006 16:27

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

Автор: volvo 15.10.2006 16:34

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

См. здесь: http://ric.uni-altai.ru/Fundamental/pascal3/lab1/lab1-index.htm

Автор: Reflex 15.10.2006 22:15

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

Автор: Reflex 16.10.2006 0:25

не знаете?

Автор: volvo 16.10.2006 1:47

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

Автор: Reflex 16.10.2006 2:30

на делфях

Автор: volvo 16.10.2006 2:35

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

Кстати, загляни сюда:
http://www.intuit.ru/department/pl/plpascal/11/3.html - еще 3 способа представления графов, более экономичные, чем матричные... Выбирай...

Автор: Reflex 16.10.2006 2:46

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

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

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

Автор: Michael_Rybak 16.10.2006 3:49

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

Автор: Reflex 16.10.2006 11:01

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

Автор: Michael_Rybak 16.10.2006 17:12

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

Автор: Reflex 16.10.2006 21:11

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

Автор: Reflex 16.10.2006 23:21

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

Автор: Michael_Rybak 17.10.2006 0:17

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

Можно так. Берем из файла/генерим/читаем список (массив) всех ребер, т.е. пар вида (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;

Автор: мисс_граффити 17.10.2006 2:38

ох ни фига себе ты его обозвала!
бедный мужик.
в общем, вот нужный тебе алгоритм:
http://algolist.manual.ru/maths/graphs/shortpath/dijkstra.php

Автор: Reflex 20.10.2006 0:21

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

Автор: volvo 20.10.2006 0:46

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

Вот тут: http://forum.pascal.net.ru/index.php?s=&showtopic=2706&view=findpost&p=23570
все написано...

Автор: Reflex 20.10.2006 1:13

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

Автор: volvo 20.10.2006 1:32

http://ric.uni-altai.ru/Fundamental/pascal3/lab3/lab3-index.htm

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

Автор: мисс_граффити 20.10.2006 3:11

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

Автор: Reflex 20.10.2006 10:22

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