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

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

Войти
Регистрация
Восстановить пароль
 
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
#1

Поиск в глубину с классификацией ребер - C++

01.12.2013, 22:39. Просмотров 204. Ответов 0
Метки нет (Все метки)

Здравствуйте. Задание в теме, использовал алгоритм с вики (http://ru.wikipedia.org/wiki/Поиск_в_глубину).

Проблема в том, что условие entry[i]<leave[i] почти всегда не выполняется, а такого быть не может. Ошибку в упор увидеть не могу.

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <memory.h>
int color[25];
int entry[25];
int leave[25];
int t = 0;
int klass[25][25];
int graph[25][25];
/* klass = 1 äóãГ* äåðåâГ* ïîèñêГ*
   klass = 2 ïðÿìГ*Гї äóãГ*
   klass = 3 ïåðåêðåñòГ*Г*Гї
   klass = 4 îáðГ*ГІГ*Г*Гї
*/
 
void DFS(int i)
 {
        int k = 0;
        int j = 0;
        t++;
        entry[i]=t;
        color[i]=1;
        while (k!=25)
        {
     while ((graph[i][k]==0) || (color[k]==1))
         {
          if (graph[i][k]==0)
           j++;
          if (k<25)
       k++;
          else
          {
           if (j==25)
           {
            t++;
            leave[i]=t;
            return;
           }
           else
            return;
          }
         }
         color[k]=1;
         printf("%2d ",i);
         printf("%2d ",k);
         printf("%2d ",entry[i]);
         printf("%2d ",entry[k]);
         printf("%2d ",leave[i]);
         printf("%2d ",leave[k]);
 
         if ((entry[i]<=t) && (entry[k]==0) && (leave[k]==0))
          klass[i][k]=1;
         if ((entry[i]<=t) && (t<entry[k]) && (entry[k]<leave[k]) && (leave[k]<leave[i]) && (leave[k]!=0))
          klass[i][k]=2;
         if ((entry[i]<=t) && (t<leave[k]) && (entry[i]>leave[k]) && (leave[k]>entry[i]))
          klass[i][k]=3;
         if ((entry[k]<=entry[i]) && (t>=entry[i]) && (leave[i]<leave[k]) && (t<leave[i]))
          klass[i][k]=4;
         printf(" %d\n",klass[i][k]);
         DFS(k);
         t++;
         leave[i]=t;
        }
 }
 
void main()
{
 int j;
 printf(" i  k  ei ek li lk k\n");
 memset(color,0,sizeof(color));
 memset(klass,0,sizeof(color));
 memset(graph,0,sizeof(graph));
 memset(entry,0,sizeof(entry));
 memset(leave,0,sizeof(leave));
 graph[1][3]=1;
 graph[1][2]=2;
 graph[1][4]=3;
 graph[2][10]=4;
 graph[3][10]=5;
 graph[3][5]=6;
 graph[3][6]=7;
 graph[4][2]=8;
 graph[6][7]=10;
 graph[7][5]=11;
 graph[7][8]=12;
 graph[8][9]=13;
 graph[9][6]=14;
 graph[10][11]=15;
 graph[10][15]=16;
 graph[11][23]=17;
 graph[11][24]=18;
 graph[12][19]=19;
 graph[12][17]=20;
 graph[12][3]=21;
 graph[12][13]=22;
 graph[13][18]=23;
 graph[14][9]=24;
 graph[15][17]=25;
 graph[16][15]=26;
 graph[16][24]=27;
 graph[17][18]=28;
 graph[18][16]=29;
 graph[19][14]=30;
 graph[20][11]=31;
 graph[20][21]=32;
 graph[21][22]=33;
 graph[22][20]=34;
 graph[23][22]=35;
 graph[24][23]=36;
 graph[24][25]=37;
 graph[25][16]=38;
 for (int j=1;j<25;j++)
  DFS(j);
 for (int j=1;j<25;j++)
 {
  printf ("%2d ",j);
  printf("%2d ",entry[j]);
  printf("%2d\n",leave[j]);
 }
 getch();
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.12.2013, 22:39
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск в глубину с классификацией ребер (C++):

Поиск в глубину - C++
Здравствуйте. Как реализовать поиск кратчайшего пути в невзвешенном графе через поиск в глубину? Пробовал сделать так const...

Поиск в глубину - C++
Объясните плз поиск в глубину с примером. Сам много реалихаций нашел, но до конца не могу разобраться, может у кого есть примерчик хороший....

поиск в глубину - C++
Дали задание реализовать поиск в глубину.Пробую релизовать по e-maxx http://e-maxx.ru/algo/dfsно не получается. vector&lt;char&gt; used; int...

Поиск в глубину - C++
&quot;В рождественскую ночь Санта-Клаус спускается по каминной трубе и раскладывает детям подарки. Кровати в комнате стоят очень плотно. Чтобы...

Поиск в глубину - C++
Помогите с заданием пожалуйста. Число 1 можно записать как сумму n чисел вида 1 / i, где i - натуральное число. Например, для n = 3 имеем...

Рекурсивный поиск в глубину - C++
Нужно найти путь по простому лабиринту от точки к точке, используя в программе рекурсивный поиск в глубину. Фотографию примера лабиринта...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.12.2013, 22:39
Привет! Вот еще темы с ответами:

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

графы. поиск в глубину - C++
Здраствуйте. Вот такая задача N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0 ≤ M ≤ 45) соединений паp шестеpенoк в виде (i,...

Итеративный поиск в глубину - C++
Здравствуйте! Вопрос связан с поиском в графе. Меня интересуют идеи решения или ссылка на литературу. Пожалуйста, подскажите... ...

Поиск в глубину. Графы. С++ - C++
Задана ,допустим, такая матрица смежности 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 Node.h #pragma once


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

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

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