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

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

Восстановить пароль Регистрация
 
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
01.12.2013, 22:39     Поиск в глубину с классификацией ребер #1
Здравствуйте. Задание в теме, использовал алгоритм с вики (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();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.12.2013, 22:39     Поиск в глубину с классификацией ребер
Посмотрите здесь:

Поиск в глубину C++
C++ итеративный поиск в глубину
C++ поиск в глубину
C++ Не работает поиск в глубину (DFS)
C++ графы,поиск в глубину
графы. поиск в глубину C++
Поиск в глубину C++
C++ Поиск в глубину

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 04:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru