图基本性质,BFS,DFS

78 阅读 0 评论 52 点赞

我是靠谱客的博主沉静枫叶，最近开发中收集的这篇文章主要介绍图基本性质,BFS,DFS，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

图的表示：
图的表示有两种形式：邻接链表表示和邻接矩阵表示。
邻接链表表示：一般用于稀疏图中，空间复杂度为 0（V+E），邻接链表表示法的鲁棒性很高，可以对其进行简单修改来支持许多其他的图变种，同时也很容易的附加各种属性。但是邻接链表却不能很快的判断一条边是否是在图中。
邻接矩阵表示：一般用于稠密图中，特别是在最短路算法中得到应用，空间复杂度为 0（V^2），相比邻接链表空间复杂度却高很多，但是其在判断一条边是否在图中却很方便。

图的搜索：
一、BFS: 0(V+E)
广度优先搜索是最简单的图搜索算法之一，也是许多重要的图算法的原型（Prim的生成树和Dijkstra的单元最短路径算法）。每个节点有一个color属性，标记着其变化，广度优先搜索先将所有的节点都初始化为WHITE。从一个源节点（树根）开始，当一个节点被访问时标记为GRAY，将其入队列（目的就是为了访问其下一层的节点，进而能连贯的访问下去而不会断开。）然后当队列不为空时，出队列一个元素，将这个元素的标记为WHITE的所有邻居都一一标记为GRAY然后入队列重复上述过程，直到栈空为止。之所以被标记，是因为防止生成的广度优先生成树有环。

<span style="font-size:18px;">struct Vertex{
	int color = WHITE;
	elementType data; //顶点关键字
	struct Vertex* parent = NULL;//记录父节点
	int d = 0; //与源点的距离
};
vector<struct Vertex* > G[Maxn];

void BFS(struct Vertex s)// 选取的一个源结点
{
	queue<struct Vertex* > q;
	//进入BFS之前保证某个连通区域中所有的节点是被初始化的。
	s.color = GRAY;
	s.d = 0;
	s.parent = NULL;
	q.push(&s);
	while (!q.empty())
	{
		struct Vertex* u = q.front(); q.pop();
		for (auto &c : G[u->data])
		{
			if (c->color == WHITE)
			{
				c->color = GRAY;
				c->d = u->d + 1;
				c->parent = u;
				q.push(c);
			}
			
		}<span style="font-family: Arial, Helvetica, sans-serif;">color = BLACK;</span><span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">}}</span></span>

BFS的一些性质：（1）在广度优先生成树中当所有的边的权值都为1的时候，从源节s点到节点v的路径就是图中从s到v的“最短路径”。（2）在BFS算法中队列里面最多包含两个不同d值的节点，并且队尾节点vi，与队头节点vj 有 vi.d >= vj,d二、DFS: 0（V+E）深度优先搜索总是对最近出现的结点v的出发边进行搜索，直到该结点的所有出发边搜索完为止。这时“回溯”到该结点的父节点，然后再进行出发边的探索。这个过程一直保持到源节点(树根)的出发边都搜索完为止。这就是建立一棵DFS树的过程。如果在邻接链表中还有没有被搜索的节点，那么就要以这个节点为新的树根继续重复上述。直到将所有的节点都遍历一遍为止。最终形成一棵树或者森林。在搜索过程中，我们对每个节点用color标记，WHITE代表还没被搜索到，GRAY代表已经发现了这个节点，但是对以这个节点为根的树搜索没有完成。BLACK代表以这个节点为根的树已经搜索完了。同时，加入时间戳的概念，每个节点有两个属性，一个是 d 起始遍历这个节点的时间，另一个是f终止遍历这个节点的时间，起始遍历时，此时正好代表着开始遍历其子节点，但是没有遍历完，所以此时color应为GRAY；当终止时间时，代表着以这个节点为根的树已经搜索完毕，开始进军其父亲的下一个出发边，所以此时color应该为BLACK。

<span style="font-size:18px;">struct Vertex{
	int color;//分别在不同时刻赋予不同的值 （WHITE， GRAY， BLACK）
	int distance ;//该结点的深度
	int d;//开始时间戳
	int f;//结束时间戳
    Int id;//为了边与点的统一
	struct Vertex* parent ;//其父节点
	elementType data;//数据域
};
vector<struct Vertex* > G[Maxn];//保存边
struct Vertex* V[Maxn];//保存点
int time; // 时间戳表示为全局变量
void DFS()
{
//进入DFS之前保证某个连通区域中所有的节点是被初始化的。
	time = 0;
	for (auto& v : V)
	{
		if (v->color == WHITE)
		{
			v->distance = 0;
			DFS_VISIT(v);
		}
	}
}
void DFS_VISIT(struct Vertex* u)
{
	time += 1;
	u->d = time;
	u->color = GRAY;
	for (auto& v : G[u->id])
	{
		if (v->color == WHITE)
		{
			v->distance = u->distance + 1;
v.parent = u;
			DFS_VISIT(v);
		}
	}
	time += 1;
	u->f = time;
	u->color = BLACK;
}</span>

深度优先搜索的性质：
（1）提供图结构很高的信息，在DFS搜索的过程实际就是用先序建立一棵树的过程，所以，在递归的调用每一个节点与树的结构一一对应，即一个节点为GRAY那么这个节点的所有子节点都还没有遍历完全。
（2）节点发现的时间与结束的时间具有括号化结构，并且最早开始时间为1的话，最晚结束时间2|V|。如果判断在一棵一棵根节点为u的树中是否包含，根节点为v的子树，则只要u.d<v.d<v.f<u.f，同时也说明了v是u的后代。当v是u的后代时当且仅当在发现u节点的时间u.d，存在一条从结点u到节点v的全部由WHITE标记的路径。等。
（3）对边进行分类。根据时间戳的关系可以分为树边，后向边，前向边，横向边。
树边：(u,v)就是生成深度优先树的边。当且仅当在 u.d<v,d<v,f<u,f情况下，即节点v为WHITE。
后向边：(u,v)v是u的一个祖先(包括u也是u的祖先)。当且仅当在 v.d<=u,d<u.f<=v,f情况下，即节点v为GRAY。
前向边：（u,v）v是u的一个后代。当且仅当在 u.d<v,d<v.f<u,f情况下，即节点v为WHITE。
(和树边一样)
横向边：除上述之外其他类型的边。当且仅当在 v.d<v.f<u.d<u,f情况下。即节点v为BLACK。
注意：在有向图中树边，后向边，前向边，横向边都存在，但是在无向图中只存在树边和后向边。