图论-拓扑排序与欧拉回路

BFS:

一、   图的宽度优先(Breadth-First)遍历:

 

（1）算法描述

 

 

时间复杂度分析

l   每一个顶点被访问一次

l   每条边被访问两次---无向图每条边出现在两个链表中

O(|V| + |E|)

O(|V|2) 对 稠密图  |E| ~ |V|2

     O(|V|)  对 稀疏图  |E| ~ |V|

 

注意：访问时间：search_time

 

（2）应用举例---拓扑排序

 

定义：

在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。

把AOV网络（用定点表示活动，用弧表示活动间优先关系的有向图）中各个顶点按照它们互相之间的优先关系排列成一个线性序列的过程叫做拓扑排序。

 

C1—c2—c3—c4—c5—c7—c8

C1—c4—c2—c3—c8—c5—c7

…

 

拓扑序列并不唯一!

 

【算法讨论】

DFS:

一、   图的深度优先(Depth-First)遍历:

（1）算法描述

 

时间复杂度分析

l   每一个顶点被访问一次

l   每条边被访问两次---无向图每条边出现在两个链表中

O(|V| + |E|)

O(|V|2) 对 稠密图  |E| ~ |V|2

     O(|V|)  对 稀疏图  |E| ~ |V|

 

注意：访问时间：search_time

      爆栈问题

（2）应用举例—欧拉路（一笔画）问题

定义：

欧拉路或欧拉回路问题，就是有一条路径（或回路）由所有边构成，且每边只用一次。也称为一笔画问题，即连续的一次画出图的所有边，经过每条边一次且仅一次。

 

 

结论1 ：无向图存在欧拉回路的充要条件是：

q  图是连通的。

q  图中所有点的度均为偶数。

结论2：无向图欧拉路存在的充要条件：

q  图是连通的。

q  图中有且仅有2个度数为奇数的点，并且这两个点一定是这条欧拉路的起点和终点。

 

 

证明

q  “勇往直前”

q  “圈套圈”

q  把欧拉回路构造出来

 

结论3：有向图G，存在欧拉回路的充要条件是：

q  基图（原有向边改为无向边后所得的无向图）连通

q  所有点的出度和入度相同

结论4：有向图G，存在欧拉路的充要条件是：

q  基图连通

q  有且仅有一个点入度比出度大1，且这个点是欧拉路的终点

q  有且仅有一个点入度比出度小1，且这个点是欧拉路的起点

q  其他所有的点入度和出度相等

 

 

有向图的递归程序

void euler(int v) {            
 for (int i=head[v]; i!=0; i=edge[i].next) {

        if(edge[i].vis==0){

edge[i].vis=1;

euler(edge[i].v);

}

    }

cout << v << " ";  //回溯时输出

}

 

非递归程序框架

void euler(int v) {            
 int i=0;
 que [ 0 ] = v;
 while ( que.size() > 0 ) {
   v = que.top() ;
   if ( get_next(v,i) )  {    //取v的相邻边(v,i)

           g[v][i]  = 0;

        //g[i][v]  = 0;  //根据情况
       que.push(i);          //访问点进栈
     } else 
       ans[ ansI++ ] = que.pop();  //出栈，放入答案队列

      }

}

 

有向图的邻接矩阵递归程序

void euler(int x){//打印以x为起点的欧拉回路或通路     for(int y=1;y<=n;y++){         if(vis[x][y]||vis[y][x]){             vis[x][y]=0;//去掉x-y这条边             vis[y][x]=0;//去掉y-x这条边             euler(y);         }     }     //逆序打印欧拉回路     printf("%d ",x); }