给定一个有向图,求其拓扑序列,若有环路,输出error!
注意:本题用栈结构实现入度为0结点存储,否则拓扑序列输出顺序会和测试数据不一致。本题栈结构建议用数组实现,不用栈类。
###你要实现的 函数接口定义:
void TopSort(AdjGraph *G);//邻接表拓扑排序。注:需要在该函数开始计算并初始化每个节点的入度,然后再进行拓扑排序
裁判测试程序样例:
#define MAXV 20
#include <iostream>
using namespace std;
typedef struct ANode
{ int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
int info; //该边的相关信息,如权重
} ArcNode; //边表节点类型
typedef int Vertex;
typedef struct Vnode
{
Vertex data; //顶点信息
int count; //入度
ArcNode *firstarc; //指向第一条边
} VNode; //邻接表头节点类型
typedef VNode AdjList[MAXV];
typedef struct
{ AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} AdjGraph;
void CreateAdj(AdjGraph *&G,int n,int e); //创建图邻接表
void TopSort(AdjGraph *G); //邻接表拓扑排序
void DispAdj(AdjGraph *G); //输出邻接表,供测试
int main()
{
int n,e,i,v;
AdjGraph *G;
cin>>n>>e;
CreateAdj(G,n,e);
//DispAdj(G);
cout<<"拓扑序列:";
TopSort(G);
}
void DispAdj(AdjGraph *G)
//输出邻接表G,可以供测试用
{
int i;
ArcNode *p;
for (i=0;i<G->n;i++)
{
p=G->adjlist[i].firstarc;
if (p!=NULL) printf("%3d: ",i);
while (p!=NULL)
{
printf("%3d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}
void CreateAdj(AdjGraph *&G,int n,int e) //创建图邻接表
{
int i,j,a,b;
ArcNode *p;
G=new AdjGraph;
for (i=0;i<n;i++) G->adjlist[i].firstarc=NULL;
for (i=1;i<=e;i++) //根据输入边建图
{
cin>>a>>b; //有向图
p=new ArcNode; //创建一个结点p
p->adjvex=b; //存放邻接点
p->nextarc=G->adjlist[a].firstarc; //采用头插法插入结点p
G->adjlist[a].firstarc=p;
}
G->n=n; G->e=n;
}
/* 请在这里填写答案 */
输入样例1:
5 7
1 0
4 3
2 1
2 0
3 2
4 1
4 2
输出样例1:
顶点编号空格隔开,尾部不带空格。
拓扑序列:4 3 2 1 0
输入样例2:
5 8
0 3
1 0
4 3
2 1
2 0
3 2
4 1
4 2
输出样例:
error!
先说说拓扑排序的实现思想:
因为 a ,b两个顶点是没有前驱的顶点的,所以说先用a(或b也一样)入栈,然后擦除 a 指出去的箭头(相当于独立出来了),然后再看剩下的没有前驱顶点的顶点,重复这个操作,直到图空。
详细流程就是:
因为这道题有说到需要用栈,那用栈的算法思想就在这里了:
CountInDegree(G,indegree); // 对各顶点求入度。
InitStack(S);
for ( i=0; i<G.vexnum; ++i)
if (!indegree[i]) Push(S, i); // 入度为零的顶点入栈
count=0; // 对输出顶点计数
while (!EmptyStack(S)) {
Pop(S, v); ++count; printf(v);
for (w=FirstAdj(v); w; w=NextAdj(G,v,w)){
--indegree(w); // 弧头顶点的入度减一
if (!indegree[w]) Push(S, w);// 新产生的入度为零的顶点入栈
}
}
if ( count<G.vexnum )printf("图中有回路");
整理一下,那这道题的最终代码在这,,
代码如下:
void TopSort(AdjGraph *G) {
// 初始化入度数组
for (int i = 0; i < G->n; i++) {
G->adjlist[i].count = 0;
}
// 计算每个节点的入度
for (int i = 0; i < G->n; i++) {
ArcNode *p = G->adjlist[i].firstarc;
while (p != NULL) {
G->adjlist[p->adjvex].count++;
p = p->nextarc;
}
}
// 使用数组实现栈结构存储入度为0的节点
int stack[MAXV];
int top = -1;
// 将初始入度为0的节点压入栈
for (int i = 0; i < G->n; i++) {
if (G->adjlist[i].count == 0) {
stack[++top] = i;
}
}
// 拓扑排序结果计数
int count = 0;
// 存储拓扑序列
int result[MAXV];
// 处理栈中的节点
while (top != -1) {
int u = stack[top--]; // 弹出栈顶节点
result[count++] = u; // 记录拓扑序列
// 遍历u的所有邻接节点
ArcNode *p = G->adjlist[u].firstarc;
while (p != NULL) {
int v = p->adjvex;
G->adjlist[v].count--; // 邻接节点入度减1
if (G->adjlist[v].count == 0) {
stack[++top] = v; // 新的入度为0的节点入栈
}
p = p->nextarc;
}
}
// 判断是否存在环路
if (count < G->n) {
cout << "error!";
} else {
// 输出拓扑序列
for (int i = 0; i < count; i++) {
if (i > 0) cout << " ";
cout << result[i];
}
}
}