algorithms/Src/Graph/BasicGraph.h at master · Vekteur/algorithms · GitHub

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
#pragma once

#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>

#include "Graph/Graph.h"

template<typename L>
std::vector<int> dfsStack(const AdjList<L>& g, int start) {
	std::vector<int> preOrder;
	std::vector<int> vis(g.size());
	vis[start] = true;
	std::stack<int> st;
	st.push(start);

	while (!st.empty()) {
		int u = st.top(); st.pop();
		preOrder.push_back(u);

		for (Edge<L> v : g.adj[u]) {
			if (!vis[v.to]) {
				vis[v.to] = true;
				st.push(v.to);
			}
		}
	}
	return preOrder;
}

template<typename L>
std::vector<int> bfs(const AdjList<L>& g, int start) {
	std::vector<int> preOrder;
	std::vector<int> vis(g.size());
	vis[start] = true;
	std::queue<int> q;
	q.push(start);

	while (!q.empty()) {
		int u = q.front(); q.pop();
		preOrder.push_back(u);

		for (Edge<L> v : g.adj[u]) {
			if (!vis[v.to]) {
				vis[v.to] = true;
				q.push(v.to);
			}
		}
	}
	return preOrder;
}