拓扑排序算法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