鱼C论坛

 找回密码
 立即注册
查看: 4265|回复: 3

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

[复制链接]
发表于 2015-1-26 02:05:10 | 显示全部楼层 |阅读模式
10鱼币
编程实现由偏序集合构造全序集合,最好能用C或C++编写,谢谢了
最佳答案
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;  
}  
其实是一个拓扑排序实现偏序。

最佳答案

查看完整内容

#include #include #include using namespace std; ifstream fin("in.txt"); #define MAX_VERTEX_NUM 26 stack 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 ...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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;  
}  
其实是一个拓扑排序实现偏序。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-9 10:36:34 | 显示全部楼层
{:1_1:}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-1-7 15:35:59 | 显示全部楼层
来看看,学习一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 21:45

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表