-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDFS and BSF for not-connected graphs
111 lines (106 loc) · 1.65 KB
/
DFS and BSF for not-connected graphs
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
#include <iostream>
#include <queue>
using namespace std;
void printDFS(int** edges,int n,int sv,bool* visited)
{
cout<<sv<<endl;
visited[sv]=true;
for(int i=0;i<n;i++)
{
if(sv==i)
continue;
if(edges[sv][i]==1)
{
if(visited[i])
continue;
printDFS(edges,n,i,visited);
}
}
}
void printBFS(int** edges,int n,int sv,bool* visited)
{
queue<int> pendingvertices;
pendingvertices.push(sv);
visited[sv]=1;
while(!pendingvertices.empty())
{
int currentvertex = pendingvertices.front();
cout<<currentvertex<<endl;
pendingvertices.pop();
for(int i=0;i<n;i++)
{
if(i==currentvertex)
continue;
if(edges[currentvertex][i]==1 && visited[i]==0)
{
pendingvertices.push(i);
visited[i]=1;
}
}
}
}
void DFS(int** edges,int n)
{
bool* visited = new bool[n];
for(int i=0;i<n;i++)
{
visited[i]=0;
}
for(int i=0;i<n;i++)
{
if(!visited[i])
printDFS(edges,n,i,visited);
}
delete [] visited;
}
void BFS(int** edges,int n)
{
bool* visited = new bool[n];
for(int i=0;i<n;i++)
{
visited[i]=0;
}
for(int i=0;i<n;i++)
{
if(!visited[i])
printBFS(edges,n,i,visited);
}
delete [] visited;
}
int main()
{
int n;
int e;
cin>>e>>n;
int** edges = new int*[n];
for(int i=0;i<n;i++)
{
edges[i]=new int[n];
for(int j=0;j<n;j++)
{
edges[i][j]=0;
}
}
for(int i=0;i<e;i++)
{
int f,s;
cin>>f>>s;
edges[f][s]=1;
edges[s][f]=1;
}
// bool* visited = new bool[n];
// for(int i=0;i<n;i++)
// {
// visited[i]=0;
// }
cout<<"DFS"<<endl;
DFS(edges,n);
// printDFS(edges,n,0,visited);
// for(int i=0;i<n;i++)
// {
// visited[i]=0;
// }
cout<<"BFS"<<endl;
BFS(edges,n);
// printBFS(edges,n,0,visited);
}