-
Notifications
You must be signed in to change notification settings - Fork 4
/
dfs.c
58 lines (47 loc) 路 1.22 KB
/
dfs.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
#include "dfs.h"
#include "stdio.h"
#include "stdlib.h"
int time;
void DfsVisit(graph *g, int *c, int *d, int *f, int *p, int **e, int u) {
linked_list_node *v_node;
int v;
time++;
d[u] = time;
c[u] = gray;
v_node = g->Adj[u]->nil->next;
while (v_node != g->Adj[u]->nil) {
v = v_node->key;
if (c[v] == white)
p[v] = u, e[u][v] = tree_edge, DfsVisit(g, c, d, f, p, e, v);
else if (c[v] == black)
e[u][v] = f[v] > d[u] ? forward_edge : cross_edge;
else
e[u][v] = back_edge;
v_node = v_node->next;
}
time++;
c[u] = black;
f[u] = time;
}
dfs_result Dfs(graph *g, int s) {
int u;
int *p = (int *)malloc(sizeof(int) * (g->V));
int *d = (int *)malloc(sizeof(int) * (g->V));
int *f = (int *)malloc(sizeof(int) * (g->V));
int *c = (int *)malloc(sizeof(int) * (g->V));
int **e = (int **)malloc(sizeof(int *) * (g->V + 1));
for (u = 0; u < g->V; u++) {
c[u] = white, d[u] = -1, f[u] = infinity, p[u] = NIL_VERTEX;
e[u] = (int *)malloc(sizeof(int) * (g->V + 1));
}
time = 0;
for (u = 0; u < g->V; u++)
if (c[u] == white)
DfsVisit(g, c, d, f, p, e, u);
dfs_result result;
result.d = d;
result.f = f;
result.p = p;
result.e = e;
return result;
}