數據結構之---C語言實現拓撲排序AOV圖

數據結構之---C語言實現拓撲排序AOV圖

//有向圖的拓撲排序
//楊鑫
#include 
#include 
#include 
#define MAX_NAME 3
#define MAX_VERTEX_NUM 20
typedef int InfoType;					//存放網的權值
typedef char VertexType[MAX_NAME];		//字符串類型
typedef enum{DG, DN, AG, AN}GraphKind;	//{有向圖，有向網，無向圖，無向網}
//圖的鄰接表存儲
typedef struct ArcNode
{
	int adjvex;							//該弧所指向的頂點的位置	
	struct ArcNode *nextarc;			//指向嚇一條的指針
	InfoType *info;						//網的權值指針
}ArcNode;

typedef struct VNode
{
	VertexType data;					//頂點信息
	ArcNode *firstarc;					//第一個表結點的地址，指向第一條依附該頂點的弧的指針
}VNode, AdjList[MAX_VERTEX_NUM];		//頭結點

typedef struct
{
		AdjList vertices;	
		int vexnum, arcnum;				//圖的當前頂點數和弧數
		int kind;						//圖的種類標志
}ALGraph;

//若G中存在頂點u，則返回該頂點在圖中的位置，都則返回-1
int LocateVex(ALGraph G, VertexType u)
{
	int i;
	for(i = 0; i < G.vexnum; ++i)
	{
		if(strcmp(u, G.vertices[i].data) == 0)
				return i;
		return -1;
	}
}

//采用鄰接表存儲結構，構造沒有相關信息的圖G(用一個函數構造4種圖)
int CreateGraph(ALGraph *G)
{
	int i, j, k;
	int w;							//權值
	VertexType va, vb;
	ArcNode *p;
	printf(請輸入圖的類型（有向圖：0，有向網：1，無向圖：2，無向網：3）:);
	scanf(%d, &(*G).kind);
	printf(請輸入圖的頂點數和邊數:(以空格間隔)： 
);
	scanf(%d%d, &(*G).vexnum, &(*G).arcnum);
	printf(請輸入%d個頂點的值(小於%d個字符):
, (*G).vexnum, MAX_NAME);
	for(i = 0; i < (*G).vexnum; ++i)                //構造頂點向量
	{
		scanf(%s, (*G).vertices[i].data);
		(*G).vertices[i].firstarc = NULL;
	}
	if((*G).kind == 1 || (*G).kind == 3)		//網
	{
		printf(請順序輸入每條弧（邊）的權值,弧尾和弧頭（以空格作為間隔）:
);
	}
	else											//圖
	{
		printf(請順序輸入每條弧（邊）的弧尾和弧頭（以空格作為間隔）:
);
	}
	for(k = 0; k < (*G).arcnum; ++k)
	{
		if((*G).kind == 1 || (*G).kind == 3)
				scanf(%d%s%s, &w, va, vb);
		else
				scanf(%s%s, va, vb);
		i = LocateVex(*G, va);					//弧尾
		j = LocateVex(*G, vb);					//弧頭
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = j;
		if((*G).kind == 1 || (*G).kind == 3)
		{
			p->info = (int *)malloc(sizeof(int));
			*(p->info) = w;
		}
		else
		{
			p->info = NULL;
		}
		p->nextarc = (*G).vertices[i].firstarc;                 //插在表頭
		(*G).vertices[i].firstarc = p;
		if((*G).kind >= 2)										//無向圖或網，產生第二個表結點
		{
			p = (ArcNode*)malloc(sizeof(ArcNode));
			p->adjvex = i;
			if((*G).kind == 3)
			{
				p->info = (int*)malloc(sizeof(int));
				*(p->info) = w;
			}
			else
			{
				p->info = NULL;
			}
			p->nextarc = (*G).vertices[j].firstarc;               //插在表頭
			(*G).vertices[j].firstarc = p;     
		}
	}
	return 1;
}

//輸出圖的鄰接表G
void Display(ALGraph G)
{
	int i;
	ArcNode *p;
	switch(G.kind)
	{
		case DG:
				printf(有向圖
);
				break;
		case DN:
				printf(有向網
);
				break;
		case AG:
				printf(無向圖
);
				break;
		case AN:
				printf(無向網
);
	}
	printf(%d 個頂點: 
, G.vexnum);
	for(i = 0; i < G.vexnum; ++i)
	{
		printf(%s , G.vertices[i].data);
	}
	printf(
%d條弧（邊）:
, G.arcnum);
	for(i = 0; i < G.vexnum; i++)
	{
		p = G.vertices[i].firstarc;
		while(p)
		{
			if(G.kind <= 1)
			{
				printf(%s->%s, G.vertices[i].data, G.vertices[p->adjvex].data);
				if(G.kind == DN)
						printf(:%d , *(p->info));
			}
			else
			{
				if(i < p->adjvex)
				{
					printf(%s--%s, G.vertices[i].data, G.vertices[p->adjvex].data);
					if(G.kind == AN)
						printf(:%d , *(p->info));
				}
			}
			p = p->nextarc;

		}
		printf(
);
	}
}


//求頂點的入度
void FindInDegree(ALGraph G, int indegree[])
{
	int i;
	ArcNode *p;
	//賦初值
	for(i = 0; i < G.vexnum; i++)
	{
		indegree[i] = 0;
	}
	for(i = 0; i < G.vexnum; i++)
	{
		p = G.vertices[i].firstarc;
		while(p)
		{
			indegree[p->adjvex]++;
			p = p->nextarc;
		}
	
	}

}

//棧類型
typedef int SElemType;
#define STACK_INIT_SIZE 10										//存儲空間初始分配量
#define STACKINCREMENT 2										//存儲空間分配增量

//棧的順序存儲結構表示
typedef struct SqStack
{
	SElemType *base;						//基地址
	SElemType *top;							//棧頂指針
	int stacksize;							//當前已經分配的存儲空間
}SqStack;                                              

//構造一個空棧
int InitStack(SqStack *S)
{
	//為棧底分分配一個指定大小的存儲空間
	(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!(*S).base)
			exit(0);						
	(*S).top = (*S).base;					//棧底與棧頂指針相同
	(*S).stacksize = STACK_INIT_SIZE;	
	return 1;
}



//若棧S為空棧（棧底指針和棧頂指針相同）, 則返回1，否則返回0
int StackEmpty(SqStack S)
{
	if(S.top == S.base)
			return 1;
	else
			return 0;
}


//插入元素e為新的棧頂元素
int Push(SqStack *S, SElemType e)
{
	if((*S).top - (*S).base >= (*S).stacksize)
	{
		(*S).base = (SElemType *)realloc((*S).base,((*S).stacksize + STACKINCREMENT)*sizeof(SElemType));
		if(!(*S).base)
				exit(0);
		(*S).top = (*S).base + (*S).stacksize;
	   	(*S).stacksize += STACKINCREMENT;	
	}
	*((*S).top)++= e;
	return 1;
}




//若棧不為空，則刪除S棧頂元素用e返回其值，並返回1，否則返回0
int Pop(SqStack *S, SElemType *e)
{
	if((*S).top == (*S).base)
	{
		return 0;
	}
	*e = *--(*S).top;
	return 1;
}


//有向圖的G采用鄰接表存儲結構，若G無回路，則輸出G的頂點的一個拓撲結構
int TopologicalSort(ALGraph G)
{
	int i, k, count, indegree[MAX_VERTEX_NUM];
	SqStack S;
	ArcNode *p;
	FindInDegree(G, indegree);
	InitStack(&S);
	for(i = 0; i < G.vexnum; ++i)
	{
		if(!indegree[i])
				Push(&S, i);
		count = 0;
		//棧不空
		while(!StackEmpty(S))
		{
			Pop(&S, &i);
			printf(%s, G.vertices[i].data);			//輸出i號頂點並計數
			++count;
			//對i號頂點的每個鄰接點的入度減1
			for(p == G.vertices[i].firstarc; p; p = p->nextarc)
			{
				k = p->adjvex;
				if(!(--indegree[k]))			//若入度減為0，則入棧
						Push(&S, k);
			}
		}
		if(count < G.vexnum)
		{
				printf(此有向圖有回路
);
				return 0;
		}
		else
		{
			printf(為一個拓撲序列!!
);
		}
	}
}

int main()
{
	ALGraph f;
	printf(請選擇有向圖
);
	CreateGraph(&f);
	Display(f);
	TopologicalSort(f);
	return 0;
}

結果：