拓撲排序演算法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;
}
B. （C語言）用兩種方法（棧和隊列）拓撲排序，由用戶選擇方法
#include <stdio.h>
#include <stack>
#include <queue>
#include <stdlib.h>
#define N 6
#define MAX 10000
void sTop(int quan[N][N])//用棧列印的是拓撲序列的逆序列
{
int visited[N],cur,i;
bool mark;
memset(visited,0,sizeof(visited));
std::stack<int> s;
for(i=0;i<N;i++)
{
if(!visited[i]){
s.push(i);
visited[i]=1;
}
while(!s.empty())
{
mark=true;
cur=s.top();
for(int i=0;i<N;i++)
if(!visited[i]&&quan[cur][i]!=MAX)
{
mark=false;
s.push(i);
visited[i]=1;
}
if(mark)
{
printf("%d ",cur);
s.pop();
}
}
}
putchar('\n');
}
void qTop(int quan[N][N])//用隊列做
{
int count[N]={0},i,j,cur;
std::queue<int> q;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(quan[i][j]!=MAX)
count[j]++;
for(i=0;i<N;i++)
if(count[i]==0)
q.push(i);
while(!q.empty())
{
cur=q.front();
q.pop();
printf("%d ",cur);
for(i=0;i<N;i++)
{
if(quan[cur][i]!=MAX)
{
count[i]--;
if(count[i]==0)
q.push(i);
}
}
}
putchar('\n');
}
main()
{
int A[N][N],i,j;//圖採用鄰接矩陣存儲，
for(i=0;i<N;i++)
for(j=0;j<N;j++)
A[i][j]=MAX;//從i到j沒有弧,全部初始化為MAX
//自己先把測試圖畫一下吧
A[0][5]=A[2][0]=A[1][2]=A[1][4]=A[4][5]=A[4][3]=A[2][3]=1;//0->5..有弧,長度為1
sTop(A);//棧列印
qTop(A);//隊列印
}
C. 求拓撲排序演算法，用C語言，詳細點，謝謝！
#include
<cstdio>
#include
<cstring>
#include
<stack>
using
namespace
std;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
Description:
表示圖的結點的鄰接邊
struct
Edge
{
int
dest;
Edge
*next;
}
**graph;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
Description:
添加一個邊
//
Input:
e
-
要添加邊的結點,
p
-
目的地
//
Output:
e
-
添加邊後的結點
void
AddEdge(Edge
*&e,
int
p)
{
if(!e)
{
e
=
new
Edge;
e->dest
=
p;
e->next
=
0;
}
else
{
Edge
*tail
=
e;
while
(tail->next)
tail
=
tail->next;
tail->next
=
new
Edge;
tail
=
tail->next;
tail->dest
=
p;
tail->next
=
0;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
Description:
輸入結點之間的邊
//
Input:
Console下用戶輸入,起點和終點;
m
-
邊的個數
//
Output:
graph
-
圖;
void
Input(int
&m)
{
int
i,
a,
b;
//
a->b存在邊(有向)
for
(i
=
0;
i
<
m;
i++)
{
scanf("%d
%d",
&a,
&b);
AddEdge(graph[a],
b);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
Description:
獲得每個結點的入度
//
Input:
n
-
結點的個數
//
Output:
degree
-
每個結點的入度
void
GetDegree(int
*degree,
int
n)
{
int
i
=
0;
Edge
*edge;
memset(degree,
0,
sizeof(int)
*
n);
for
(i
=
0;
i
<
n;
i++)
{
edge
=
graph[i];
while(edge)
{
degree[edge->dest]++;
edge
=
edge->next;
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
Description:
拓撲排序
//
Input:
n
-
結點個數
//
Output:
console下輸出一個正確的拓撲序
void
TopoSort(int
n)
{
int
*degree
=
new
int[n];
//
初始化所有結點的入度
GetDegree(degree,
n);
stack<int>
s;
//
獲得入度為0的結點,並入棧
int
i
=
0;
for
(i
=
0;
i
<
n;
i++)
if
(degree[i]
==
0)
s.push(i);
int
index
=
0;
//
結點的下標
Edge
*edge;
//
當前結點鄰接表
while
(!s.empty())
{
index
=
s.top();
printf("%d",
index);
s.pop();
edge
=
graph[index];
while
(edge)
{
if
(--degree[edge->dest]
==
0)
s.push(edge->dest);
edge
=
edge->next;
}
}
delete
[]degree;
}
int
main()
{
int
n,
m;
//
結點個數、邊個數
scanf("%d
%d",
&n,
&m);
int
i;
graph
=
new
Edge*[n];
for(i
=
0;
i
<
n;
i++)
graph[i]
=
0;
Input(m);
TopoSort(n);
return
0;
}
D. 怎樣實現c語言的拓撲排序啊，誰能幫我寫一下代碼啊 謝謝啊
#include<stdio.h>
#include<stdlib.h>
#define Max_VertexNum 100 //頂點個數的宏定義
/*鄰接表結點*/
typedef struct node{
int adjvex; /*鄰接點域*/
struct node *next;/*鏈域*/
}EdgeNode;
/*頂點結點*/
typedef struct vnode{
int vertex; //頂點域
int Degree; //存放入度
EdgeNode *firstedge; //邊頭指針
}VertexNode;
typedef VertexNode Adjlist[Max_VertexNum];//定義一個鄰接表的數組,用於存放頂點的信息
/*圖的定義*/
typedef struct ALGraph{
Adjlist adjlist;
int n,e;//圖的頂點和邊
}Graph;
/*
為了避免重復檢測入度為0的頂點，設置一個棧暫存所有入度為0的頂點
*/
typedef struct stacknode{
int data;
struct stacknode *next;
}StackNode;
typedef struct{
StackNode *top; //棧頂指針
}LinkStack;
//////////////////////////////////////////////////////////////////////////////////////////
//輔助棧的相關定義
/*
初始化棧
*/
void InitStack(LinkStack *S)
{
S->top=NULL;
}
/*
判空
*/
int IsEmpty(LinkStack *S)
{
return(S->top==NULL);
}
/*
進棧
*/
void Push(LinkStack *S,int x)
{
StackNode *p;
p=(StackNode*)malloc(sizeof(StackNode));
p->data=x;
p->next=S->top;
S->top=p;
}
/*
出棧
*/
int Pop(LinkStack *S)
{
int x;
StackNode *p=S->top; //保存頭指針
if(IsEmpty(S))
{
printf("棧為空!");
exit(1);
}
x=p->data;
S->top=p->next; //將棧頂結點從棧上摘下
free(p);
return x;
}
////////////////////////////////////////////////////////////////////////////////////////////////////
/*
建立一個有向圖，其存儲結構為鄰接表
*/
void CreateGraph(Graph *G)
{
int i,j,k;
EdgeNode *s;
printf("請輸入圖的頂點數和邊數: ");
scanf("%d %d",&G->n,&G->e);
//建立頂點列表
for(i=1;i<=G->n;i++)
{
printf("請輸入頂點的信息: ");
printf("\n");
scanf("%d",&G->adjlist[i].vertex);
G->adjlist[i].firstedge=NULL;
}
for(k=0;k<G->e;k++)
{
printf("請輸入邊(vi,vj)的頂點序號: ");
printf("\n");
scanf("%d%d",&i,&j);
s=(EdgeNode*)malloc(sizeof(EdgeNode)); //生成邊表結點
s->adjvex=j;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s; //將新建的結點插入到邊表的頭部
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
對各個頂點求入度
*/
void FindInDegree(Graph *G)
{
int i,j;
EdgeNode *p;
for(i=1;i<=G->n;i++)
{
G->adjlist[i].Degree=0;
}
for(j=1;j<=G->n;j++)
{
for(p=G->adjlist[j].firstedge;p;p=p->next)
{
G->adjlist[p->adjvex].Degree++;
}
/*
p=G->adjlist[j].firstedge;
while(p!=NULL)
{
G->adjlist[p->adjvex].Degree++;
p=p->next;
}
*/
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
進行拓撲有序排列
*/
int TopoSort(Graph *G)
{
int i,m,k;
int count=0;
LinkStack S;
FindInDegree(G);
InitStack(&S);
for(i=1;i<=G->n;i++)
{
if(!G->adjlist[i].Degree)
{
Push(&S,i);
}
}
while(!IsEmpty(&S))
{
m=Pop(&S);
printf("(%d,%d)",m,G->adjlist[m].vertex); //輸出i號頂點並計數
count++;
for(EdgeNode *p=G->adjlist[m].firstedge;p;p=
p->next)
{
k=p->adjvex;
if(!(--G->adjlist[k].Degree))
{
Push(&S,k);
}
}
}
if(count<G->n)
{
printf("有迴路!");
exit(1);
}
else
{
return 0;
}
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
輸出有向圖
*/
void PrintAdjlist(Graph *G)
{
int i;
EdgeNode *p;
for(i=1;i<=G->n;i++)
{
printf("%d:%d",i,G->adjlist[i].vertex);
for(p=G->adjlist[i].firstedge;p;p=p->next)
{
printf("%d",p->adjvex);
}
printf("\n");
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
主函數
*/
void main()
{
Graph G;
CreateGraph(&G);
PrintAdjlist(&G);
TopoSort(&G);
}
E. 編程實現圖的拓撲排序演算法
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;
}
這個是用棧實現的一個演算法，你看下吧
F. 求C語言高手！數據結構的拓撲排序
演算法
1.無前趨的頂點優先:
(1)演算法描述：
(a)從網中選擇一個入度為零的頂點輸出；
(b)刪除該頂點及其於該點有關的所有邊；
(c)是否還有入度為零的頂點？若有，執行(a)，否則結束。
演算法實現
以鄰接表為圖的存儲結構的演算法：
a)掃描頂點表，將入度為零的頂點入棧；
b)當棧非空時：
輸出棧頂元素v，出棧；
檢查v的出邊，將每條出邊的終端頂點的入度減1，若該頂點入度為0，入棧；
c)當棧空時，若輸出的頂點小於頂點數，則說明AOV網有迴路，否則拓撲排序完成。
演算法實現：
void Graph::Toplogicasort()//top是入度為0的頂點棧的棧頂指針
{
int top=-1;
for(int i=0;i<n;i++) //建立如度為0頂點的鏈棧
if (count[i]==0)
{
count[i]=top;
top=i;
}
for(int i=0;i<n;i++)
if(top==-1)
{
cout<<"Network has a cycle"<<endl;
return;
}
else
{
int j=top;top=count[top];//入度為0的頂點出棧
count<<j<<endl;
Edge<float> *l=NodeTable[j].adj;
while(l)
{
int k=l,dest;
if(--count[k]==0)
{
count[k]=top;//入度減至0的頂點進棧
top=k;
}
l=l->link;//取j的下一條出邊
}
}
}
/*通常的拓撲演算法要用兩個數組，一個用來記錄每個頂點的入度，當入度為0，則進棧
。另一個數組用作棧數組，記錄入度為0的頂點。其實當入度為0的頂點進棧以後，count[i]
＝0就不再有用，所以可以用count[i]記錄棧內下一個入度為0的頂點，top指向棧頂頂點號 */
G. 有關拓撲排序c語言實現：
指針作為函數參數的問題。。
void init_stack(struct linkstack *top) 參數是一個指針，也就是你需要傳一個地址進去，當你調用這個函數的時候，比如
struct linkstack *myTop;
init_stack(myTop);
沒錯，myTop指向的地址傳進去了，但是，在你函數體裡面的top和myTop雖然它們的值一樣，也就是它們指向的地址一樣，但是這兩個指針是兩個不同的指針，你改變的是top這個形參的值，也就是說top被指向了一個新的地址，是你malloc出來的地址，但是myTop所指的地方還是沒有變的，所以初始化就失敗了。（注意函數的形參是實參的一份，是一個新的變數，只是這個變數的值和實參一樣，但是它們的地址和作用域都不一樣）
這里需要傳指向指針的指針作為參數:
void init_stack(struct linkstack **top){
*top = (struct linkstack *)malloc(sizeof(struct linkstack));
(*top)->next = NULL;
}
調用的時候把myTop的地址傳進去，比如：
struct linkstack *myTop;
struct linkstack ** p = &myTop;
init_stack(p);
這樣，在init_stack函數裡面修改的就是*p，也就是【p所指的地址的內容】，這里的p和參數裡面的形參top，它們雖然是兩個不同的指針，但是它們指向一個地址，修改了top所指的內容也就修改了p所指的內容。
H. 用讀取文件的方法編有向圖的拓撲排序（用C語言編）
拓撲排序演算法:先計算各個頂點的入度，將入度為0的頂點入棧，然後通過循環，將入度為0的頂點出棧，此時要count記錄出棧的頂點個數，並將與該頂點的鄰接頂點的入度減1，若減後的頂點中有入度為0的，則將其入棧，直到所有的頂點都訪問到為止。如果count不等頂點的個數，說明圖中有環，錯誤的！
//stack.h頭文件
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define STACKSIZE 50
#define STACKINCREMENT 20
#define OVERFLOW -1
#define OK 1
#define ERROR -1
typedef struct
{
int *base;
int *top;
int stacksize;
}Stack;//棧的結構，存儲圖的頂點序號
int InitStack(Stack &s) //創建一個空棧
{
s.base=(int*)malloc(STACKSIZE*sizeof(int));
if(!s.base)
return (OVERFLOW);
s.top=s.base;
s.stacksize=STACKSIZE;
return (OK);
}
int Push(Stack &s,int e)
{
if((s.top-s.base)>s.stacksize)
{
s.base=(int*)realloc(s.base,(STACKSIZE+STACKINCREMENT)*sizeof(int));
if(!s.base)
return(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*s.top++=e;
return (OK);
}
bool Empty(Stack s)
{
if(s.base==s.top)
return true;
else
return false;
}
int Pop(Stack &s)
{
int e;
e=*--s.top;
return e;
}
//graph.h文件
//有向無環圖的拓撲排序
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MAX 20
#define NULL 0
typedef struct ArcNode //頭節點
{
int adjvex; //該邊所指向的頂點的位置
struct ArcNode *nextarc; //指向下一條邊
}ArcNode;//弧結點
typedef struct VNode //表節點
{
int data; //頂點信息
int indegree; //節點的入度
ArcNode *firstarc; //指向第一條依附該節點的邊的指針
}VNode,AdjList[MAX];
typedef struct
{
AdjList vertices; //表節點
int vexnum; //節點的個數
int arcnum; //邊的條數
}Graph;
int LocateVex(Graph G,int v) //返回節點v在圖中的位置
{
int i;
for(i=0;i<G.vexnum;++i)
if(G.vertices[i].data==v)
break;
else
continue;
if(i<G.vexnum)
return i;
else
return -1;
}
void CreateGraph(Graph &G)
{
int m,n;
printf("請輸入圖的節點數: ");
scanf("%d",&m);
while(m<0)
{
printf("Error!\n頂點數不能小於1.\n");
printf("請重新輸入圖的頂點數: ");
scanf("%d",&m);
}
printf("請輸入圖的邊數: ");
scanf("%d",&n);
while(n<0)
{
printf("Error!\n圖的邊數不能小於0.\n");
printf("請重新輸入圖的邊數: ");
scanf("%d",&n);
}
G.vexnum=m; //頂點數目
G.arcnum=n; //邊的數目
int i,j,k;
for(i=0;i<G.vexnum;++i) //初始化圖的信息
{
G.vertices[i].data=i+1; //頂點信息
G.vertices[i].firstarc=NULL;
G.vertices[i].indegree=0; //開始時入度都為0
}
//頂點信息
printf("輸出頂點信息:\n");
for(i=0;i<G.vexnum;++i)
printf("v%d\n",G.vertices[i].data);
int v1,v2,flag=0;
for(k=0;k<G.arcnum;++k)
{
printf("請輸入第%d邊的起點和終點: ",k+1);
scanf("%d%d",&v1,&v2);
i=LocateVex(G,v1); //頂點v1在圖中的位置
j=LocateVex(G,v2); //頂點v2在圖中的位置
if(i >=0 && j>=0)
{
++flag;
(G.vertices[j].indegree)++;
ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=NULL;
ArcNode *p1;
if(! G.vertices[i].firstarc)
G.vertices[i].firstarc=p;
else
{
for(p1=G.vertices[i].firstarc;p1->nextarc;p1=p1->nextarc); //求該頂點的最後一個鄰接頂點
p1->nextarc=p; //將p插入到最後一個鄰接頂點的後面
}
}
else //沒有該弧，刪除掉
{
printf("沒有該邊!\n");
k=flag;
}
}
//輸出鄰接表
printf("構造的鄰接表為:\n");
printf("位置 頂點 弧\n");
for(i=0;i<G.vexnum;++i)
{
printf(" %d v%d",i,G.vertices[i].data);
ArcNode *p=G.vertices[i].firstarc;
if(p)
{
while(p->nextarc)
{
printf("->v%d",p->adjvex+1);
p=p->nextarc;
}
printf("->v%d\n",p->adjvex+1);
}
else
printf("\n");
}
printf("輸出個頂的的入度:\n");
for(i=0;i<G.vexnum;++i)
{
printf("%d頂點的入度為: %d\n",G.vertices[i].data,G.vertices[i].indegree);
}
}
int FirstAdjVex(Graph G,int v) //返回v的第一個鄰接頂點
{
if(G.vertices[v].firstarc)
return G.vertices[v].firstarc->adjvex;
else
return -1;
}
int NextAdjVex(Graph G,int v,int w) //返回v中相對於w的下一個鄰接頂點
{
int flag=0;
ArcNode *p;
p=G.vertices[v].firstarc;
while(p)
{
if(p->adjvex==w)
{
flag=1;
break;
}
p=p->nextarc;
}
if(flag && p->nextarc)
return p->nextarc->adjvex;
else
return -1;
}
bool Visited[MAX];
//main.cpp文件
#include "graph.h"
#include "stack.h"
void TopologicalSort(Graph G) //拓撲排序函數
{
int i,j,k;
int count=0; //用來統計頂點的個數
Stack s; //定義一個棧，用來保存入度為0的頂點
InitStack(s); //初始化棧
for(i=0;i<G.vexnum;++i)
if(G.vertices[i].indegree==0) //若第i個頂點的入度為0 ，i表示頂點在圖中的位置
Push(s,i); //將第i個頂點入棧
while(!Empty(s))
{
j=Pop(s); // 將為入度0的頂點位置出棧，並保存到j中
count++; //統計頂點的個數
printf("v%d ",G.vertices[j].data); //輸出入度為0的頂點
ArcNode *p;
for(p=G.vertices[j].firstarc; p ;p=p->nextarc) //找與第j個頂點的鄰接頂點，並將其入度減1
{
k=p->adjvex;
--(G.vertices[k].indegree);
if(G.vertices[k].indegree==0) //如果入度為0,就入棧
Push(s,k);
}
}
if(count<G.vexnum) //count小於頂點的個數時候，說明有環，不符合拓撲排序的要求
{
printf("Error!\n圖中有環!不是有向無環圖!\n");
exit(0); //退出
}
}
//主函數的實現
void main()
{
Graph G;
CreateGraph(G);
printf("\n拓撲排序為: \n");
TopologicalSort(G);
printf("\n");
}
I. 高手解答 全拓撲排序 c語言演算法 或者 演算法思想也行啊
拓撲排序，很多時候，會作為演算法的預處理。
它是針對有向無環圖。
我空間中寫過，比較詳細。
演算法思想：
針對一個有向無環圖，求它的拓撲排序的一個簡單方法：首先找到這個圖中入度為0的頂點。把它放在序列的第一個位置，然後刪除改頂點和它的邊。得到一個新的有向無環圖，在找這個圖中入度為0的頂點。放在序列的下一個位置，然後再刪除改頂點和它的邊。。。，這個步驟重復直到圖中所有的頂點都在序列中。
詳細請看，有程序代碼和相應的圖片說明。
http://hi..com/huifeng00/blog/item/667348af89c42e044b36d6a6.html