IPB
ЛогинПароль:

> Правила раздела!

1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> графы
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


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


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






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

См. здесь: "Представление графов с помощью матриц"
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


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

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


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


не знаете?


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






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


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


на делфях


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






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

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


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


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

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

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


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


А с какого сайта решаешь, если не секрет?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


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


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Запугивает ;)
Так а в чем задача, собственно? С графом которая.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


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


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


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


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

Можно так. Берем из файла/генерим/читаем список (массив) всех ребер, т.е. пар вида (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;
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


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


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Гость






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

Вот тут: FAQ: Все о динамических структурах данных -> Списки
все написано...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


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


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






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

(смотри "Теоретические сведения" №1 и №2, и, соответственно, для них же Демонстрационные примеры №1 и №2)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 22.11.2017 0:39
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"