首页
登录 | 注册

算法导论-第22章-基本的图算法-22.5 强连通分量

转自

#include <iostream>
using namespace std;

//8个点
#define N 8 
#define WHITE 0
#define GRAY 1
#define BLACK 2


//边结点结构
struct Edge
{
    int start;//有向图的起点
    int end;//有向图的终点
    Edge *next;//指向同一个起点的下一条边
    int type;//边的类型
    Edge(int s, int e):start(s),end(e),next(NULL){}
};
//顶点结点结构
struct Vertex
{
    int id;
    Edge *head;//指向以该顶点为起点的下一条边
    int color;//顶点的颜色
    Vertex *p;//指向遍历结果的父结点
    int d, f;//第一次被发现的时间和结束检查的时间
    Vertex( ):head(NULL),color(WHITE),p(NULL),d(0x7fffffff),id(0){}
};
//图结构
struct Graph
{
    Vertex V[N+1];//N个顶点
    Graph()
    {
        int i;
        for(i = 1; i <= N; i++)
            V[i].id=i;
    }
};

int time = 0;
bool flag = 0;//flag为0表示第一次调用DFS,为1表示第二次调用DFS
int Sort[N+1] = {N};//存储按u.f从大到小排序时的点,即sort[1]存储的点的f值最大,sort[N]存储的点的f值最小,按这个点的顺序调用DFS_Visit函数

//插入边,按边的end由小到大排列
void InsertEdge(Graph *G, int start , int end)
{
    Edge *E = new Edge(start,end);
    //如果当前点E->start的链表为空,则把E边作为head
    if(G->V[E->start].head == NULL)
        G->V[E->start].head =E;
    //如果有,加入到链表中,递增顺序排列,便于查重
    else
    {
        //链表的插入
        Edge *e1 = G->V[E->start].head, *e2 = e1;
        while(e1 && e1->end < E->end)
        {
            e2 = e1;
            e1 = e1->next;
        }
        //插入了重复的边,直接返回
        if(e1 && e1->end == E->end)
            return;
        //第一条边的end都比E边的end大, 此时e1 == e2,则把E作为head
        if(e1 == e2)
        {
            E->next = e1;
            G->V[E->start].head =E;
        }
        //找到E的正确位置
        else
        {
            e2->next = E;
            E->next = e1;
        }
    }
}
//转置,重新构造一个图
Graph* Reverse(Graph *G)  
{  
    Graph *ret = new Graph;  
    int i;  
    //遍历图G中的每一条边,以终点为起点,以起点为终点,加入到新图RET中   
    for(i = 1; i <= N; i++)  
    {  
        Edge *E = G->V[i].head;  
        while(E)  
        {   
            InsertEdge(ret, E->end, E->start);  
            E = E->next;  
        }  
    }  
    return ret;  
}
//访问某顶点
void DFS_Visit(Graph *G, Vertex *u)
{
    //在第二次DFS调用时输出
    if(flag)
        cout<<u->id<<' ';
    //将u置为黑色
    u->color = GRAY;
    //使全局变量time增值
    time++;
    //将time的新值记录为发现时间
    u->d = time;
    //检查和u相邻的每个顶点v
    Vertex *v;
    Edge *e = u->head;
    while(e)
    {
        v = &G->V[e->end];
        //如果顶点为白色
        if(v->color == WHITE)
        {
            //递归访问顶点
            v->p = u;
            DFS_Visit(G, v);
            //树边
            e->type = 1;
        }
        else if(v->color == GRAY)
        {
            //反向边
            e->type = 2;
        }
        else if(v->color == BLACK)
        {
            //正向边
            if(u->d < v->d)
                e->type = 3;
            //交叉边
            else
                e->type = 4;
        }
        e = e->next;
    }
    //以u为起点的所有边都被探寻后,置u为黑色
    u->color = BLACK;
    //并将完成时间记录在f[u]中
    time++;
    u->f = time;
    //把结果按照f从大到小的顺序保存于Sort数组中
    if(flag == 0)
    {
        Sort[Sort[0]] = u->id;
        Sort[0]--;
    }
}
//深度优先搜索
void DFS(Graph *G)
{
    int i;
    //对每个顶点初始化
    for(i = 1; i <= N; i++)
    {
        G->V[i].id = i;
        G->V[i].color = WHITE;
        G->V[i].p = NULL;
    }
    //时间戳初始化
    time = 0;
    //依次检索V中的顶点,发现白色顶点时,调用DFS_Visit访问该顶点
    for(i = 1; i <= N; i++)
    {
        int j;
        //第一次是以正常顺序按点1->2->3->.....->8的顺序调用DFS_Visit函数
        if(flag == 0)
            j = i;
        //第二次是以f从大到小的顺序,这个顺序在第一次dfs次保存于Sort数组中
        else 
            j = Sort[i];
        //发现白色顶点时,调用DFS_Visit访问该顶点
        if(G->V[j].color == WHITE)
        {
            if(flag)
                cout<<"强连通分量为:";
            DFS_Visit(G, &G->V[j]);
            //flag == 1时,第二次调用DFS,此时每次调用DFS_Visit 就会输出一个强连通分量,换行后,再调用,又输出一个强连通分量
            if(flag)
                cout<<endl;
        }
    }
}
void Strongly_Connected_Component(Graph *G)
{
    //第一次DFS,计算每个顶点的f
    DFS(G);
    //转置,计算GT   
    Graph *G2 = Reverse(G);  
    //第一次的DFS和第二次的DFS不同,用flag区分
    flag = 1;
    //第二次的DFS,按照f从大到小的顺序调用
    DFS(G2);
}
/*
  1  →2→ 3 ↔ 4
↓↑ ↙↓  ↓  ↓
  5 → 6 ↔ 7 →8

  上面8还要指向自己,共15条边
*/
int main()  
{  
    //构造一个空的图   
    Graph *G = new Graph;   
    //15条边
    int edge[16][2] = {{0,0},{1,2},{1,5},{2,3},{2,5},{2,6},{3,4},{3,7},{4,3},{4,8},{5,1},{5,6},{6,7},{7,6},{7,8},{8,8}};
    for(int i = 1; i <= 15; i++)  
    {       
        int start = edge[i][0];
        int end = edge[i][1];  
        InsertEdge(G, start , end);     
    }  
    //计算强联通分量
    Strongly_Connected_Component(G);
    return 0;  
}  

相关文章

  • 六西格玛设计DFSS在研发管理中是怎么应的
    六西格玛设计DFSS在研发管理中是怎么应用的? 现如今,六西格玛管理的知名度是越来越高了,很多企业为了能够更好的发展,开始选择实施六西格玛管理,并且已经有企业成功的检验推行六西格玛管理会给企业带来显着的成效.那么,六西格玛设计在研发管理中是 ...
  • 深浅拷贝的定义: 浅拷贝只是增加了一个指针指向一个存在的地址, 深拷贝是增加一个指针并且开辟了新的内存,这个增加的指针指向这个新的内存, 采用浅拷贝的情况,释放内存,会释放同一内存,深拷贝就不会出现释放同一内存的错误 一层的情况: impo ...
  • 从虚拟化前端Bug学习分析Kernel Dump
    前言 也许大家都知道,分析 Kernel Dump 有个常用的工具叫 Crash,在我刚开始学习分析 Kernel Dump 的时候,总是花大量的时间折腾这个工具的用法,却总是记不住这个工具的功能.后来有一次在参加某次内部分享的时候,有位大 ...
  • 贾扬清:我对人工智能方向的一点浅见
    阿里妹导读:作为 AI 大神,贾扬清让人印象深刻的可能是他写的AI框架Caffe ,那已经是六年前的事了.经过多年的沉淀,成为"阿里新人"的他,对人工智能又有何看法?最近,贾扬清在阿里内部分享了他的思考与洞察,欢迎共同探 ...
  • 微软发布人工智能教育与学习共建社区
    步入2019,人工智能(Artificial Intelligence)的浪潮依然汹涌,各国对于AI人才的需求进一步加大:2月,美国总统特朗普签署行政命令,正式启动美国人工智能计划:加拿大正通过"全球技能战略签证"吸引国 ...
  • 4折购书福利,再送你畅销新书
    4折购书福利,再送你畅销新书   福利一: 扫描下方小程序选购你心仪的图书吧! 423世界读书日图书每满 100 减 50 结算时输入优惠码:UJ7UW7(实付200再减30) 可与每满 100 减 50 活动叠加使用! 也就是说只要花17 ...

2020 jeepshoe.net webmaster#jeepshoe.net
13 q. 0.262 s.
京ICP备10005923号