D-oj|使用邻接表实现AOV网的拓扑排序算法 题目编号:1137

用邻接表存储有向图，在顶点表中增加入度域，使用队列存储入度为零的顶点编号，实现AOV网的拓扑排序算法，并输出拓扑序列，顶点个数少于20个。

部分提示代码：

#include <iostream>
using namespace std;

struct Arcnode
{
    int adjvex;
    Arcnode *next;
};

struct Vertexnode
{
    int in;
    char vertex;
    Arcnode *firstedge;
};

const int Maxsize = 20;

class ALgraph
{
public:
    ALgraph(char a[],int n,int e);  
    ~ALgraph();
    void TopSort();
private:
    Vertexnode adjlist[Maxsize];
    int vertexnum;
    int arcnum;
};

ALgraph::ALgraph(char a[],int n,int e)
{
  //write your code

}

ALgraph::~ALgraph()
{
    int i;
    Arcnode *p;
    for(i=0;i<vertexnum;i++)
    {
        p = adjlist[i].firstedge;
        while(p)
        {
            Arcnode *q = p;
            p = p->next;
            delete q;
        }
    }

}

void ALgraph::TopSort()
{
    //write your code

}
int main()
{
    int i,n,m;

    cin >>n>>m;

    char *b = new char[n];

    for (i = 0;i < n;i++)
    {
        cin >>b[i];
    }

    ALgraph al(b,n,m);

    al.TopSort();
    return 0;
}

输入描述

首先输入图中顶点个数和边的条数； 输入顶点的信息（字符型）； 输入各顶点的入度； 输入各边及其权值。

输出描述

输出AOV网的拓扑序列（顶点信息），以空格隔开，最后一个顶点后面有空格，如果AOV网存在回路，输出"有回路"的信息，占一行。

输入样例

6 9
A B C D E F
3 0 1 3 0 2
1 0
1 3
2 0
2 3
3 0
3 5
4 2
4 3
4 5

输出样例

B E C D F A 

思路

为了避免有回路也会输出，所以先将每次加入列表，最后再经过判断后是输出”有回路“，还是输出前驱顶点

问题

不知道是平台问题还是什么，问题暂未解决，求解。。。

• 使用while循环输出，50%正确

while(front!=a){
        if(count<vertexnum){cout<<"有回路";front=a;}
        else{cout<<A[++front]<<" ";}
    }

• 使用if语句+for循环，100%正确

 if(count<vertexnum){cout<<"有回路";}
    else{
       for(int i=0;i<vertexnum;i++) {
           cout<<A[i]<<' ';

    }}

完整代码

#include <iostream>
using namespace std;
struct Arcnode
{
    int adjvex;
    Arcnode *next;
};
struct Vertexnode
{
    int in;
    char vertex;
    Arcnode *firstedge;
};
const int Maxsize = 20;
class ALgraph
{
public:
    ALgraph(char a[],int n,int e);
    ~ALgraph();
    void TopSort();
private:
    Vertexnode adjlist[Maxsize];
    int vertexnum;
    int arcnum;
    int S[Maxsize];//栈表
    char A[Maxsize];//存储输出的栈；
};
ALgraph::ALgraph(char a[],int n,int e)
{
    //write your code
    vertexnum=n;
    arcnum=e;
    int in;
    int x1,x2;
    for(int i=0;i<n;i++){
        //存顶点
        cin>>in;
        adjlist[i].vertex=a[i];
        adjlist[i].in=in;
        adjlist[i].firstedge=NULL;
    }
    for(int i=0;i<e;i++){
        cin>>x1>>x2;
        Arcnode *p=new Arcnode;
        p->adjvex=x2;
        p->next=adjlist[x1].firstedge;
        adjlist[x1].firstedge=p;
    }}
ALgraph::~ALgraph()
{
    int i;
    Arcnode *p;
    for(i=0;i<vertexnum;i++)
    {
        p = adjlist[i].firstedge;
        while(p)
        {
            Arcnode *q = p;
            p = p->next;
            delete q;
        }
    }

}
void ALgraph::TopSort()
{
    //write your code
    int top=-1,front=-1,j,count=0,a=0;
    for(int i=0;i<vertexnum;i++){
        if(adjlist[i].in==0)S[++top]=i;//入度为0的入栈
    }
    while(front!=top){
        j=S[++front];//入度0出栈
        A[a++]=adjlist[j].vertex;
        count++;//count计算已经出栈的顶点个数
        Arcnode *p;
        p=adjlist[j].firstedge;
        while(p!=NULL){
            //将j的每一个邻接点入度计数减1，当它为0的时候它就是下一个没有前驱而入栈的顶点
            adjlist[p->adjvex].in--;
            if(adjlist[p->adjvex].in==0)S[++top]=p->adjvex;
            p=p->next;
        }
    }
    //while循环50%正确
    /*front=-1;
    while(front!=a){
        if(count<vertexnum)throw"有回路";
        else{cout<<A[++front]<<' ';}
    }*/
    if(count<vertexnum){cout<<"有回路";}
    else{
       for(int i=0;i<vertexnum;i++) {
           cout<<A[i]<<' ';
    }}
}
int main()
{
    int i,n,m;
    cin >>n>>m;
    char *b = new char[n];
    for (i = 0;i < n;i++)
    {
        cin >>b[i];
    }
    ALgraph al(b,n,m);
    al.TopSort();
    return 0;
}