Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.81
MaX47
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 23
#1

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

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

Имеется задача : построить транзитивное замыкание для неориентир графа(метод Уоршала не предлагать) , помогите с этим делом ,хотя бы алгоритм.Вообще как мне сказал препод ,можно использовать поиск в глубину, но я не могу понять как .
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2011, 19:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Транзитивное замыкание неор графа (C++):

Теорие графов. Композиция двух неор. графов. - C++
Здравствуйте. Прошу помощи уже здесь :| (old topic)... Прошу помочь с составлением алгоритма "Композиции двух неориентированных графов". ...

заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь - C++
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь. Помогите написать...

Лямбда-выражения и замыкание - C++
Здравствуйте, изучаю новый для себя стандарт языка и не совсем могу разобраться с замыканием Прогнал по отладчику - c изменяется...

Насколько корректно будет работать замыкание? - C++
Мой друг-JS'ер бросил мне очередной челлендж. В этот раз он мне предложил сделать замыкание для a*x+y function line(k,b){ return...

Объяснить термин "замыкание" и код - C++
Прочитал и всё равно ничего не понял. Даже код не помог. Прошу объяснить. function<int()> f() { int x = 0; return ()...

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

8
valeriikozlov
Эксперт С++
4675 / 2501 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2011, 08:53 #2
MaX47, какие-нибудь наработки есть?
1
MaX47
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 23
29.12.2011, 10:00  [ТС] #3
Вот что успел сделать,но прога зависает, причем непонятно где.и еще ответ желателен в виде матрицы достижимости
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
Эксперт С++
4675 / 2501 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2011, 10:21 #4
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
greeezz
274 / 167 / 4
Регистрация: 10.07.2011
Сообщений: 441
29.12.2011, 10:33 #5

Не по теме:

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


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

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

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

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


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



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

Добавлено через 8 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Сообщение от greeezz
randomize();
вопрос к автору темы
из STDLIB если не ошибаюсь
0
greeezz
274 / 167 / 4
Регистрация: 10.07.2011
Сообщений: 441
29.12.2011, 11:11 #8
Цитата Сообщение от MaX47 Посмотреть сообщение
из STDLIB если не ошибаюсь
если б оно у меня там было я бы и не интересовался.. вы случаем не в борланде все это делаете ?
0
MaX47
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 23
29.12.2011, 17:05  [ТС] #9
Цитата Сообщение от greeezz Посмотреть сообщение
если б оно у меня там было я бы и не интересовался.. вы случаем не в борланде все это делаете
В нем ,В нем родимиом!
0
29.12.2011, 17:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2011, 17:05
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.