Нужна помощь по си.Тема:Графы и матрицы смежности.

 

DiSok

втянувшийся
Спасибо за помощь! ;)помогите составить алгоритм, хотя бы в общих чертах.
Имеется неориентированный граф представленный смежной матрицей .
Требуется реализовать функцию :
code text
  1. void find_reachable(
  2. char adj[NUM_VERTICES] [NUM_VERTICES],
  3. unsigned int v,
  4. unsigned int reachable[])

которая возвращает все достижимые вершины от данной вершины V
где adj матрица смежностей,v это данная вершина ,reachable массив, содержащий в себе результаты функции... если от вершины v возможно достичь вершины i тогда reachabel[i]=1
к примеру если v1,v2,v4,v5 достижимые (reachable) тогда при данном V =2, reachable[1]=1 reachable[2]=1
reachable[4]=1
требуемая сложность вычислений (complexity) памяти 0(1), т.е. нельзя использовать динамическую память.

п.с. я знаю,что есть алгоритм BFS который работает с Матрицами инцидентности, однако мне нужно реализовать именно со смежными... Спасибо!
 

DiSok

втянувшийся
Ребята? Кто нибудь?
 
EE Татарин #10.08.2008 17:22
+
-
edit
 

Татарин

координатор
★★★★☆
"Все ушли на фронт" (С) :)
Если честно, над твоей задачей чуток посидеть, подумать надо, а народу просто не до того - новости читают. :)

Задача практическая?
насколько велика матрица?
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  

DiSok

втянувшийся
Спасибо татарин, ты званный гость.. ;)
Задача практическая, решаемая... размер матрицы опеределен NUM_VERTICES в #define.
Спасибо. Я тут уже второй день голову ломаю, думал может тут кто на путь истинный наведет..
В добавок рекурсией пользоваться нельзя! (почему то я только о ней и думаю! :( )
 
DiSok> Спасибо за помощь! ;)помогите составить алгоритм, хотя бы в общих чертах.
Уже неактуально, но я попробую. Ради спортивного интереса.
DiSok> требуемая сложность вычислений (complexity) памяти 0(1),
Условия не совсем корректно даны вами. Как правило отдельно указывается требуемая сложность алгоримта по вычислениям и по памяти. O(1) здесь скорее всего - это сложность по памяти. Буду считать, что требований по сложности вычислений нет, так как O(1) по вычислениям - это бред.
DiSok> т.е. нельзя использовать динамическую память.
Не так. Это означает, что объём требуемой алгоритму памяти не должен зависеть от NUM_VERTICES.
DiSok> В добавок рекурсией пользоваться нельзя! (почему то я только о ней и думаю! :( )
Какое-то бредовое ограничение. Если речь о недопустимости реккуретного вызова ф-ций при обходе графа, то это всего лишь следствие требования O(1) по памяти.
Воздух выдержит только тех, Только тех, кто верит в себя, Ветер дует туда, куда Прикажет тот, кто верит в себя.  
+
-
edit
 

Mishka

модератор
★★★
DiSok>> Спасибо за помощь! ;)помогите составить алгоритм, хотя бы в общих чертах.
sabakka> Уже неактуально, но я попробую. Ради спортивного интереса.
Блин, мимо пропустил. Неужели совсем образование уплыло в России? Ведь стандартная же задача в курсе дискретной математики (теория графов или терия сетей). И древняя, как Г мамонта. Матрица достижимости — Википедия

А алгоритм Уоршала, который не в лоб — тоже древний — 1962 год. Алгоритм Флойда–Уоршелла — Википедия
 
+
-
edit
 
Mishka> Блин, мимо пропустил. Неужели совсем образование уплыло в России? Ведь стандартная же задача в курсе дискретной математики (теория графов или терия сетей). И древняя, как Г мамонта. Матрица достижимости — Википедия
Mishka> А алгоритм Уоршала, который не в лоб — тоже древний — 1962 год. Алгоритм Флойда–Уоршелла — Википедия
Так сказано же: требуемая сложность по памяти O(1). Иначе решение получается тривиальным.
Как вы после применения алгоритма Уоршала будете исходную матрицу смежности восстанавливать?
Подсказка: граф ненаправленный.
Воздух выдержит только тех, Только тех, кто верит в себя, Ветер дует туда, куда Прикажет тот, кто верит в себя.  
Это сообщение редактировалось 22.08.2011 в 14:07

TEvg

аксакал

админ. бан
Mishka> Блин, мимо пропустил. Неужели совсем образование уплыло в России? Ведь стандартная же задача в курсе дискретной математики (теория графов или терия сетей). И древняя, как Г мамонта.

Стандартная-то стандартная. Но я к примеру уже не решу - маразм и старость. Разве что на шарашку посадят, с инетом, вплоть до решения - тогда решу.
 3.6.133.6.13
+
-
edit
 

Mishka

модератор
★★★
sabakka> Так сказано же: требуемая сложность по памяти O(1). Иначе решение получается тривиальным.

О(1) — это константа. Не растёт. Возьми две матрицы. При умножении в лоб умножают матрицу до степени N.

sabakka> Подсказка: граф ненаправленный.

И что?
 

Mishka

модератор
★★★
TEvg> Стандартная-то стандартная. Но я к примеру уже не решу - маразм и старость. Разве что на шарашку посадят, с инетом, вплоть до решения - тогда решу.

Тут не самому решать надо, а просто почитать учебник. В этом и состоит упражнение для студентов. Найти, оценить, применить. Тот же алгоритм Уоршалла вовсе не так тривиален, как кажеться. Даже в лоб уже не так тривиален, т.к. требует знания работы с матрицами, логических операция и прочего. Более того, простой алгоритм з может и сам напишу, а вот Уоршалла — уже надо брать литературу.


А так одно из применений — в линковщиках задач, в частности на мэйнфреймах она часто строилась, поэтому на той же ЕС ЭВМ OS (OS/360, /370, /390, SVS, MVS, ...)поруадок библиотек не имеет значения, в отличии от того UNIX-а и линя.
 
+
-
edit
 

Mishka

модератор
★★★
программирование компьютеры техника


Матрица достижимости — Википедия


Матрица достижимости
Материал из Википедии — свободной энциклопедии
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 15 апреля 2010;
проверки требуют 5 правок.
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 15 апреля 2010;
проверки требуют 5 правок.


// Дальше —
ru.wikipedia.org
 



По определению, матрица композиции отношений есть , где — конъюнкция, а — дизъюнкция.

После нахождения матриц композиций для всех будет получена информация о всех путях длины от 1 до n. Таким образом, матрица есть искомая матрица достижимости.

Смотри, нужно реовно три матрицы одинакового размера — исходная, степень ишодной для построения степени (или матрицы композиций), результат — накапливаем. Берём исходную и инициализируем обе для накопления и результат. Потом получаем степень 2 и тут же ORаем в результат. Получаем степень 3 умножай степень 2 на исходную и опять ORаем в ресультат. Никакого динамического использования памяти, все матрицы определены (могут быть) через define-ры.
 
Это сообщение редактировалось 22.08.2011 в 16:45

Mishka

модератор
★★★
Да, и ещё замечание. Матрица смежности всегда квадратная (вершина-вершина связь), а матрица инцидентности — прямоугольная (вершина-ребро связь). Преобразование из одного в другое достаточно тривиальная задача.
 
+
-
edit
 
sabakka>> Так сказано же: требуемая сложность по памяти O(1). Иначе решение получается тривиальным.
Mishka> О(1) — это константа. Не растёт. Возьми две матрицы. При умножении в лоб умножают матрицу до степени N.
O(1) по памяти означает, что объём используемой алгоритмом доп.памяти не должен зависеть от NUM_VERTICES.
Алгоритм Уоршала позволяет это сделать, но как после заполнения вектора достижимости для требуемой исходной вершины вернуть исходную матрицу смежности? Алгоритм, который портит после себя исходные данные, переданные ему по ссылке, очевидно, не годится.

sabakka>> Подсказка: граф ненаправленный.
Mishka> И что?
Это означает, что исходная матрица смежности содержит избыточную информацию.
Воздух выдержит только тех, Только тех, кто верит в себя, Ветер дует туда, куда Прикажет тот, кто верит в себя.  
+
-
edit
 

Mishka

модератор
★★★
sabakka> O(1) по памяти означает, что объём используемой алгоритмом доп.памяти не должен зависеть от NUM_VERTICES.

У тебя просто представление исходных данных уже не будет, как О(1) в твоём понимании. Поскольку исходные данные. Когда учили, то у нас О(1) было именно статическое размещение (хотя эта метрика официальной не была). Потому, я думаю, что рекурсия запрещена, т.к. это неявное размещение динамическое на стеке. Поэтому и можно всё дефайнером определить.

sabakka> Алгоритм Уоршала позволяет это сделать, но как после заполнения вектора достижимости для требуемой исходной вершины вернуть исходную матрицу смежности? Алгоритм, который портит после себя исходные данные, переданные ему по ссылке, очевидно, не годится.

Ты говоришь про вектор достижимости. Понятно, что для одного элемента, это строка/столбец из матрицы достижимости. В твоём понимании, О(1) не получится, если только не гадить в исходные данные.

Можно ещё пойти и путём ленивых вычислений. Для вычисления вершина-вершина в лоб надо сделать по "или" из матриц композиций отношений до степени N. Для вычисления элемента уже надо хранить вектор степеней. Т.е. не получиться обойтись одной переменной. Для Флойда-Уоршелла тоже мжно зафиксировать внутрение переменные цикла, но внешнюю не выйдет — нужно замыкание. Посмотрел на Кнута, Джонса и Данцига — вроде те же проблемы.

Ну, нет правда у нас ограничений на количество ввода-вывода. :) Можно исходную там хранить. :) Или вывести заранее исходную, а потом строить замыкание.

sabakka> Это означает, что исходная матрица смежности содержит избыточную информацию.
Ты, видимо, считаешь то, что там симметрия получается получается? Кто тебе мешает работать с треугольной матрицей?
 6.06.0
+
-
edit
 
sabakka>> O(1) по памяти означает, что объём используемой алгоритмом доп.памяти не должен зависеть от NUM_VERTICES.
Mishka> У тебя просто представление исходных данных уже не будет, как О(1) в твоём понимании. Поскольку исходные данные.
Не будет. Требование O(1) относится только к доп. памяти.

Mishka> Когда учили, то у нас О(1) было именно статическое размещение (хотя эта метрика официальной не была).
Этого не может быть.

Mishka> Потому, я думаю, что рекурсия запрещена, т.к. это неявное размещение динамическое на стеке.
А тут получается, что рекурсия сама по себе будет нарушать требование O(1) по памяти.

Mishka> Поэтому и можно всё дефайнером определить.
Это нарушение условий задачи.

Mishka> Ты говоришь про вектор достижимости. Понятно, что для одного элемента, это строка/столбец из матрицы достижимости. В твоём понимании, О(1) не получится, если только не гадить в исходные данные.
Гадить можно, но нужно и убрать за собой. Возможно ли это воообще и как это сделать? В этом и вся суть задачи.

Mishka> Можно ещё пойти и путём ленивых вычислений....
Дальше ничего не понял.

Mishka> Ну, нет правда у нас ограничений на количество ввода-вывода. :) Можно исходную там хранить. :) Или вывести заранее исходную, а потом строить замыкание.
У нас есть ссылка на матрицу смежности и вектор достижимости, а также индекс начальной вершины всё.
Воздух выдержит только тех, Только тех, кто верит в себя, Ветер дует туда, куда Прикажет тот, кто верит в себя.  
+
-
edit
 
Так как граф ненаправленный, то матрица смежности симметрична. То есть можно гадить в одну половину и использовать вторую для восстановления исходной матрицы смежности.
code c
  1. #include <stdio.h>
  2.  
  3. #define NUM_VERTICES 6
  4.  
  5. void find_reachable(char adj[NUM_VERTICES][NUM_VERTICES],
  6.                     unsigned int v,
  7.                     unsigned int reachable[NUM_VERTICES])
  8. {
  9.     unsigned int k, i, j;
  10.     for(k = 0; k < NUM_VERTICES; k++)
  11.         for(i = 0; i < NUM_VERTICES; i++)
  12.             for(j = i + 1; j < NUM_VERTICES; j++)
  13.             {
  14.                 char v1 = (k > i) ? adj[i][k] : adj[k][i];
  15.                 char v2 = (k < j) ? adj[k][j] : adj[j][k];
  16.                 adj[i][j] = adj[i][j] || (v1 && v2);
  17.             }
  18.     for(i = 0; i < NUM_VERTICES; i++)
  19.         reachable[i] = v < i ? adj[v][i] : adj[i][v];
  20.     reachable[v] = 1;
  21.     for(i = 0; i < NUM_VERTICES; i++)
  22.         for(j = i; j < NUM_VERTICES; j++)
  23.         adj[i][j] = adj[j][i];
  24. }
  25.  
  26. void printMatrix(char m[NUM_VERTICES][NUM_VERTICES])
  27. {
  28.     int i, j;
  29.     for(i = 0; i < NUM_VERTICES; i++)
  30.     {
  31.         for(j = 0; j < NUM_VERTICES; j++)
  32.             printf("%d ", m[i][j]);
  33.         printf("\n");
  34.     }
  35. }
  36.  
  37. int main(int argc, const char * argv[])
  38. {
  39.     int i, v;
  40.     char rm[NUM_VERTICES][NUM_VERTICES] = { { 0, 1, 1, 0, 0, 0 },
  41.                                             { 1, 0, 0, 0, 0, 0 },
  42.                                             { 1, 0, 0, 1, 0, 0 },
  43.                                             { 0, 0, 1, 0, 0, 0 },
  44.                                             { 0, 0, 0, 0, 0, 1 },
  45.                                             { 0, 0, 0, 0, 1, 0 }};
  46.     unsigned int result[NUM_VERTICES];
  47.  
  48.     printf("Adjacency matrix:\n");
  49.     printMatrix(rm);
  50.     printf("\n");
  51.  
  52.     for(v = 0; v < NUM_VERTICES; v++)
  53.     {
  54.         find_reachable(rm, v, result);
  55.         printf("Reachability vector for vertex %d: ", v);
  56.         for(i = 0; i < NUM_VERTICES; i++)
  57.             printf("%d ", result[i]);
  58.         printf("\n");
  59.     }
  60.     printf("\n");
  61.  
  62.     printf("Adjacency matrix again:\n");
  63.     printMatrix(rm);
  64.     printf("It's not corrupted ;\n");
  65.     return 0;
  66. }
Воздух выдержит только тех, Только тех, кто верит в себя, Ветер дует туда, куда Прикажет тот, кто верит в себя.  
+
-
edit
 

Mishka

модератор
★★★
sabakka> Не будет. Требование O(1) относится только к доп. памяти.

Где? В исходнике:
требуемая сложность вычислений (complexity) памяти 0(1), т.е. нельзя использовать динамическую память.

sabakka> Этого не может быть.
Ы?
sabakka> А тут получается, что рекурсия сама по себе будет нарушать требование O(1) по памяти.
Я тебе это и сказал.

sabakka> Это нарушение условий задачи.

О(1) там уже по представлению исходных данных не выходит.

sabakka> Гадить можно, но нужно и убрать за собой. Возможно ли это воообще и как это сделать? В этом и вся суть задачи.

Кто тебе сказал, что гадить можно? :)

sabakka> У нас есть ссылка на матрицу смежности и вектор достижимости, а также индекс начальной вершины всё.

Откуда появился вектор достижимости?
 6.06.0
+
-
edit
 

Mishka

модератор
★★★
sabakka> Так как граф ненаправленный, то матрица смежности симметрична. То есть можно гадить в одну половину и использовать вторую для восстановления исходной матрицы смежности.

Можно и проще — где стояли 1 работаем в положительном, где 0 работаем в отрицательном. Потом убрать отрицательные. Всё. И даже второй половины не понадобится. Можно разнести на 1, 2.


И для орграфов работает, только уже надо разносить на -1, -2, 1, 2.
 6.06.0
+
-
edit
 
Mishka> Где? В исходнике:
Mishka> требуемая сложность вычислений (complexity) памяти 0(1), т.е. нельзя использовать динамическую память.
Человек просто неправильно понял условия задачи, и я его поправил. Я уже решал подобные задачи. В лоб они легко решаются, но к ним выдвигаются требования к сложности алогоритма по вычислениям и памяти.

Mishka> О(1) там уже по представлению исходных данных не выходит.
Не тормози.

Mishka> Кто тебе сказал, что гадить можно? :)
Потому что Нагадить + Убрать == Не нагадить

Mishka> Откуда появился вектор достижимости?
См. код выше.
Воздух выдержит только тех, Только тех, кто верит в себя, Ветер дует туда, куда Прикажет тот, кто верит в себя.  
+
-
edit
 

Mishka

модератор
★★★
sabakka> Не тормози.

Блин, у тебя появился вектор. Откуда он? Размер вектора зависит от входных данных. Почему вектор, а не матрица достижимости? Ты не видишь у тебя появилась куча своих условий, которых нет в исходных.

sabakka> Потому что Нагадить + Убрать == Не нагадить

Вовсе нет. Часто память, которую дают, rad only для твоего процесса.

Mishka>> Откуда появился вектор достижимости?
sabakka> См. код выше.
Нафиг тот код. Ты произвольно ввёл его. Ну так введи произвольно матрицу и/или две матрицы. Фигна одного порядка.

PS А, увидел заголовок ф-ции. :) По непонятным причинам он unsigned int.

PPS Он ещё не понятной размерности. :)
 6.06.0
Это сообщение редактировалось 23.08.2011 в 01:38

в начало страницы | новое
 
Поиск
Поддержка
Поддержи форум!
ЯндексЯндекс. ДеньгиХочу такую же кнопку
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru