数据结构——拓扑排序
本文最后更新于69 天前,其中的信息可能已经过时,如有错误请发送邮件到big_fw@foxmail.com

AOV网:在表示一个工程的有向图的中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网。

设G=(V,E)是一个具有n个顶点的有向图,V中顶点序列V1,V2,…,Vn,满足若从顶点Vi到Vj有一条路径,则在顶点序列中顶点Vi必在顶点Vj之前。则我们称这样的顶点序列为一个拓扑序列。

1.拓扑排序算法思想

对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出,然后删去此顶点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

在拓扑排序中,需要删除顶点,显然用邻接表更加方便,因此我们需要为AOV网建立一个邻接表。考虑到算法过程中始终要查找入度为0的顶点,我们在原来顶点表的结构中,增加一个入度域in。

下面是一张AOV网,我们可以得到下面的邻接表数据结构:

//边表结构 
typedef struct EdgeNode{
	int adjvex;//邻接点域
	int weight;//存储权值
	struct EdgeNode *next; //链域,指向下一个邻接点 
}EdgeNode; 

//顶点表结点 
typedef struct VertexNode {
	int in;//顶点入度
	int data;//顶点域,存储顶点信息
	EdgeNode *firstedge;//边表头指针 
}VertexNode,AdjList[MAXVEX];

typedef struct {
	AdjList adjList;
	int numVertexes;//顶点数
	int numEdges;//边数 
}graphAdjList,*GraphAdjList; 

2.拓扑排序代码实现

#include<iostream>
#include "math.h" 
    
#include "stdlib.h"  
using namespace std;

#define MAXVEX 14
#define MAXEDGE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
//边表结构 
typedef struct EdgeNode{
	int adjvex;//邻接点域
	int weight;//存储权值
	struct EdgeNode *next; //链域,指向下一个邻接点 
}EdgeNode; 

//顶点表结点 
typedef struct VertexNode {
	int in;//顶点入度
	int data;//顶点域,存储顶点信息
	EdgeNode *firstedge;//边表头指针 
}VertexNode,AdjList[MAXVEX];

typedef struct {
	AdjList adjList;
	int numVertexes;//顶点数
	int numEdges;//边数 
}graphAdjList,*GraphAdjList; 


//邻接矩阵结构
typedef struct
{
	int vexs[MAXVEX];
	int arc[MAXVEX][MAXVEX];
	int numVertexes, numEdges;
}MGraph;

void CreateMGraph(MGraph *G)
{
	int i, j;
	
	G->numEdges=MAXEDGE;
	G->numVertexes=MAXVEX;

	for (i = 0; i < G->numVertexes; i++)
	{
		G->vexs[i]=i;
	}

	for (i = 0; i < G->numVertexes; i++)
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			G->arc[i][j]=0;
		}
	}

	G->arc[0][4]=1;
	G->arc[0][5]=1; 
	G->arc[0][11]=1; 
	G->arc[1][2]=1; 
	G->arc[1][4]=1; 
	G->arc[1][8]=1; 
	G->arc[2][5]=1; 
	G->arc[2][6]=1;
	G->arc[2][9]=1;
	G->arc[3][2]=1; 
	G->arc[3][13]=1;
	G->arc[4][7]=1;
	G->arc[5][8]=1;
	G->arc[5][12]=1; 
	G->arc[6][5]=1; 
	G->arc[8][7]=1;
	G->arc[9][10]=1;
	G->arc[9][11]=1;
	G->arc[10][13]=1;
	G->arc[12][9]=1;

}

/* 利用邻接矩阵构建邻接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{
	int i,j;
	EdgeNode *e;

	*GL = (GraphAdjList)malloc(sizeof(graphAdjList));

	(*GL)->numVertexes=G.numVertexes;
	(*GL)->numEdges=G.numEdges;
	for(i= 0;i <G.numVertexes;i++) /* 读入顶点信息,建立顶点表 */
	{
		(*GL)->adjList[i].in=0;
		(*GL)->adjList[i].data=G.vexs[i];
		(*GL)->adjList[i].firstedge=NULL; 	/* 将边表置为空表 */
	}
	
	for(i=0;i<G.numVertexes;i++) /* 建立边表 */
	{ 
		for(j=0;j<G.numVertexes;j++)
		{
			if (G.arc[i][j]==1)
			{
				e=(EdgeNode *)malloc(sizeof(EdgeNode));
				e->adjvex=j;					/* 邻接序号为j  */                        
				e->next=(*GL)->adjList[i].firstedge;	/* 将当前顶点上的指向的结点指针赋值给e */
				(*GL)->adjList[i].firstedge=e;		/* 将当前顶点的指针指向e  */  
				(*GL)->adjList[j].in++;
				
			}
		}
	}
	
}

//拓扑排序 
int TopologicalSort(GraphAdjList GL){
EdgeNode *e;    
	int i,k,gettop;   
	int top=0;  /* 用于栈指针下标  */
	int count=0;/* 用于统计输出顶点的个数  */    
	int *stack;	/* 建栈将入度为0的顶点入栈  */   
	stack=(int *)malloc(GL->numVertexes * sizeof(int) );    

	for(i = 0; i<GL->numVertexes; i++)                
		if(0 == GL->adjList[i].in) /* 将入度为0的顶点入栈 */         
			stack[++top]=i;    
	while(top!=0)    
	{        
		gettop=stack[top--];        
		cout<<GL->adjList[gettop].data<<" -> ";    
		count++;        /* 输出i号顶点,并计数 */        
		for(e = GL->adjList[gettop].firstedge; e; e = e->next)        
		{            
			k=e->adjvex;            
			if( !(--GL->adjList[k].in) )  /* 将i号顶点的邻接点的入度减1,如果减1后为0,则入栈 */                
				stack[++top]=k;        
		}
	}   
	cout<<endl; 
	if(count < GL->numVertexes)        
		return ERROR;    
	else       
		return OK;
} 

int main(void)
{    
	MGraph G;  
	GraphAdjList GL; 
	int result;   
	CreateMGraph(&G);
	CreateALGraph(G,&GL);
	result=TopologicalSort(GL);
	cout<<"result:"<<result<<endl; 

	return 0;
}
如果觉得本文对您有所帮助,可以支持下博主,一分也是缘
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇