邻接矩阵存图的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
#include <iostream>
#include <list>
#include <vector>

using namespace std;

void addEdge(vector<list<int> > &adj, int i, int j) {
adj[i].push_back(j);
adj[j].push_back(i);
}

void DFS(vector<list<int> > &adj,int i,bool visited[]){
visited[i] = true;
cout << i << " ";
for (auto j = adj[i].begin(); j != adj[i].end(); j++)
{
if (!visited[*j])
DFS(adj, *j, visited);
}
}

void DFStraverse(vector<list<int> > &adj,int V){
bool* visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

for (int i = 0; i < V; i++)
{
if (!visited[i])
DFS(adj,i,visited);
}
}

void printGraph(vector<list<int> >& adj, int V)
{
for (int i = 0; i < V; ++i)
{
cout << " " << i << endl;

for (int & j : adj[i])
cout << j << " ";
cout << endl;
}
}

int main()
{
int V = 4;
vector<list<int> > adj(4);

addEdge(adj, 0, 1);
addEdge(adj, 0, 2);
addEdge(adj, 1, 2);
addEdge(adj, 2, 3);
printGraph(adj,V);
DFStraverse(adj,V);
return 0;
}