【算法】设计算法求所有强连通分量的完整代码（kosaraju算法）

亦凉 2022-10-13 05:10 183阅读 0赞

代码：

typedef struct anode { 
        int adjvex;//该边的邻接点编号
        struct anode* nexarc;//指向下一条边的指针
        int weight;//该边的相关信息，比如权值
    }arcnode;//边结点类型
    typedef struct vnode { 
        //InfoTyoe info; 顶点的其他信息
        arcnode* firstarc;//指向第一个边结点
    }Vnode;//邻接表头结点类型
    typedef struct { 
        vnode adjlist[10000];//邻接表头结点数组
        int n, e;//图中顶点数n和边数e
    }adjgraph;//完整的图邻接表类型
    #define INF 1e6; 
    #define maxn 1000; 
    int visited[maxn];
    stack<int>st;//全局栈，存放逆拓扑序列
    void create(adjgraph*g,int A[8][8],int n,int e)
    { 
    	g->e = e;
    	g->n = n;
    	arcnode*q;
    	for(int i = 0;i < n;i++)
    	for(int j = 0;j < n;j++)
    	{ 
    		if(A[i][j] != INF && i != j)
    		{ 
    			g->adjlist[i].firstarc->weight = A[i][j];
    q = (arcnode*)malloc(sizeof(arcnode));
    q->adjvex = j;
    q->nexarc = g->adjlist[i].firstarc;//头插法
    g->adjlist[i].firstarc = q;
    
    
    		}
    	}
    }
    void createReAdj(adjgraph*g,adjgraph*g2){ 
    	//产生逆邻接表
    	arcnode*q,*p;
    	int i,w;
    
    	g2 = (adjgraph*)malloc(sizeof(adjgraph));
    	g2->n = g->n;
    	for(int i = 0;i < g->n;i++)
    	g2->adjlist[i].firstarc = NULL;
    		for(int i = 0;i < g->n;i++)
    		{ 
    			p = g->adjlist[i].firstarc;
    			while (p != NULL)
    			{ 
    			w = p->adjvex;//如果原图存在（i,w)
    			q = (arcnode*)malloc(sizeof(arcnode));
    			q->adjvex = i;
    			q->weight = p->weight;
    			q->nexarc = g2->adjlist[w].firstarc;
    			g2->adjlist[w].firstarc = q;//生成一条（w,i)边
    			
    		p = p->nexarc;
    			}
    	
    		}
    }
    //深度递归1 产生一个逆拓扑序列
    void dfs1(adjgraph*g, int u)
    { 
    	visited[u] = 1;
    	//从u出发深度搜索
    	arcnode* q;
    	q = g->adjlist[u].firstarc;//指向u的第一个邻接点
    
    while(q){ 
    	int num = q->adjvex;
    		if(visited[num]!=1)
    		dfs1(g,num);
    	q = q->nexarc;//指向下一个邻接点
    		
    	
    	}
    	st.push(u);//最后一步才将u入栈
    
    }
    //深度递归2 用于求一个强连通分量 ，其中一个数组component即一个强连通分量
    void dfs2(adjgraph* g,int v,vector<int>&component)
    { 
    	int w;
    	arcnode*p;
    	visited[v] = 1;
    	p = g->adjlist[v].firstarc;
    		component.push_back(num);
    			st.pop();//每次递归都出栈中的一个元素，直到最后栈为空
    	while(p)
    	{ 
    		int num = p->adjvex;
    	
    		if(!visited[num])
    		{ 
    		
    		dfs2(g,num,component);
    		}
    		p = p->nexarc;
    	}
    }
    void Kosaraju(adjgraph*g)
    { 
    	//求g的强连通分量
    	adjgraph*g1;
    	vector<int>com;
    	memset(visited,0,sizof(visited));
    	for(int i = 0;i < g->n;i++)
    	if(st.size() != g->n)//当st中元素个数小于顶点数目时
    	dfs1(g,i);//第一步首先递归产生逆拓扑序列
    	memset(visited,0,sizeof(visited));//再次恢复visited为未访问
    	createReAdj(g,g1);//产生逆邻接表
    	while(!st.empty())
    	{ 
    		//栈不空时循环
    		int top1 = st.top();//取栈顶
    		com.clear();//每次都清空vector数组
    		print("顶点%d的强连通分量",top1);
    		dfs2(g,top,com);
    		for(int i = 0;i < com.size();i++)
    		cout<<com[i]<<" ";//输出一个强连通分量
    		cout<<endl;
    	}
    	detroy(g1);//销毁g1
    }