[已解决]编程实现由偏序集合构造全序集合，最好能用C或C++编写，谢谢了

Simanzen

编程实现由偏序集合构造全序集合，最好能用C或C++编写，谢谢了

最佳答案

月排行榜 / 总排行榜

lixiaoshuai

2015-1-26 02:05:11

#include <iostream>  
#include <fstream>  
#include <stack>  
using namespace std;  
  
ifstream fin("in.txt");  
#define MAX_VERTEX_NUM 26  
  
stack<int> s;  
  
typedef struct ArcNode{  
    int adjvex;  
    struct ArcNode *nextarc;  
    ArcNode(){nextarc=0;}  
//  InfoType *info;  
}ArcNode;  
  
typedef struct VNode{  
    int data;  
    ArcNode *firstarc;  
    VNode(){firstarc=0;}  
}VNode,AdjList[MAX_VERTEX_NUM];  
  
typedef struct{  
    AdjList vertices;  
    int vexnum,arcnum;  
    int kind;  
}ALGraph;  
  
bool TopologicalSort(ALGraph G,int *indegree)  
{  
    int i,k;  
    for(i=1;i<G.vexnum+1;i++)  
    {  
        if(!indegree[i]){s.push(i);}  
    }  
    int count=0;  
    ArcNode *p;  
    while(!s.empty())  
    {  
        i = s.top();  
        s.pop();  
        cout<<G.vertices[i].data<<"-->";  
        count++;  
        for(p=G.vertices[i].firstarc;p;p=p->nextarc)  
        {  
            k = p->adjvex;  
            indegree[k]--;  
            if(!indegree[k])s.push(k);  
        }  
    }  
    if(count<G.vexnum) return false;  
    return true;  
}  
  
  
int main()  
{  
    int i;  
    ALGraph g;  
    cout<<"输入节点数和边数： ";  
    fin>>g.vexnum>>g.arcnum;  
    for(i=1;i<g.vexnum+1;i++)  
        g.vertices[i].data = i;  
  
    int b,e;  
    ArcNode *p;  
    int *indegree = new int[g.vexnum+1];      
    //注意 int *a=new int(n);  申请一个整型变量空间，赋初值为n，并定义一个整型指针a指向该地址空间   
    //int *indegree=(int *)malloc(sizeof(int)*(g.vexnum+1));  
    memset(indegree,0,sizeof(int)*(g.vexnum+1));  
    cout<<"逐一输入边的顶点对，形如 3 5 "<<endl;  
    for(i=1;i<g.arcnum+1;i++)  
    {  
        cout<<"第"<<i<<"条边：";  
        fin>>b>>e;  
        p = new ArcNode();  
        p->adjvex = e;  
        p->nextarc = g.vertices[b].firstarc;  
        g.vertices[b].firstarc = p;  
        indegree[e]++;  
        cout<<endl;  
    }  
    if(TopologicalSort(g,indegree))cout<<"正常完成！"<<endl;  
    else cout<<"该有向图有回路！"<<endl;  
    return 0;  
}  
其实是一个拓扑排序实现偏序。

跳转到最佳答案楼层

lixiaoshuai

#include <iostream>  
#include <fstream>  
#include <stack>  
using namespace std;  
  
ifstream fin("in.txt");  
#define MAX_VERTEX_NUM 26  
  
stack<int> s;  
  
typedef struct ArcNode{  
    int adjvex;  
    struct ArcNode *nextarc;  
    ArcNode(){nextarc=0;}  
//  InfoType *info;  
}ArcNode;  
  
typedef struct VNode{  
    int data;  
    ArcNode *firstarc;  
    VNode(){firstarc=0;}  
}VNode,AdjList[MAX_VERTEX_NUM];  
  
typedef struct{  
    AdjList vertices;  
    int vexnum,arcnum;  
    int kind;  
}ALGraph;  
  
bool TopologicalSort(ALGraph G,int *indegree)  
{  
    int i,k;  
    for(i=1;i<G.vexnum+1;i++)  
    {  
        if(!indegree[i]){s.push(i);}  
    }  
    int count=0;  
    ArcNode *p;  
    while(!s.empty())  
    {  
        i = s.top();  
        s.pop();  
        cout<<G.vertices[i].data<<"-->";  
        count++;  
        for(p=G.vertices[i].firstarc;p;p=p->nextarc)  
        {  
            k = p->adjvex;  
            indegree[k]--;  
            if(!indegree[k])s.push(k);  
        }  
    }  
    if(count<G.vexnum) return false;  
    return true;  
}  
  
  
int main()  
{  
    int i;  
    ALGraph g;  
    cout<<"输入节点数和边数： ";  
    fin>>g.vexnum>>g.arcnum;  
    for(i=1;i<g.vexnum+1;i++)  
        g.vertices[i].data = i;  
  
    int b,e;  
    ArcNode *p;  
    int *indegree = new int[g.vexnum+1];      
    //注意 int *a=new int(n);  申请一个整型变量空间，赋初值为n，并定义一个整型指针a指向该地址空间   
    //int *indegree=(int *)malloc(sizeof(int)*(g.vexnum+1));  
    memset(indegree,0,sizeof(int)*(g.vexnum+1));  
    cout<<"逐一输入边的顶点对，形如 3 5 "<<endl;  
    for(i=1;i<g.arcnum+1;i++)  
    {  
        cout<<"第"<<i<<"条边：";  
        fin>>b>>e;  
        p = new ArcNode();  
        p->adjvex = e;  
        p->nextarc = g.vertices[b].firstarc;  
        g.vertices[b].firstarc = p;  
        indegree[e]++;  
        cout<<endl;  
    }  
    if(TopologicalSort(g,indegree))cout<<"正常完成！"<<endl;  
    else cout<<"该有向图有回路！"<<endl;  
    return 0;  
}  
其实是一个拓扑排序实现偏序。

阔怀

{:1_1:}

飘渺463431810

来看看，学习一下