Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/47: Рейтинг темы: голосов - 47, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 24

Транзитивное замыкание неор графа

28.12.2011, 19:38. Показов 8540. Ответов 8
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Имеется задача : построить транзитивное замыкание для неориентир графа(метод Уоршала не предлагать) , помогите с этим делом ,хотя бы алгоритм.Вообще как мне сказал препод ,можно использовать поиск в глубину, но я не могу понять как .
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
28.12.2011, 19:38
Ответы с готовыми решениями:

Транзитивное замыкание
Добрый вечер! Разбираю транзитивное замыкание и насколько я поняла, выполняется перемножение матриц. Однако пример, который находится на...

Транзитивное замыкание
Нужно написать программу для Транзитивного замыкания. Я не могу сделать чтобы строка умножалась на столбец ,и все это выводилось во...

Транзитивное замыкание Уоршелла
Реализовать алгоритм построения транзитивного замыкания Уоршелла и проиллюстрировать по шагам этапы его выполнения. Обязательное условие:...

8
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
29.12.2011, 08:53
MaX47, какие-нибудь наработки есть?
1
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 24
29.12.2011, 10:00  [ТС]
Вот что успел сделать,но прога зависает, причем непонятно где.и еще ответ желателен в виде матрицы достижимости
C Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <conio.h>
#define __SIZE 5
#include <stdlib.h>
 
 
int Graf[__SIZE][__SIZE];
int size = __SIZE;
int FIFO[__SIZE];
int Label[__SIZE];
 
 
 
void rndMX( void ) {
      int i,j;
    for(  i=0; i<size; i++ )
    {   for(  j=0; j<size; j++ )
            Graf[i][j] = rand()%2 ? !!rand()%10 : 0;
 
    }
 
    for( i=0;i<size;i++)
       {      Graf[i][i]=0;    }
 
    for( i=0;i<size;i++)
      for( j=0;j<size;j++)
     if(Graf[i][j]==1){
            Graf[i][j]=Graf[j][i];}
 
}
 void printMX( void ) {
    for( int i=0; i<size; i++ ) {
        for( int j=0; j<size; j++ )
            printf( " %2d", Graf[i][j] );
        printf( "\n" );
    }
}
void  main()
{
   randomize();
   int Start=0,i,j,k,p=0,m;
   rndMX( );
   for(i=0;i<(size);i++)
    {
     FIFO[i]=0;
     Label[i]=0;
    }
     printMX( );
    FIFO[0]=Start;     // Заносим в стек стартовую вершину
    Label[Start]=1;    // Присваиваем стартовой вершине метку 1
     k=1;
     m=1;
      
   while (k!=0)
  {
    
/*Находим вершину с минимальным номером, смежную с
вершиной, номер которой находится в стеке в позиции к*/
    for (i=0; i<size; i++)
     if (Graf[FIFO[k-1]][i]==1)
     {
       p=1; 
       break; 
     }      
     if (p!=0)
     {
      if (Label[i]==0) 
      {
        FIFO[k]=i;     // Заносим вершину в стек 
          m++; // Увеличиваем значение метки
         Label[i]=m;    // Помечает вершину       
         Graf[FIFO[k-1]][i]=2;
         Graf[i][FIFO[k-1]]=2;// Помечаетмребро как прямее
          k++; // Сдвигаем позицию вершины стека
                                                //на единицу вверх
      }    
      
      else 
      {
         // Помечаем ребро как обратное
       Graf[i][FIFO[k-1]]=3;
       Graf[FIFO[k-1]][i]=3;
      }
     }  
    
    else k--; // Сдвигаем позицию вершины стека на единицу вниз, тем самым удаляя  вершину из стека
   
  }
   
// Выводим результат
    
    printMX( );
  
   
   getch();
 }
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
29.12.2011, 10:21
C Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <conio.h>
#define __SIZE 5
#include <stdlib.h>
 
 
int Graf[__SIZE][__SIZE];
int size = __SIZE;
int FIFO[__SIZE];
int Label[__SIZE];
int LL[__SIZE][__SIZE];//матрица транзитивного замыкания графа
 
 
void rndMX( void ) {
      int i,j;
        for(  i=0; i<size-1; i++ )
        {       for(  j=i+1; j<size; j++ )
                        Graf[i][j] = Graf[j][i]= rand()%2;
                Graf[i][i]=0;
 
        }
        Graf[size-1][size-1]=0;
}
 void printMX( void ) {
        for( int i=0; i<size; i++ ) {
                for( int j=0; j<size; j++ )
                        printf( " %2d", Graf[i][j] );
                printf( "\n" );
        }
}
void  main()
{
   randomize();
   int Start, End,i,j,;
   rndMX( );
   printMX( );
   for(i=0; i<size; i++)
   {
       for(j=0; j<size; j++)
           Label[j]=0;
       Label[i]=1;
       Start=0; End=1; FIFO[0]=i;
       while(Start<End)
       {
           for(j=0; j<size; j++)
               if(Graf[FIFO[Start]][j]==1 && Label[j]==0)
               {
                   Label[j]=1;
                   FIFO[End++]=j;
               }
            Start++;
       }
       for(j=0; j<size; j++)
           LL[i][j]=Label[j];
   }    
   // а вот здесь вместо вывода на экран Graf[__SIZE][__SIZE] нужно вывести LL[__SIZE][__SIZE] - матрицу транзитивного замыкания графа
  
   
   getch();
 }
0
278 / 174 / 21
Регистрация: 10.07.2011
Сообщений: 441
29.12.2011, 10:33

Не по теме:

простите что вмешиваюсь. тема интересна.


Цитата Сообщение от valeriikozlov Посмотреть сообщение
int Start, End,i,j,;
эта строчка (№34)разве корректна ?
Цитата Сообщение от valeriikozlov Посмотреть сообщение
randomize();
не подскажите функция из какой библиотеки?

Добавлено через 4 минуты
да и еще хотел спрасить какой смысл делать так

C++ Скопировано
1
2
3
#define __SIZE 5
.....
int size = __SIZE;
я не увидел по коду чтобы значение size где-нибудь менялось
почему бы тогда везде не использовать __SIZE
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
29.12.2011, 10:36
Цитата Сообщение от greeezz Посмотреть сообщение
эта строчка (№34)разве корректна ?
да здесь запятую нужно убрать.

Цитата Сообщение от greeezz Посмотреть сообщение
randomize();
вопрос к автору темы


Цитата Сообщение от greeezz Посмотреть сообщение
#define __SIZE 5
.....
int size = __SIZE;
вопрос к автору темы
1
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 24
29.12.2011, 11:06  [ТС]
По поводу __SIZE действительно глупость.



Спасибо большое,заработало

Добавлено через 8 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Сообщение от greeezz
randomize();
вопрос к автору темы
из STDLIB если не ошибаюсь
0
278 / 174 / 21
Регистрация: 10.07.2011
Сообщений: 441
29.12.2011, 11:11
Цитата Сообщение от MaX47 Посмотреть сообщение
из STDLIB если не ошибаюсь
если б оно у меня там было я бы и не интересовался.. вы случаем не в борланде все это делаете ?
0
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 24
29.12.2011, 17:05  [ТС]
Цитата Сообщение от greeezz Посмотреть сообщение
если б оно у меня там было я бы и не интересовался.. вы случаем не в борланде все это делаете
В нем ,В нем родимиом!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
29.12.2011, 17:05
Помогаю со студенческими работами здесь

Что такое транзитивное замыкание?
Можете привести парочку простых примеров, а то не очень понял что это такое и как применяется.

Как задать транзитивное замыкание?
M=\begin{Bmatrix}1,3,5,7\end{Bmatrix} Отношение R= \begin{Bmatrix}(a,b):b=a+2\end{Bmatrix} Если его задать списком то получится:...

Транзитивное замыкание бинарного отношения
Подскажите пожалуйста как на заданном графе R= ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6) ) найти транзитивное замыкание бинарного...

Алгоритмом Уоршелла построить транзитивное замыкание для отношения
Алгоритмом Уоршелла построить транзитивное замыкание для отношения a+b=10, реализация на С++, спасибо заранее)

Транзитивное замыкание для бинарного соотношения (тройной цикл...)
Приветствую. Что то не пойму никак, как реализовать данный алгоритм. С программированием в маткаде не сталкивался никогда. На ум приходит...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
Работа с объемным DOM в javascript
Htext 04.04.2025
Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .
Оптимизация производительности Node.js с помощью кластеризации
run.dev 04.04.2025
Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .
Управление зависимостями в Python с Poetry
py-thonny 04.04.2025
Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .
Мониторинг с Prometheus в PHP
Jason-Webb 04.04.2025
Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .
Пакет Context в Golang: Управление потоками и ресурсами
golander 04.04.2025
Работа с горутинами в Go часто напоминает управление непослушными детьми - они разбегаются кто куда, делают что хотят и не всегда завершаются вовремя. К счастью, в Go 1. 7 появился пакет context,. . .
Контейнеризация React приложений с Docker
Reangularity 03.04.2025
Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .
Свой попап в SwiftUI
mobDevWorks 03.04.2025
SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .
Антипаттерны микросервисной архитектуры
ArchitectMsa 03.04.2025
Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .
std::mutex в C++: Советы и примеры использования
bytestream 03.04.2025
std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .
Не удержался от оценки концепции двигателя Стирлинга.
Hrethgir 03.04.2025
Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер