拓撲排序演算法

㈠ 【討論】「拓撲排序演算法僅適用於有向無環圖」，對嗎

支持7樓的說法。在書上看到的是一個拓撲排序演算法，也許還有其他的方法可以進行拓撲排序。而對一個東西進行拓撲排序是要有結果的。拓撲排序演算法只是一個可以進行拓撲排序的方法之一，就像各種排序演算法都能排序。

㈡ 編程實現圖的拓撲排序演算法

typedef struct node
{
int adjvex;
struct node *next;
}edgenode;

typedef struct
{
int vertex;
int id;
edgenode *link;
}vexnode;

vexnode dig[n];

void topsort(vexnode dig[])
{
int i,j,k,m=0,top=-1;
edgenode *p;
for(i=0;i<n;i++)
if(dig[i].id==0)
{
dig[i].id=top;
top=i;
}
while(top!=-1)
{
j=top;
top=dig[top].id;
cout<<dig[j].vertex+1<<"\t";
m++;
p=dig[j].link;
while(p)
{
k=p->adjvex;
dig[k].id--;
if(dig[k].id==0)
{
dig[k].id=top;
top=k;
}
p=p->next;
}
}
if(m<n)
cout<<"The network has a cycle.."<<endl;
}
這個是用棧實現的一個演算法，你看下吧

㈢ 數據結構 拓撲排序

【1】拓撲排序
在一個表示工程的有向圖中，有頂點表示活動，用弧表示活動之間的優先關系，這樣的有向圖為頂點表示活動的網，我們稱為AOV網。
AOV網中的弧表示活動之間存在的某種制約關系。
所謂拓撲排序，其實就是對一個有向圖構造拓撲序列的過程。
【2】拓撲排序演算法
對AOV網進行拓撲排序的基本思路：
從AOV網中選擇一個入度為0的頂點輸出；
然後刪除此頂點，並刪除以次頂點為尾的弧；
繼續重復此操作.....
直到輸出全部頂點或AOV網中不存在入度為0的頂點為止。
由於拓撲排序過程中，需要刪除頂點，顯然用鄰接表更加方便。
因此我們需要為AOV網建立一個鄰接表。
另外，考慮到演算法過程中始終需要查找入度為0的頂點？
需要在原頂點表節點結構中，增加一個入度域in，in就是入度數字。

㈣ 簡單拓撲排序演算法C語言

#include <stdio.h>
#include <stdlib.h>
#define TURE 1
#define FALSE 0
//圖相關----------------------
typedef int ArcCell; /*對於無權圖，用1或0表示是否相鄰；對帶權圖，則為權值類型*/
typedef int booleanType; //狀態變數
typedef struct
{
ArcCell **arcs; /*鄰接矩陣*/
int vexnum; /*圖的頂點數和弧數*/
} MGraph; /*（Adjacency Matrix Graph）*/
//-----------------------------

MGraph G; //圖
booleanType *visited; //建立標志數組(全局量）

int GetGraph(MGraph *G); //建立鄰接矩陣
int SearchNoEn(MGraph *G); //尋找沒有入度的結點。如果沒有，返回-1，否則返回其位置
booleanType Iscircle(MGraph *G); //判斷是否有環。有則返回1，無返回0
int main()
{
GetGraph(&G);
if(Iscircle(&G))
{
printf("YES\n");
}
else
{
printf("NO\n");
}
return 0;
}

int GetGraph(MGraph *G) //建立鄰接矩陣
{
int i, j, v;
scanf("%d", &(G->vexnum));
G->arcs = (ArcCell**)malloc(sizeof(ArcCell*) * G->vexnum);
for(i = 0; i < G->vexnum; i++)
{
G->arcs[i] = (ArcCell*)malloc(sizeof(ArcCell) * G->vexnum);
} //建立二維動態數組

for(i = 0; i < G->vexnum; i++)
{
for(j = 0; j < G->vexnum; j++)
{
scanf("%d", G->arcs[i] + j);
}
} //輸入數據

visited = (booleanType*)malloc(sizeof(booleanType) * G->vexnum); //分配標志數組
for(v = 0; v < G->vexnum; v++) //初始化
{
visited[v] = FALSE;
}
return 0;
}//GetGraph

int SearchNoEn(MGraph *G) //尋找沒有入度的結點。如果沒有，返回-1，否則返回其位置
{
int i, j;
for(i = 0; i < G->vexnum; i++)
{
for(j = 0; j < G->vexnum; j++)
{
if(G->arcs[j][i] == 1)
{
break;
}
if(visited[i] != TURE && j == G->vexnum - 1)
{
return i;
}
}
}
return -1;
}

booleanType Iscircle(MGraph *G) //判斷是否有環。有則返回1，無返回0
{
int i, j;
int count = G->vexnum;
i = SearchNoEn(G);
for(; i != -1; i = SearchNoEn(G))
{
for(j = 0; j < G->vexnum; j++)
{
G->arcs[i][j] = 0;
}
visited[i] = TURE;
count--;
}
if(count != 0)
{
return 1;
}
return 0;
}

㈤ 高手解答 全拓撲排序 c語言演算法 或者 演算法思想也行啊

拓撲排序，很多時候，會作為演算法的預處理。
它是針對有向無環圖。
我空間中寫過，比較詳細。
演算法思想：
針對一個有向無環圖，求它的拓撲排序的一個簡單方法：首先找到這個圖中入度為0的頂點。把它放在序列的第一個位置，然後刪除改頂點和它的邊。得到一個新的有向無環圖，在找這個圖中入度為0的頂點。放在序列的下一個位置，然後再刪除改頂點和它的邊。。。，這個步驟重復直到圖中所有的頂點都在序列中。

詳細請看，有程序代碼和相應的圖片說明。
http://hi..com/huifeng00/blog/item/667348af89c42e044b36d6a6.html

㈥ 拓撲排序的流程圖

由AOV網構造拓撲序列的拓撲排序演算法主要是循環執行以下兩步，直到不存在入度為0的頂點為止：選擇一個入度為0的頂點並輸出之；從網中刪除此頂點及所有出邊。

循環結束後，若輸出的頂點數小於網中的頂點數，則輸出「有迴路」信息，否則輸出的頂點序列就是一種拓撲序列。

由AOV網構造出拓撲序列的實際意義是：如果按照拓撲序列中的頂點次序，在開始每一項活動時，能夠保證它的所有前驅活動都已完成，從而使整個工程順序進行，不會出現沖突的情況。

(6)拓撲排序演算法擴展閱讀

拓撲排序（Topological Sorting）為一個有向無環圖（DAG，Directed Acyclic Graph）的所有頂點的線性序列。且該序列必須滿足下面兩個條件：每個頂點出現且只出現一次。若存在一條從頂點A到頂點B的路徑，那麼在序列中頂點A出現在頂點B的前面。

拓撲排序常用來確定一個依賴關系集中，事物發生的順序。例如，在日常工作中，可能會將項目拆分成A、B、C、D四個子部分來完成，但A依賴於B和D，C依賴於D。為了計算這個項目進行的順序，可對這個關系集進行拓撲排序，得出一個線性的序列，則排在前面的任務就是需要先完成的任務。

㈦ 課程設計 實現拓撲排序演算法

#include<stdio.h>
#include<stdlib.h>
#define MAX_VEXTEX_NUM 20
#define M 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VEXTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
typedef struct //構件棧
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack *); //函數聲明
int Pop(SqStack *, ElemType *);
void Push(SqStack *,ElemType );
int StackEmpty(SqStack *);
void CreatGraph(ALGraph *);
void FindInDegree(ALGraph , int * );
void TopologicalSort(ALGraph );
void InitStack(SqStack *S)//初始化棧
{
S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
int Pop(SqStack *S,ElemType *e)//出棧操作
{
if(S->top==S->base)
{return ERROR;}
*e=*--S->top;
//printf("%d\n",e);
// return e;
return 0;
}
void Push(SqStack *S,ElemType e)//進棧操作
{if(S->top-S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top = S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}*S->top++=e;
}
int StackEmpty(SqStack *S)//判斷棧是否為空
{
if(S->top==S->base)
return OK;
else
return ERROR;}
void CreatGraph(ALGraph *G)//構件圖
{int m, n, i;
ArcNode *p;
printf("請輸入頂點數和邊數:");
scanf("%d%d",&G->vexnum,&G->arcnum);
for (i = 1; i <= G->vexnum; i++)
{G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
for (i = 1; i <= G->arcnum; i++) //輸入存在邊的點集合
{
printf("\n請輸入存在邊的兩個頂點的序號:");
scanf("%d%d",&n,&m);
while (n < 0 || n > G->vexnum || m < 0 || m > G->vexnum)
{printf("輸入的頂點序號不正確 請重新輸入:");
scanf("%d%d",&n,&m);
}
p = (ArcNode*)malloc(sizeof(ArcNode));
if (p == NULL)
{printf("memory allocation failed,goodbey");
exit(1);
}
p->adjvex = m;
p->nextarc = G->vertices[n].firstarc;
G->vertices[n].firstarc = p;
}
printf("建立的鄰接表為:\n"); //輸出建立好的鄰接表
for(i = 1; i <= G->vexnum; i++)
{
printf("%d",G->vertices[i].data);
for(p = G->vertices[i].firstarc; p; p = p->nextarc)
printf("%3d",p->adjvex);
printf("\n");
}}
void FindInDegree(ALGraph G, int indegree[])//求入度操作
{
int i;
for (i = 1; i <= G.vexnum; i++)
{
indegree[i] = 0;
}
for (i = 1; i <= G.vexnum; i++)
{while (G.vertices[i].firstarc)
{indegree[G.vertices[i].firstarc->adjvex]++;
G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
}
}
}
void TopologicalSort(ALGraph G) //進行拓撲排序
{
int indegree[M];
int i, k, n;
int count = 0;
ArcNode *p;
SqStack S;
FindInDegree(G, indegree);
InitStack(&S);
for (i = 1; i <= G.vexnum; i++)
{
printf("第%d個點的入度為%d \n", i, indegree[i]);
}
printf("\n");
for ( i = 1; i <= G.vexnum; i++)
{
if (!indegree[i])
Push(&S,i);
}
printf("進行拓撲排序輸出順序為:"); //輸出結果
while(!StackEmpty(&S))
{
Pop(&S,&n);
printf("%4d",G.vertices[n].data);
count++;
for (p = G.vertices[n].firstarc; p != NULL; p = p->nextarc)
{
k = p->adjvex;
if (!(--indegree[k]))
{
Push(&S,k);
}
}

}printf("\n");

if (count < G.vexnum)
{
printf("出現錯誤\n");
}
else
{
printf("排序成功\n");
}
}
int main(void) //主函數
{
ALGraph G;
CreatGraph(&G);
TopologicalSort(G);
system("pause");
return 0;
}

㈧ 在用鄰接表表示圖時，拓撲排序演算法時間復雜度為多少

O（n + e）。
對於一個具有n個頂點e條弧的有向圖來說，剛開始將入度為0的頂點入棧的時間復雜為O(n)，在之後頂點出棧時，入度減1的操作共執行了e次，所以整個演算法的時間復雜度為O(n + e)。

㈨ 圖的拓撲排序

拓撲排序是有向圖的一個重要操作。在給定的有向圖G中，若頂點序列vi1,vi2,...,vin滿足下列條件：若在有向圖G中從頂點vi到頂點vj有一條路徑，則在序列中頂點vi必在頂點vj之前，便稱這個序列為一個拓撲序列。求一個有向圖拓撲序列的過程稱為拓撲排序。
舉例：計算機專業的學生應該學習的部分課程及其每門課程所需要的先修課程。
拓撲排序的方法：
（1）從圖中選擇一個入度為0的頂點且輸出之；
（2）從圖中刪掉該頂點及其所有以該頂點為弧尾的弧；
反復執行這兩個步驟，直到所有的頂點都被輸出，輸出的序列就是這個無環有向圖的拓撲序列。細心的讀者可能會發現：在每一時刻，可能同時存在多個入度為0的頂點，選擇註：表中c1~c9列表示的是每個頂點的入度。
下面我們討論一下如何實現拓撲排序的演算法。假設有向圖以鄰接表的形式存儲。
下面給出演算法實現的基本過程：
{ 將所有入度為0的頂點入棧；
當棧非空時重復執行下列操作：
從棧中退出頂點k；
（1）將k頂點的信息輸出；
（2）將與k鄰接的所有頂點的入度減1。 }#defineMAX_VERTEX_NUM30//最大頂點個數typestructEdgeLinklist{//邊結點intadjvex;structEdgeLinklist*next;}EdgeLinklist;typedefstructVexLinklist{//頂點結點Elemtypeelem;intindegree;//記錄頂點的入度EdgeLinklist*firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];下面是拓撲排序的完整演算法。 StatusTopologicalSort(AdjListadj){InitStack(s);for(i=0;i<MAX_VERTEX_NUM-1;i++)if(adj.indegree==0)Push(s,i);while(!StackEmpty(s)){Pop(s,i);printf(i);for(p=adj.firstedge;p;p=p->next){adj.indegree-=1;if(adj.indegree==0)Push(s,i);}

㈩ 拓撲排序是一種內部排序的演算法，對嗎

不是，不對的