深度遍历
简介
遍历一开始,第一个开始遍历的顶点是没有被遍历过的顶点,依次递归遍历当前顶点下第一个相邻顶点,只要是没有被遍历过的顶点,就一直递归下去,如果是已经递归过的顶点就跳过。
深度遍历的特点是可以方便找到一张图的 连通分量
。从一顶点开始,一直按照深度遍历的逻辑递归下去,等到递归完毕,如果图中还存在没有被遍历过的顶点,说明存在两个连通分量,若第二个递归完毕还有没有被遍历过的顶点,说明存在三个连通分量,以此类推。
实现
/**
* 深度遍历求连通分量
*/
template<typename Graph>
class Component {
private:
/** 图 */
Graph &G;
/** 在深度遍历时,是否访问过了 */
bool *visited;
/** 连通分量个数 */
int ccount;
/**
* 递归求深度遍历
*/
void dfs(int v) {
// 首先更改成已访问
visited[v] = true;
// 遍历 v 的相邻顶点
typename Graph::AdjIterator adgIter(G, v);
for (int i = adgIter.begin(); !adgIter.end(); i = adgIter.next()) {
if (!visited[i]) {
// 相邻顶点没有被遍历过
dfs(i);
}
}
}
public:
Component(Graph &graph) : G(graph) {
visited = new bool[G.v()];
ccount = 0;
// 初始化时,所有顶点都没有被访问过。
for (int i = 0; i < G.v(); ++i) {
visited[i] = false;
}
// 开始遍历顶点
for (int i = 0; i < G.v(); ++i) {
if (!visited[i]) {
// 顶点没有被遍历过
dfs(i);
// 每存在一次遍历就存在一个连通分量
++ccount;
}
}
}
~Component() {
delete[] visited;
}
/**
* 返回图的联通分量个数
*/
int count() {
return ccount;
}
};
测试:
void testComponent() {
// TestG1.txt - g1 and g2
string filename1 = "testG1.txt";
SparseGraph g1 = SparseGraph(13, false);
ReadGraph<SparseGraph> readGraph1(g1, filename1);
Component<SparseGraph> component1(g1);
cout << "TestG1.txt, Using Sparse Graph, Component Count: " << component1.count() << endl;
DenseGraph g2 = DenseGraph(13, false);
ReadGraph<DenseGraph> readGraph2(g2, filename1);
Component<DenseGraph> component2(g2);
cout << "TestG1.txt, Using Dense Graph, Component Count: " << component2.count() << endl;
cout << endl;
// TestG2.txt - g3 and g4
string filename2 = "testG2.txt";
SparseGraph g3 = SparseGraph(7, false);
ReadGraph<SparseGraph> readGraph3(g3, filename2);
Component<SparseGraph> component3(g3);
cout<<"TestG2.txt, Using Sparse Graph, Component Count: "<<component3.count()<<endl;
DenseGraph g4 = DenseGraph(7, false);
ReadGraph<DenseGraph> readGraph4(g4, filename2);
Component<DenseGraph> component4(g4);
cout<<"TestG2.txt, Using Dense Graph, Component Count: "<<component4.count()<<endl;
}
// testG1.txt
13 13
0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3
// testG2.txt
7 8
0 1
0 2
0 5
0 6
3 4
3 5
4 5
4 6
顶点之间是否相连
经过上边的步骤,知道了把一个顶点深度遍历完毕之后,就完成了一个连通分量的遍历,也就是说在一次深度遍历中(一次深度遍历相当于一个连通分量),所有被遍历到的点,其实都是相连接的,都是属于同一个连通分量。
在上面代码的基础上,增加 id
数组,采用 Quick Find
并查集的方式来记录是否相连的关系。修改后的代码:
/**
* 深度遍历求连通分量
*/
template<typename Graph>
class Component {
private:
/** 图 */
Graph &G;
/** 在深度遍历时,是否访问过了 */
bool *visited;
/** 连通分量个数 */
int ccount;
/** 记录顶点是否相连的数组 */
int *id;
/**
* 递归求深度遍历
*/
void dfs(int v) {
// 首先更改成已访问
visited[v] = true;
// 此次所有的深度遍历都应属于 ccount 所代表的的连通分量,直接使用连通分量值作为连通分量的分组表示。
id[v] = ccount;
// 遍历 v 的相邻顶点
typename Graph::AdjIterator adgIter(G, v);
for (int i = adgIter.begin(); !adgIter.end(); i = adgIter.next()) {
if (!visited[i]) {
// 相邻顶点没有被遍历过
dfs(i);
}
}
}
public:
Component(Graph &graph) : G(graph) {
visited = new bool[G.v()];
ccount = 0;
// 初始化时,所有顶点都没有被访问过。
for (int i = 0; i < G.v(); ++i) {
visited[i] = false;
id[i] = -1;
}
// 开始遍历顶点
for (int i = 0; i < G.v(); ++i) {
if (!visited[i]) {
// 顶点没有被遍历过
dfs(i);
// 每存在一次遍历就存在一个连通分量
++ccount;
}
}
}
~Component() {
delete[] visited;
}
/**
* 返回图的联通分量个数
*/
int count() {
return ccount;
}
};
经过改动就可以通过 id 数组来快速的判断两个顶点是否相连。
/**
* 两个顶点是否相连
*/
bool isConnected(int v, int w) {
assert(v >= 0 && v < G.v());
assert(w >= 0 && w < G.v());
return id[v] == id[w];
}
路径规划
思路
外部传入起始点 s
,就以 s 为起始点进行深度优先遍历,如果存在多个连通分量,则只关心当前起始点所在连通分量。增加数组 from
用来记录到达当前顶点的上一个顶点是谁,默认全部为 -1
,起始点一直都是 -1
不会改变,当前连通分量内,经过深度遍历之后,除起始点以外,应都有对应的值。
实现
/**
* 深度遍历求路径
*/
template<typename Graph>
class ComponentPath {
private:
/** 图 */
Graph &G;
/** 在深度遍历时,是否访问过了 */
bool *visited;
/** 源点、起始点 */
int s;
/**
* 当前顶点是从哪个顶点过来的
* 索引为当前顶点,值为当前顶点的上一个顶点
*/
int *from;
/**
* 递归求深度遍历
*/
void dfs(int v) {
// 首先更改成已访问
visited[v] = true;
// 遍历 v 的相邻顶点
typename Graph::AdjIterator adgIter(G, v);
for (int i = adgIter.begin(); !adgIter.end(); i = adgIter.next()) {
if (!visited[i]) {
// 相邻顶点没有被遍历过
// 找到顶点 v 没有被遍历过的相邻顶点,记录路径,相邻顶点是从 v 过来的。
from[i] = v;
dfs(i);
}
}
}
public:
ComponentPath(Graph &graph, int s) : G(graph) {
visited = new bool[G.v()];
from = new int[G.v()];
// 初始化时,所有顶点都没有被访问过。
for (int i = 0; i < G.v(); ++i) {
visited[i] = false;
from[i] = -1;
}
this->s = s;
// 开始深度遍历顶点,源点的 from 为 -1。
dfs(s);
}
~ComponentPath() {
delete[] visited;
delete[] from;
}
/**
* 查看源点 与 w 顶点之间是否存在路径
*
* 如果 w 被遍历过,说明在一个连通分量中,肯定是存在路径的。
*/
bool hasPath(int w) {
assert(w >= 0 && w < G.v());
return visited[w];
}
/**
* 获取源点到 w 顶点的路径
*/
void path(int w, std::vector<int> &vector) {
assert(hasPath(w));
std::stack<int> s;
int p = w;
while (p != -1) {
// 只要 p 不等于 -1,说明还没倒推到源点(源点的 from 是 -1),就 push 到栈中
s.push(p);
p = from[p];
}
vector.clear();
while (!s.empty()) {
vector.push_back(s.top());
s.pop();
}
}
/**
* 打印路径
*/
void showPath(int w) {
assert(hasPath(w));
std::vector<int> vec;
path(w, vec);
for (int i = 0; i < vec.size(); i++) {
std::cout << vec[i];
if (i == vec.size() - 1)
std::cout << std::endl;
else
std::cout << " -> ";
}
}
};
测试
void testPath() {
string filename = "testG2.txt";
SparseGraph g = SparseGraph(7, false);
ReadGraph<SparseGraph> readGraph(g, filename);
g.show();
cout << endl;
ComponentPath<SparseGraph> path(g, 0);
cout << "Path from 0 to 6 : " << endl;
path.showPath(6);
}
// testG2.txt
7 8
0 1
0 2
0 5
0 6
3 4
3 5
4 5
4 6
文章评论