# The source code(DFS)
|
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150 |
#include <stdio.h>
#include <stdlib.h>
#define NUM_VERTEX 5
struct node
{
int v;
struct node * next;
};
struct node * graph[NUM_VERTEX];
/* visit or not */
int visited[NUM_VERTEX] = { 0 };
/* stack related */
int stack[NUM_VERTEX];
int top = -1;
int isEmpty()
{
if (top == -1)
{
return 1;
}
return 0;
}
int isFull()
{
if (top == NUM_VERTEX - 1)
{
return 1;
}
return 0;
}
int pop()
{
if (isEmpty() == 1)
{
printf("fail to pop \n");
return -999;
}
else
{
int v = stack[top];
top--;
return v;
}
}
int push(int v)
{
if (isFull() == 1)
{
printf("fail to push \n");
return -999;
}
else
{
top++;
stack[top] = v;
return 1;
}
}
void addEdge(int v1, int v2, int reverse)
{
struct node *new_one = (struct node *)malloc(sizeof(struct node));
struct node *cur = graph[v1];
new_one->v = v2;
new_one->next = 0;
if (cur == 0)
{
graph[v1] = new_one;
}
else
{
while (cur->next != 0)
{
cur = cur->next;
}
cur->next = new_one;
}
if (reverse == 1)
{
addEdge(v2, v1, 0);
}
return;
}
void showAdjacentVertex(int v)
{
struct node * cur = graph[v];
while (cur != 0)
{
printf("%d is a %d's adjacent vertex \n", cur->v, v);
cur = cur->next;
}
}
// not visited vertex that is related to 'v'
int findNextVertex(int v)
{
struct node * cur = graph[v];
while (cur != 0)
{
if (visited[cur->v] == 0)
{
return cur->v;
}
cur = cur->next;
}
return -1;
}
void doDFS(int v)
{
printf("visited %d \n", v);
visited[v] = 1;
push(v);
while (isEmpty() == 0)
{
int next_vertex = -1;
next_vertex = findNextVertex(stack[top]);
if (next_vertex == -1)
{
pop();
}
else
{
printf("visited %d \n", next_vertex);
visited[next_vertex] = 1;
push(next_vertex);
}
}
}
void main()
{
addEdge(0, 1, 1);
addEdge(0, 2, 1);
addEdge(0, 4, 1);
addEdge(1, 2, 1);
addEdge(2, 3, 1);
addEdge(2, 4, 1);
addEdge(3, 4, 1);
doDFS(1);
} |
cs |
# The result(DFS)
# The source code(BFS)
|
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138 |
#include <stdio.h>
#include <stdlib.h>
#define NUM_VERTEX 5
struct node
{
int v;
struct node * next;
};
struct node * graph[NUM_VERTEX];
/* visit or not */
int visited[NUM_VERTEX] = { 0 };
/* queue related */
int head = 0;
int tail = 0;
int que[NUM_VERTEX];
int isEmpty()
{
if (head == tail)
{
return 1;
}
else
{
return 0;
}
}
int isFull()
{
if (((tail + 1) % NUM_VERTEX) == head)
{
return 1;
}
else
{
return 0;
}
}
void enque(int v)
{
if (isFull() == 1)
{
printf("Queue is full \n");
return;
}
else
{
tail = (tail + 1) % NUM_VERTEX;
que[tail] = v;
return;
}
}
int deque()
{
if (isEmpty() == 1)
{
printf("Queue is empty \n");
return -1;
}
else
{
head = (head + 1) % NUM_VERTEX;
return que[head];
}
}
void addEdge(int v1, int v2, int reverse)
{
struct node *new_one = (struct node *)malloc(sizeof(struct node));
struct node *cur = graph[v1];
new_one->v = v2;
new_one->next = 0;
if (cur == 0)
{
graph[v1] = new_one;
}
else
{
while (cur->next != 0)
{
cur = cur->next;
}
cur->next = new_one;
}
if (reverse == 1)
{
addEdge(v2, v1, 0);
}
return;
}
// visite non-visited vertex that is related to 'v'
void addAdjacentNonVistiedVertexToQue(int v)
{
struct node * cur = graph[v];
while (cur != 0)
{
if (visited[cur->v] == 0)
{
enque(cur->v);
}
cur = cur->next;
}
return -1;
}
void doBFS(int v)
{
enque(v);
while (isEmpty() == 0)
{
int next_vertex = deque();
if (visited[next_vertex] == 0)
{
printf("BFS visited %d \n", next_vertex);
visited[next_vertex] = 1;
addAdjacentNonVistiedVertexToQue(next_vertex);
}
}
}
void main()
{
addEdge(0, 1, 1);
addEdge(0, 2, 1);
addEdge(0, 4, 1);
addEdge(1, 2, 1);
addEdge(2, 3, 1);
addEdge(2, 4, 1);
addEdge(3, 4, 1);
doBFS(0);
} |
cs |
# The result(BFS)
'그 외 공부 > Algorithm' 카테고리의 다른 글
| # 14_Dijkstra (0) | 2017.11.21 |
|---|---|
| # 13_MST(Minimum spanning tree) (0) | 2017.11.20 |
| # 11_Graph (0) | 2017.11.05 |
| # 10_Sorting (0) | 2017.11.05 |
| # 9_Heap (0) | 2017.11.05 |