本文主要是对图的一些基本算法进行总结,涉及的算法有:广度优先搜索(BFS)、深度优先搜索(DFS)、拓扑排序、强连通分量(Kosaraju、Tarjan)以及欧拉回路等问题。
广度优先搜索(BFS):BFS的特点是其搜索过的节点形成一颗广度优先树,每个节点到这棵树的根节点的距离叫做深度。BFS搜到的路径是最短路径,这里的最短路径是指经历的节点数目。BFS算法一般会用到队列作为节点的存储结构,其实现的时间复杂度为O(V+E)。其代码为:
-
void Graphic::breadth_first_search(void){
-
std::list<size_t> queue;
-
for(size_t i=0;i<vertex_num;++i){
-
if(WHITE != root[i].color)
-
continue;
-
queue.push_front(root[i].number);
-
root[i].color = GRAY;
-
while(!queue.empty()){
-
vertex* tmp = root[queue.back()].next;
-
while(NULL != tmp){
-
if(root[tmp->number].color == WHITE){
-
root[tmp->number].color = GRAY;
-
root[tmp->number].parent = &root[queue.back()];
-
tmp->var .depth = root[queue.back()].var.depth + 1;
-
queue.push_front(tmp->number);
-
}
-
tmp = tmp->next;
-
}
-
root[queue.back()].color = BLACK;
-
BFS_result.push_back(queue.back());
-
queue.pop_back();
-
}
-
}
-
}
注:在我们的算法中,图的存储方式为邻接矩阵表。
深度优先遍历(DFS):DFS有两个主要特点,即:深度优先搜索形成的不再是一棵树,而是深度优先森林、节点的发现时间和完成时间具有括号性。之所以形成优先森林,是因为在进行深度优先遍历时,到达某个节点的源节点不唯一。具有括号性是指:如果开始搜索记为“(”,结束搜索记为“)”,则左右的括号都适当的嵌套在一起。通过括号性,我们可以更好的理解深度优先遍历的过程。利用这两个特性,DFS有很多应用,例如:判断图中是否有环、拓扑排序等的。下面是DFS的代码:
-
void Graphic::depth_first_search(){
-
for(size_t i=0;i<vertex_num;++i){
-
if(WHITE == root[i].color)
-
DFS(i);
-
}
-
}
-
Graphic::DFS(size_t num){
-
DFS_result.push_back(num);
-
root[num].color = GRAY;
-
Graphic::time += 1;
-
root[num].var.time[0] = (unsigned short)Graphic::time;
-
vertex *tmp = root[num].next;
-
while(0 != tmp){
-
if(root[tmp->number].color == WHITE){
-
root[tmp->number].parent = &root[num];
-
DFS(tmp->number);
-
}
-
tmp = tmp->next;
-
}
-
root[num].color = BLACK;
-
Graphic::time += 1;
-
root[num].var.time[1] = (unsigned short)Graphic::time;
-
}
拓扑排序:拓扑排序就是将有向图中节点间的关系转化为线性关系。拓扑排序可以用于查看图中是否存在环,如果存在环则无法进行拓扑排序。但是,在下面的程序中,我们假设图中不存在环。对于无向图来说,因为节点间的关系是对称的,所以节点不能进行拓扑排序。拓扑排序其实很简单,其过程如下:每次从节点集合中选出一个节点A,且A的入度为0,然后修改以A为使点的节点的入度,按上述过程依次进行,直到节点集合为空或者不存在拓扑排序为止。这个过程可以通过DFS的括号性来表示,即:拓扑排序就是将节点按着完成时间进行降序排序。代码如下:
-
std::list<size_t> Graphic::topological_sort(void){
-
depth_first_search();
-
std::map<size_t,size_t> rst_map;
-
for(size_t i=0;i<vertex_num;++i){
-
rst_map.insert(std::make_pair(root[i].var.time[1],root[i].number));
-
}
-
std::list<size_t>rst_list;
-
for(std::map<size_t,size_t>::const_iterator iter = rst_map.begin();
-
iter != rst_map.end();++iter){
-
rst_list.push_front(iter->second);
-
}
-
}
强连通分量:强连通分量是指,在有向图中任意两点之间都存在连通边,即:如果u、v在同一个强连通分量红,则(u,v)(v,u)都存在。这个我们同样可以通过DFS进行求解。求解强连通分量的方法很多,常用的有三种:Kosaraju、Tarjan和Gabow。下面简要介绍着三种算法,然后给出相应代码。
Kosaraju:1)对原图进行DFS,2)求解原图的转置,3)按着1)中DFS完成时间的递减次序对2)中的转置图进行DFS,每生成一颗深度优先树就求到了一个强连通分支。具体证明见算法导论(证明的关键在于连通分支不存在环)。代码如下:
-
Graphic Graphic::transposed_graphic(){
-
Graphic rst(edage_num,vertex_num);
-
for(size_t i=0;i<rst.vertex_num;++i){
-
vertex *tmp = root[i].next;
-
while(NULL != tmp){
-
size_t num = tmp->number;
-
vertex *tmp_node = new vertex;
-
tmp_node->number = i;
-
tmp_node->next = rst.root[num].next;
-
rst.root[num].next = tmp_node;
-
tmp = tmp->next;
-
}
-
}
-
return rst;
-
}
-
std::list<size_t> Graphic::calculate_cycle_path(const std::list<std::list<size_t> > cycle){
-
std::list<size_t> rst_list;
-
for(size_t i=0;i<vertex_num;++i){
-
bool mark = true;
-
if(BLACK == root[i].color){
-
for(std::list<std::list<size_t> >::const_iterator iter = cycle.begin();
-
iter != cycle.end();++iter){
-
if(find(iter->begin(),iter->end(),i) != iter->end()){
-
mark = false;
-
break;
-
}
-
}
-
if (mark)
-
rst_list.push_back(i);
-
}
-
}
-
return rst_list;
-
}
-
void Graphic::SCC_Kosaraju(void){
-
depth_first_search();
-
Graphic tran_root = transposed_graphic();
-
std::list<size_t>rst_list = node_sort_by_out_time();
-
std::list<size_t>::const_iterator iter = rst_list.begin();
-
std::list<std::list<size_t> > cycle;
-
while(iter != rst_list.end()){
-
tran_root.DFS(*iter++);
-
std::list<size_t> tmp = tran_root.calculate_cycle_path(cycle);
-
if(!tmp.empty())
-
cycle.push_front(tmp);
-
}
-
}
Tarjan:1)在节点第一次被访问时将其压入栈;2)遇到已在栈中的元素时,记录此节点,并进行出栈操作,直到找到记录的节点为止,此为一个连通分量。代码如下;
-
std::list<std::list<size_t> > Graphic::Tarjan_DFS(size_t *DFN, size_t *low,size_t num){
-
static std::list<std::list<size_t> > rst;
-
static std::list<size_t> stck;
-
static size_t index = 0;
-
-
DFN[num] = low[num] = index++;
-
stck.push_back(num);
-
root[num].color = GRAY;
-
-
vertex *tmp = root[num].next;
-
while(0 != tmp){
-
size_t tmp_num = tmp->number;
-
if(root[tmp_num].color == WHITE){
-
Tarjan_DFS(DFN,low,tmp_num);
-
low[num] = std::min(low[num],low[tmp_num]);
-
}
-
else if(root[tmp_num].color == GRAY){
-
low[num] = std::min(low[num],DFN[tmp_num]);
-
}
-
tmp = tmp->next;
-
}
-
-
std::list<size_t> t;
-
size_t t_num;
-
-
if(low[num] == DFN[num]){
-
do{
-
t_num = stck.back();
-
t.push_front(t_num);
-
stck.pop_back();
-
root[t_num].color = BLACK;
-
}while(t_num != num && !stck.empty());
-
}
-
-
if(!t.empty())
-
rst.push_front(t);
-
return rst;
-
}
-
void Graphic::SCC_Tarjan(void){
-
size_t *low = new size_t [vertex_num];
-
size_t *DFN = new size_t [vertex_num];
-
std::list<std::list<size_t> > rst;
-
-
for(size_t i=0;i<vertex_num;++i){
-
if(WHITE == root[i].color){
-
rst = Tarjan_DFS(DFN,low,i);
-
}
-
}
-
delete [] low;
-
delete [] DFN;
-
-
}
欧拉回路:欧拉回路就是通过G的每条边仅一次,但可以访问每个节点多次。我们看到欧拉回路就是强连通分量的一个子集,只是在强连通分量上加了一个限制条件,即:强连通分量中的每个节点的入度和出度必须相同(具体证明就不说啦)。其实,欧拉回路也就是一笔画的问题。我们仅需按着上述算法求出强连通分量,然后判断其中节点的入度是否等于出度即可,代码就省略了:)。
下面是,本文代码的一个整体框架,也就是一个类,只给出了类的大方法和上面没有实现的代码,如下:
-
enum node_color{WHITE,GRAY,BLACK};
-
struct vertex{
-
size_t number;
-
vertex *parent,*next;
-
node_color color;
-
union{
-
size_t depth;
-
//enter_time,out_time;
-
unsigned short time[2];
-
}var;
-
};
-
-
class Graphic{
-
public:
-
Graphic(size_t e_num,size_t v_num,std::list<std::pair<size_t,size_t> >edges)
-
:edage_num(e_num),vertex_num(v_num),root(0){
-
root = new vertex[vertex_num];
-
init_vertex();
-
init_edge(edges);
-
}
-
Graphic(size_t e_num,size_t v_num)
-
:edage_num(e_num),vertex_num(v_num),root(0){
-
root = new vertex[vertex_num];
-
init_vertex();
-
}
-
Graphic(){}
-
~Graphic(){
-
if(0 != root)
-
delete [] root;
-
}
-
private:
-
void init_vertex(void);
-
void init_edge(const std::list<std::pair<size_t,size_t> > &edges);
-
public:
-
void breadth_first_search(void);
-
void depth_first_search(void);
-
public:
-
std::list<size_t> topological_sort(void);
-
void SCC_Kosaraju(void);
-
void SCC_Tarjan(void);
-
private:
-
void DFS(size_t num);
-
std::list<std::list<size_t> > Tarjan_DFS(size_t *DFN, size_t *low,size_t num);
-
Graphic transposed_graphic(void);
-
std::list<size_t> node_sort_by_out_time();
-
std::list<size_t> calculate_cycle_path(const std::list<std::list<size_t> > cycle);
-
private:
-
std::vector<size_t> BFS_result;
-
std::vector<size_t> DFS_result;
-
private:
-
vertex *root;
-
vertex tran_root;
-
size_t edage_num;
-
size_t vertex_num;
-
static size_t time;
-
};
-
size_t Graphic::time = 0;
-
void Graphic::init_vertex(void){
-
for(size_t i=0;i<vertex_num;++i){
-
root[i].parent = 0;
-
root[i].number = i;
-
root[i].next = 0;
-
root[i].color = WHITE;
-
root[i].var.depth = 0;
-
}
-
}
-
-
void Graphic::init_edge(const std::list<std::pair<size_t,size_t> > &edges){
-
for(std::list<std::pair<size_t,size_t> >::const_iterator iter = edges.begin();
-
iter != edges.end();++iter){
-
vertex *tmp_vertex = new vertex;
-
tmp_vertex->next = root[iter->first].next;
-
tmp_vertex->number = iter->second;
-
root[iter->first].next = tmp_vertex;
-
}
-
}
本文出自:http://blog.chinaunix.net/uid/28311809/abstract/1.html
阅读(466) | 评论(0) | 转发(0) |