-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcycle_check_in_graph.c
108 lines (93 loc) · 4.2 KB
/
cycle_check_in_graph.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
/*check whether there is a cycle in graph*/
#include <stdio.h>
#include <string.h>
#define TOTAL_NODE_NUMBER 6
char adj_matrix[TOTAL_NODE_NUMBER][TOTAL_NODE_NUMBER] = {
1,0,0,0,0,0,
0,1,0,0,0,1,
0,1,1,0,0,0,
1,0,0,1,0,0,
1,0,0,0,1,0,
0,0,1,1,1,1
};
/*nodeset_dst[i][k][]表示i节点经过K跳可达节点集合
*nodeset_dst_cnt[i][k]记录节点i从发经过k跳可达节点的个数
*nodeset_map[i][j]; 0-3bit非0表示节点j在节点i的可达目的节点集合中，4-7bit非0表示节点i在节点j的可达目的节点集合中。
*shortest_path[i][j][]记录从i到j经过的最短路径*/
char nodeset_dst[TOTAL_NODE_NUMBER][TOTAL_NODE_NUMBER][TOTAL_NODE_NUMBER];
char nodeset_dst_cnt[TOTAL_NODE_NUMBER][TOTAL_NODE_NUMBER-1];
char nodeset_map[TOTAL_NODE_NUMBER][TOTAL_NODE_NUMBER];
/*shortest_path[i][j].node_set表示从i到j的路径包含到节点，含i，j
*shortest_path[i][j].node_cnt表示从i到j到路径包含的节点个数，含i，j*/
typedef struct stPath {
char node_cnt;
char node_set[TOTAL_NODE_NUMBER];
} stPath;
stPath shortest_path[TOTAL_NODE_NUMBER][TOTAL_NODE_NUMBER];
void add_to_shortest_path(char firstnode, char lastnode, char newnode) {
char tmp_cnt, i;
tmp_cnt = shortest_path[firstnode][lastnode].node_cnt;
for(i = 0; i < tmp_cnt; i++) {
shortest_path[firstnode][newnode].node_set[i] = shortest_path[firstnode][lastnode].node_set[i];
}
shortest_path[firstnode][newnode].node_set[i] = newnode;
shortest_path[firstnode][newnode].node_cnt = i + 1;
}
void graph_init() {
int node_index;
memset(nodeset_dst, -1, sizeof(nodeset_dst));
memset(nodeset_dst_cnt, 0, sizeof(nodeset_dst_cnt));
memset(nodeset_map, 0, sizeof(nodeset_map));
memset(shortest_path, -1, sizeof(shortest_path));
for(node_index = 0; node_index < TOTAL_NODE_NUMBER; node_index ++) {
nodeset_dst[node_index][0][0] = node_index;
nodeset_dst_cnt[node_index][0] = 1;
nodeset_map[node_index][node_index] |= 0x11;
shortest_path[node_index][node_index].node_set[0] = node_index;
shortest_path[node_index][node_index].node_cnt = 1;
}
}
void print_cycle(int src, int dst) {
int i;
printf("cycle is :\n");
for(i = 0; i < shortest_path[src][dst].node_cnt; i++) {
printf ("%d ", shortest_path[src][dst].node_set[i]);
}
for(i = 1; i < shortest_path[dst][src].node_cnt; i++) {
printf ("%d ", shortest_path[dst][src].node_set[i]);
}
printf("\n");
}
void main() {
int node_index, jump, i, j;
int last_node, node_cnt;
graph_init();
for(node_index = 0; node_index < TOTAL_NODE_NUMBER; node_index ++) { //遍历图中每个节点
for(jump = 1; ; jump ++){//遍历从一个节点A出发的跳数
for(i = 0; i < nodeset_dst_cnt[node_index][jump-1]; i ++) {//遍历到节点A距离jump-1跳的节点
last_node = nodeset_dst[node_index][jump -1][i];
for(j = 0; j < TOTAL_NODE_NUMBER; j ++) {//以到节点A距离jump-1跳的节点b作为起始地点查找jump跳的节点
if((last_node == j) || ((nodeset_map[node_index][j] & 0x0f) != 0)){
continue;
} else if(adj_matrix[last_node][j] != 0) {
//将节点j加入到node_index的jump跳可达节点中
add_to_shortest_path(node_index, last_node, j);
//printf("node:%d, jump:%d, lastnode:%d, newnode:%d\n",node_index, jump, last_node, j);
node_cnt = nodeset_dst_cnt[node_index][jump];
nodeset_dst[node_index][jump][node_cnt] = j;
nodeset_dst_cnt[node_index][jump] ++;
nodeset_map[node_index][j] |= 0x01;
nodeset_map[j][node_index] |= 0x10;
if((nodeset_map[node_index][j] & 0xf0) != 0){
//找到环了,打印shortest_path中的路径
print_cycle(node_index, j);
return;
}
}
}
}
if (nodeset_dst_cnt[node_index][jump] == 0)
break;
}
}
}