拓?fù)渑判?/span>。任意給定一個有向圖，設(shè)計(jì)一個算法，對它進(jìn)行拓?fù)渑判颉Ｍ負(fù)渑判蛩惴ㄋ枷耄篴.在有向圖中任選一個沒有前趨的頂點(diǎn)輸出；b.從圖中刪除該頂點(diǎn)和所有以它為尾的弧；c.重復(fù)上述a、b，直到全部頂點(diǎn)都已輸出，此時，頂點(diǎn)輸出序列即為一個拓樸有序序列；或者直到圖中沒有無前趨的頂點(diǎn)為止，此情形表明有向圖中存在環(huán)。?

拓?fù)渑判蛩惴ㄋ枷耄?/p>

1. 在有向圖中任選一個沒有前趨的頂點(diǎn)輸出；
2. 從圖中刪除該頂點(diǎn)和所有以它為尾的?。?/li>
3. 重復(fù)上述1、2、直到全部頂點(diǎn)都已輸出，此時，頂點(diǎn)輸出序列即為一個拓樸有序序列；或者直到圖中沒有無前趨的頂點(diǎn)為止，此情形表明有向圖中存在環(huán)。

拓?fù)渑判?/span>算法偽代碼如下：?

1. 棧S初始化；累加器count初始化；

2. 掃描頂點(diǎn)表，將沒有前驅(qū)（即入度為0）的頂點(diǎn)壓棧；

3. 當(dāng)棧S非空時循環(huán)

????3.1 vj=退出棧頂元素；輸出vj；累加器加1；

3.2 將頂點(diǎn)vj的各個鄰接點(diǎn)的入度減1；

3.3 將新的入度為0的頂點(diǎn)入棧；

4. if (count<vertexNum)?輸出有回路信息；

代碼如下：

#include <stdio.h>
#include <stdlib.h>
#define MAXV 100
#define INF 10000

typedef struct
{
	int data[MAXV];
	int top;
}SqStack;

typedef struct ANode
{
	int adjvex;
	struct ANode *nextarc;
	int weight;
}ArcNode;

typedef struct
{
	int adjvex;
	int count;
	ArcNode *firstarc;

}VNode;

typedef struct
{
	VNode adjlist[MAXV];
	int n,e;
}AdjGraph;

void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e)
{
	int i,j;
	ArcNode *p;
	G=(AdjGraph*)malloc(sizeof(AdjGraph));
	for(i=0;i<n;i++)
    G->adjlist[i].firstarc=NULL;
	for(i=0;i<n;i++) 
	    for(j=n-1;j>=0;j--)
	    if(A[i][j]!=0&&A[i][j]!=INF)
		{
			p=(ArcNode*)malloc(sizeof(ArcNode));
			p->adjvex =j;
			p->weight =A[i][j];
			p->nextarc=G->adjlist[i].firstarc;
			G->adjlist[i].firstarc =p;  
		 } 
		 G->n =n;
		 G->e =e;
 } 

void DispAdj(AdjGraph *G)
 {
 	int i;
 	ArcNode *p;
 	for(i=0;i<G->n ;i++)
 	{
 		p=G->adjlist[i].firstarc;
 		printf("%3d:",i);
 		while(p!=NULL)
 		{
 			printf("%3d[%d]->",p->adjvex,p->weight);
 			p=p->nextarc ;
		 }
		 printf("^\n");
	 }
 }
 
void DestoryAdj(AdjGraph *&G)
{
	int i;ArcNode *pre,*p;
	for(i=0;i<G->n ;i++)
	{
		pre=G->adjlist [i].firstarc;
		if(pre!=NULL)
		{
			p=pre->nextarc ;
			while(p!=NULL)
			{
					free(pre);
					pre=p;
					p=p->nextarc ;
				}
				free(pre);
			}
		}
		free(G);
		
	
}

void InitStack (SqStack *&s)
{
	s=(SqStack *)malloc(sizeof(SqStack));
	s->top =-1;
}

void DestoryStack(SqStack *&s)
{
	free(s);
}

void TopSort(AdjGraph *G)
{
	int i,j,flag=0;
	int a[MAXV];
	int St[MAXV],top=-1;
	ArcNode *p;
	for(i=0;i<G->n;i++)
	G->adjlist [i].count =0;
	for(i=0;i<G->n;i++)
	{
		p=G->adjlist [i].firstarc;
		while(p!=NULL)
		{
			G->adjlist [p->adjvex ].count++;
			p=p->nextarc ;
		}
	}
	for(i=0;i<G->n;i++)
	{
		if(G->adjlist [i].count==0)
		{
			top++;
			St[top]=i;
		}
	} 
	while(top>-1)
	{
		i=St[top];
		top--;
		a[flag++]=i;
		p=G->adjlist [i].firstarc;
		while(p!=NULL)
		{
			j=p->adjvex;
			G->adjlist [j].count--;
				if(G->adjlist [j].count==0)
				{
					top++;
					St[top]=j;
				}
				p=p->nextarc; 
					
		}
	}
		
	if(flag<G->n)
	    printf("該圖存在回路，不存在拓?fù)湫蛄?！\n");
	else
	{
		printf("該圖的拓?fù)湫蛄袨?");
		for(i=0;i<flag;i++)
		printf("%d",a[i]);
		printf("\n"); 
	}
	
}

int main()
{
	AdjGraph *G;
	int n=7;
	int e=8;
	int A[100][100]={{0,1},{0,0,1,0,0,1},{0,0,0,0,1},{0,0,1,0,1},{0},{0}};
	CreateAdj(G,A,n,e);
	printf("圖的鄰接表：\n");
	DispAdj(G);
	TopSort(G);
	printf("銷毀圖的鄰接表\n");
	DestoryAdj(G);
	return 0; 
}

有問題可以留言文章來源地址http://www.zghlxwxcb.cn/news/detail-490048.html

到了這里，關(guān)于有向圖的拓?fù)渑判虻奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！