Рекурсивная реализация void dfc_rec unsigned visited true for unsigned

 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
// Рекурсивная реализация
void dfc_rec(unsigned v) {
visited[v] = true;
for (unsigned i = 0; i < N; ++i)
{
if (!matrix[v][i]){
continue;
}
if (visited[v]){
continue;
}
dfc_rec(i);
}
}
struct _record
{
unsigned v, i;
};
// Нерекурсивная реализация
void dfc_norec(int v) {
_record record;
unsigned dwOldCount = 0;
push(record);
while (!empty()){
visited[v] = true;
unsigned i = 0;
for (i = dwOldCount; i < N; ++i) {
if (matrix[v][i] && !visited[v]) {
record.v = v; record.i = i;
push(record);
v = i;
break;
}
}
if (i + 1 == N) {
record = pop();
v = record.v;
dwOldCount = record.i;
}
}
}