forked from TheAlgorithms/C
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbfs_queue.c
More file actions
124 lines (115 loc) · 3.2 KB
/
Copy pathbfs_queue.c
File metadata and controls
124 lines (115 loc) · 3.2 KB
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
#include <stdbool.h>
#include <stdio.h>
#include "Graph.h"
#include "queue.h"
#define MAX_NODES 1000
int visited[MAX_NODES]; // array to store visiting order
// indexed by vertex 0..nV-1
bool findPathBFS(Graph g, int nV, Vertex src, Vertex dest)
{
Vertex v;
for (v = 0; v < nV; v++) visited[v] = -1;
visited[src] = src;
queue Q = newQueue();
QueueEnqueue(Q, src);
while (!QueueIsEmpty(Q))
{
v = QueueDequeue(Q);
Vertex w;
for (w = 0; w < nV; w++)
if (adjacent(g, v, w) && visited[w] == -1)
{
visited[w] = v;
if (w == dest)
return true;
else
QueueEnqueue(Q, w);
}
}
return false;
}
int main(void)
{
int V = 10;
Graph g = newGraph(V);
Edge e;
e.v = 0;
e.w = 1;
insertEdge(g, e);
e.v = 0;
e.w = 2;
insertEdge(g, e);
e.v = 0;
e.w = 5;
insertEdge(g, e);
e.v = 1;
e.w = 5;
insertEdge(g, e);
e.v = 2;
e.w = 3;
insertEdge(g, e);
e.v = 3;
e.w = 4;
insertEdge(g, e);
e.v = 3;
e.w = 5;
insertEdge(g, e);
e.v = 3;
e.w = 8;
insertEdge(g, e);
e.v = 4;
e.w = 5;
insertEdge(g, e);
e.v = 4;
e.w = 7;
insertEdge(g, e);
e.v = 4;
e.w = 8;
insertEdge(g, e);
e.v = 5;
e.w = 6;
insertEdge(g, e);
e.v = 7;
e.w = 8;
insertEdge(g, e);
e.v = 7;
e.w = 9;
insertEdge(g, e);
e.v = 8;
e.w = 9;
insertEdge(g, e);
int src = 0, dest = 6;
if (findPathBFS(g, V, src, dest))
{
Vertex v = dest;
while (v != src)
{
printf("%d - ", v);
v = visited[v];
}
printf("%d\n", src);
}
return 0;
}
// By
// .----------------. .----------------. .----------------.
// .-----------------. .----------------. .----------------.
// | .--------------. || .--------------. || .--------------. ||
// .--------------. | | .--------------. || .--------------. | | | _________ |
// || | _____ _____ | || | __ | || | ____ _____ | | | | ____ ____
// | || | ____ | | | | | _ _ | | || ||_ _||_ _|| || | / \
// | || ||_ \|_ _| | | | | |_ || _| | || | .' `. | | | | |_/ | |
// \_| | || | | | | | | || | / /\ \ | || | | \ | | | | | | |
// |__| | | || | / .--. \ | | | | | | | || | | ' ' | | || |
// / ____ \ | || | | |\ \| | | | | | | __ | | || | | | | | | |
// | | _| |_ | || | \ `--' / | || | _/ / \ \_ | || | _| |_\ |_
// | | | | _| | | |_ | || | \ `--' / | | | | |_____| | || | `.__.'
// | || ||____| |____|| || ||_____|\____| | | | | |____||____| | || | `.____.'
// | | | | | || | | || | | || | | | | |
// | || | | | | '--------------' || '--------------' ||
// '--------------' || '--------------' | | '--------------' || '--------------'
// |
// '----------------' '----------------' '----------------'
// '----------------' '----------------' '----------------'
// Email : z5261243@unsw.edu.au
// hhoanhtuann@gmail.com