1. 编程号首页

c++有向图实现_若一个有向图的邻接矩阵

编程小号 • • 未分类

c++有向图实现_若一个有向图的邻接矩阵给定一个工程项目的施工流程图，并给出其每项子工程所需的时间，请设计程序判断该施工进展图能否顺利执行？如果能，需求出完成整项工程所需的最短工期，并给出影响整个工程中的可能影响工期的最关键的子工程是哪些

题目描述：给定一个工程项目的施工流程图，并给出其每项子工程所需的时间，请设计程序判断该施工进展图能否顺利执行？如果能，需求出完成整项工程所需的最短工期，并给出影响整个工程中的可能影响工期的最关键的子工程是哪些。

功能要求及说明：

（1）构建图：工程施工流程图的相关信息可从文件读入，项目至少有11个子工程组成。

（2）流程图检测： 判断该施工流程图能否顺利进行；

（3）求最短工期：若该项目施工流程图能顺利进行，输出完成整个项目所需要的最短工期；

（4）求最关键的子工程：给出每一个最关键的子工程及其最早开工时间；

（5）采用模块化设计，菜单界面简洁清晰。

具体要求如下：

  1. 对现实复杂问题中的数据对象特性及组织方法进行分析和研究，设计适当的数据逻辑结构、存贮结构以及相应运算操作，把现实世界问题建模转化为计算机内部表示并进行处理。
  2. 采取模块化方式进行程序设计，要求程序的功能设计、数据结构设计及整体结构设计合理。学生也可根据自己对题目的理解增加新的功能模块。
  3. 系统以菜单界面方式（至少采用文本菜单界面，如能采用图形菜单界面更好）工作，运行界面友好，演示程序以用户和计算机的对话方式进行，利用文件进行数据的提取与存储。
  4. 程序算法说明清晰，理论分析与计算正确，运行情况良好，实验测试数据无误，容错性强（能对错误输入进行判断控制）。
  5. 编程风格良好（包括缩进、空行、适当注释、变量名和函数名见名知意，程序容易阅读等）；

先给代码，后面做说明解释。 

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

using namespace std;

#define MVNum 100

int topo[MVNum];        //定义拓扑排序数组
typedef float OtherInfo;//权值为float类型工程可以设置小数
typedef char VerTexType;

typedef struct ArcNode {      //边结点
    int adjvex;               //该边所指向的顶点的位置
    struct ArcNode *nextarc;  //指向下一条边的指针
    OtherInfo info;           //和边相关的信息
} ArcNode;

typedef struct VNode {
    VerTexType data;      //顶点信息
    ArcNode *firstarc;    //指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNum];  //AdjList表示邻接表类型

typedef struct {
    AdjList vertices;   //邻接表
    int vexnum, arcnum; //图的当前顶点数和边数
} ALGraph;

typedef struct StackNode {//链栈的相关定义
    int data;
    StackNode* next;
}StackNode, *LinkStack;

int InitStack(LinkStack &S) {//栈的初始化
    S = NULL;
    return 1;
}

int Push(LinkStack &S,int e) {//入栈
    LinkStack p;
    p = new StackNode;
    p->data = e;
    p->next = S;
    S = p;
    return 1;
}

int Pop(LinkStack &S,int &e) {//出栈
    LinkStack p;
    p = new StackNode;
    if (S == NULL)
        return  0;
    e = S->data;  //将栈顶元素带出
    p = S;      //用P临时存放栈顶元素，以备释放
    S = S->next;
    free(p);
    return 1;
}

int GetTop(LinkStack S) {//取栈顶元素
    if (S != NULL)
        return S->data;
    return -1;
}

int StackEmpty(LinkStack S) {//判断栈是否为空
    if (S != NULL)
        return 0;
    else
        return 1;
}

int LocateVex(ALGraph &G,VerTexType vex){//确定顶点vex在G.vertices中的序号
    for(int i=0;i<G.vexnum;i++){
        if(G.vertices[i].data == vex){
            return i;
        }
    }
    return 0;
}

int CreateDAG(ALGraph &G){//采用邻接表法创建有向无环图G
    ifstream fileIn;//文件打开、遍历
    fileIn.open("D:\\数据结构课程设计\\工程.txt",ios::in);
    if(!fileIn){
        cout<<"error:没有找到该工程图"<<endl;
        exit(1);
    }
    fileIn>>G.vexnum;cout<<"图总顶点数:"<<G.vexnum<<endl;
    fileIn>>G.arcnum;cout<<"图总边数:"<<G.arcnum<<endl;
    for(int i = 0;i<G.vexnum;i++){
        fileIn>>G.vertices[i].data;
        cout<<"第"<<i+1<<"个顶点:"<<G.vertices[i].data<<endl;
        G.vertices[i].firstarc=NULL;//初始化表头结点的指针域为NULL
    }
    for(int k = 0;k<G.arcnum;k++){//输入各边构造邻接表
        int weight;fileIn>>weight;
        cout<<"第"<<k+1<<"条边的权值:"<<weight<<" ";
        VerTexType v1,v2;
        fileIn>>v1;cout<<"依附的第一个顶点:"<<v1<<" ";
        fileIn>>v2;cout<<"依附的第二个顶点:"<<v2<<endl;
        int i = LocateVex(G,v1); int j = LocateVex(G,v2);//确定v1和v2在G中的位置
        ArcNode *P1;//结点初始化
        P1 = new ArcNode;//生成一个新的边结点P1
        P1->adjvex = j;//邻接点序号为j
        P1->info = weight;//权值赋值给info
        P1->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = P1;//将新结点*P1插入顶点vi的边表头部
    }
    fileIn.close();
    return 1;
}

void FindInDegree(ALGraph G,int indegree[]){
    //求每个顶点入度存入数组indegree[]
    //遍历整个邻接表求入度
    ArcNode *p;
    int i;
    for(i = 0;i<G.vexnum;i++)//入度初始化为0
        indegree[i] = 0;
    for(i = 0;i<G.vexnum;i++){//邻接表遍历
        p = G.vertices[i].firstarc;
        while (p != NULL) {
            indegree[p->adjvex]++;//入度加1
            p = p->nextarc;
        }
    }
}

int TopologicalSort(ALGraph G,int topo[]){
    //图无回路生成扑排序结果数组topo[]并返回1,有回路则返回0
    int i;
    ArcNode *p;
    LinkStack S;InitStack(S);//定义栈并初始化
    int indegree[MVNum];
    FindInDegree(G,indegree);//求顶点入度并存入数组indegree
    cout<<"顶点入度为:";
    for(i = 0;i<G.vexnum;i++){
        cout<<indegree[i];
    }
    cout<<endl;
    for(i = 0;i<G.vexnum;i++){
        if(indegree[i] == 0)
            Push(S,i);//入度为0的顶点入栈
    }
    int count = 0;//统计个数确认是否全部打印
    while (!StackEmpty(S)) {
        Pop(S,i);//将栈顶顶点Vi出栈
        topo[count] = i;//Vi存入topo数组中
        count++;//计数加一
        p = G.vertices[i].firstarc;//p指向第一个邻接点
        while(p != NULL){
            int k = p->adjvex;//Vk设为Vi邻接点
            indegree[k]--;//Vi的每个邻接点入度减1
            if(indegree[k] == 0)
                Push(S,k);//入度为0则入栈
            p = p->nextarc;//p指向下一个邻接点
        }
    }
    if(count<G.vexnum){//计数小于顶点个数说明有回路
        cout<<"---------工程图有回路，请检查工程----------"<<endl;
        return 0;
    }
    else{
        cout<<"------------该工程能顺利进行-------------"<<endl;
        return 1;
    }
}

int CriticalPath(ALGraph G){
    //输出G的各项关键活动
    ArcNode *p;
    int ve[MVNum];//最早发生时间
    int vl[MVNum];//最迟发生时间
    int i,j,k,vet,vlt;
    ofstream fileout;
    fileout.open("D:\\数据结构课程设计\\结果.txt",ios::out|ios::ate|ios::app);
    if(!TopologicalSort(G,topo)){//调用拓扑排序算法，使拓扑序列保存在topo中
        return 0;//若调用失败，则存在有向环，返回0
    }
    int n = G.vexnum;//顶点个数
    for(i=0;i<n;i++)
        ve[i] = 0;//事件最早发生时间置为0
    //-----按拓扑次序求每个事件的最早发生时间-----//
    for(i=0;i<n;i++){
        k = topo[i];//取得拓扑序列中顶点序号k
        p = G.vertices[k].firstarc;//p指向k第一个邻接点
        while (p != NULL) {//依次更新k的所有邻接点的最早发生时间
            j = p->adjvex;//j为邻接顶点序号
            if(ve[j]<ve[k]+p->info)//更新顶点j的最早发生时间
                ve[j] = ve[k]+p->info;
            p = p->nextarc;//p指向k的下一个邻接点
        }
    }
    for(i=0;i<n;i++)//给每个事件的最迟发生时间初值置为ve[n-1]（即最早发生时间）
        vl[i]=ve[n-1];
    cout<<"最短工期为:"<<ve[n-1]<<"天"<<endl;
    fileout<<"最短工期为:"<<ve[n-1]<<"天"<<endl;
    //-----按逆拓扑次序求每个事件的最迟发生时间-----//
    for(i=n-1;i>=0;i--){
        k = topo[i];//取得拓扑序列中顶点序号k
        p = G.vertices[k].firstarc;//p指向k第一个邻接点
        while (p != NULL) {//依次更新k的所有邻接点的最迟发生时间
            j = p->adjvex;//j为邻接点序号
            if(vl[k]>vl[j]-p->info)//更新顶点k的最迟发生时间
                vl[k]=vl[j]-p->info;//取小值，否则会延误工期，需要考虑其他路线
            p = p->nextarc;//p指向k的下一个邻接点
        }
    }
    //-----判断每一活动是否为关键活动-----//
    cout<<"关键路径如下:"<<endl;
    for(i=0;i<n;i++){
        p = G.vertices[i].firstarc;//p指向k第一个邻接点
        while (p != NULL) {
            j = p->adjvex;//j为邻接顶点序号
            vet = ve[i];//计算活动<vi,vj>的最早开始时间,相当于边的最早发生时间
            vlt = vl[j]-(p->info);//计算活动<vi,vj>的最迟开始时间
            if(vet == vlt){//若为关键活动，输出关键活动最早时间和<vi,vj>
                cout<<"<"<<G.vertices[i].data<<","<<G.vertices[j].data<<">"
                   <<"为关键活动最早时间为"<<vet<<"天"<<endl;
                fileout<<"<"<<G.vertices[i].data<<","<<G.vertices[j].data<<">"
                   <<"为关键活动最早时间为"<<vet<<"天"<<endl;
            }
            p = p->nextarc;//p指向i的下一个邻接顶点
        }
    }
    fileout<<"<---------------以上为本次工程计算结果------------------->"<<endl;
    fileout.close();//关闭文件
    cout<<" ->结束"<<endl;
    return 1;
}

void userGuide(){//用户指引
    cout<<"这是一个计算工程能否进行并计算最短工期和关键工程的程序:"<<endl;
    cout<<"1.请将工程文件放于D:\\数据结构课程设计\\工程.txt"<<endl;
    cout<<"2.工程结果会在运行程序上显示，同时结果会存入文件(若没有则自动生成)D:\\数据结构课程设计\\结果.txt"<<endl;
    cout<<"3.工程的txt文件格式请先输入图总顶点数，图总边数，顶点信息，"
          "再循环输入权值，依附的第一个顶点和第二个顶点顺序输入。数据之间为空格或换行"<<endl;
}

void menu(){//菜单
    cout<<"---------菜单----------"<<endl;
    cout<<"输入1、创建工程图"<<endl;
    cout<<"输入2、判断工程能否顺利进行"<<endl;
    cout<<"输入3、计算关键路径和最短工期"<<endl;
    cout<<"输入0、退出程序"<<endl;
    cout<<"-----------------------"<<endl;
    cout<<"请输入你的选择:";
}

int main()
{
    int x;
    ALGraph G;
    userGuide();
    while (1) {
        menu();//菜单
        cin>>x;//用户选择
        switch (x) {
            case 1:{//创建图结构
                if(CreateDAG(G))
                    cout<<"---------创建成功----------"<<endl;
                else
                    cout<<"---------创建失败----------"<<endl;
                break;
            }
            case 2:{//拓扑排序
                if(TopologicalSort(G,topo)){
                    cout<<"拓扑排序结果如下:"<<endl;
                    for(int i = 0;i<G.vexnum;i++)
                        cout<<G.vertices[topo[i]].data<<"->";
                    cout<<"完成"<<endl;
            break;
                }
            }
            case 3:{//关键路径和最短工期
                CriticalPath(G);
                break;
            }
            case 0:exit(0);//退出程序
        }
    }
    return 0;
}

 喜欢的话点个关注~~

需求分析

1、输入数据

输入的数据由程序自动读入工程图并显示在窗口，所以不需要用户输入数据，只需要选择相应选项使程序运行。

2、输出数据

读入数据后，在窗口输出每个子工程时间，并可以判断工程能否完工，检查是否有错误，无错误则可以求最短工期与关键子工程，给出每一个最关键的子工程及其最早开工时间，并将结果写入相应文件。

3、施工流程图构建与检测

构建图需要用邻接矩阵或者邻接表，因为需要求拓扑排序与关键活动，且图有向无环，使用邻-接表法较为简单高效，因此采用邻接表法创建有向无环图G。

同时要求工程从文件读入，所以需要用到C++相关的<sstream>，<fstream>头文件相关语句ifstream，open等用来读取相关工程图数据。同时结果要写入文件，需要用ofstream和ios::out|ios::ate|ios::app用于输出结果到文件。

判断该施工流程图能否顺利进行，即是在创建完图后求顶点入度，判断拓扑排序，需要在拓扑排序里判断工程图是否存在回路，若有则返回0，否则返回1。

4、求最短工期与关键子工程

求最短工期需要先求顶点入度，再求图的拓扑排序，同时需要用到栈做辅助。确定关键路径，求各个工程的最早开始时间和最晚开始时间，根据最早开始时间和最晚开始时间确定关键活动，得到关键路径，即最关键的子工程，再输出工程的最早开工时间。同时也可以确定最短工期。

5、程序设计提示

（1）构建图：工程施工流程图的相关信息可从文件读入，项目至少有11个子工程组成。

（2）流程图检测：判断该施工流程图能否顺利进行。

（3）求最短工期：若该项目施工流程图能顺利进行，输出完成整个项目所需要的最短工期。

（4）求最关键的子工程：给出每一个最关键的子工程及其最早开工时间。

（5）采用模块化设计，菜单界面简洁清晰。

概要设计

1、图结构及存储结构

定义有向邻接表图结构，边结点，顶点信息，和边相关的信息，图的当前顶点数和边数，同时定义好相应指针以便对邻接表进行操作和数据保存。

1.定义工程结点

typedef struct ArcNode {      //边结点

    int adjvex;               //该边所指向的顶点的位置

    struct ArcNode *nextarc;  //指向下一条边的指针

    OtherInfo info;           //和边相关的信息

} ArcNode;

2.定义工程结构，邻接表类型

typedef struct VNode {

    VerTexType data;      //顶点信息

    ArcNode *firstarc;    //指向第一条依附该顶点的边的指针

} VNode, AdjList[MVNum];  //AdjList表示邻接表类型

3.定义工程图

typedef struct {

    AdjList vertices;   //邻接表

    int vexnum, arcnum; //图的当前顶点数和边数

} ALGraph;

2、辅助栈定义

   定义链栈和相关函数。初始化，基本的入栈出栈，取栈顶元素，判断栈是否为空。用于求顶点入度与拓扑排序。

1.定义链栈

typedef struct StackNode {//链栈的相关定义

    int data;

    StackNode* next;

}StackNode, *LinkStack;

2.初始化栈

int InitStack(LinkStack &S) {//栈的初始化

    S = NULL;

    return 1;

}

3.定义入栈

int Push(LinkStack &S,int e) {//入栈

    LinkStack p;

    p = new StackNode;

    p->data = e;

    p->next = S;

    S = p;

    return 1;

}

4.定义出栈

int Pop(LinkStack &S,int &e) {//出栈

    LinkStack p;

    p = new StackNode;

    if (S == NULL)

        return  0;

    e = S->data;  //将栈顶元素带出

    p = S;      //用P临时存放栈顶元素，以备释放

    S = S->next;

    free(p);

    return 1;

}

4.定义取栈顶元素

int GetTop(LinkStack S) {//取栈顶元素

    if (S != NULL)

        return S->data;

    return -1;

}

int StackEmpty(LinkStack S) {//判断栈是否为空

    if (S != NULL)

        return 0;

    else

        return 1;

}

3、功能函数说明

int   CreateDAG(ALGraph &G)采用邻接表法创建有向无环图G。

int   LocateVex(ALGraph &G,VerTexType vex)确定顶点vex在G.vertices中的序号 。

void   FindInDegree(ALGraph G,int indegree[])求每个顶点入度存入数组indegree[]。

int TopologicalSort(ALGraph G,int topo[]) 图无回路生成扑排序结果数组topo[]并返回1,有回路则返回0。

int CriticalPath(ALGraph G)输出G的各项关键活动。

void userGuide()用户指引函数。

void menu()用户菜单菜单。

int StackEmpty(LinkStack S) 判断栈是否为空

int Pop(LinkStack &S,int &e) 出栈

int GetTop(LinkStack S) 取栈顶元素

int Push(LinkStack &S,int e) 入栈

int InitStack(LinkStack &S)初始化栈

主函数中使用while循环和switch语句，用户让可以选择程序运行方向和重复运行程序代码。

4、主要算法思想

1.创建图：用ifstream打开工程文件、遍历，读取文件内容，输入图总顶点数，图总边数，边的权值依附的第一个顶点，依附的第二个顶点，确定两个顶点在G中的位置，生成一个新的边结点，权值赋值，将新结点*P1插入顶点vi的边表头部，返回1代表创建成功。即成功创建图。

2.求入度：遍历整个邻接表求入度，求每个顶点入度存入数组indegree[]，之后即可求拓扑排序。

3.判断工程能否进行：定义栈并初始化，求顶点入度并存入数组indegree，入度为0的顶点入栈，统计个数确认是否全部打印，将栈顶顶点Vi出栈，存入topo数组中，计数增加，Vk设为Vi邻接点，每个邻接点入度减1，入度为0再入栈，再指向下一个邻接点，循环直到遍历完成。计数小于顶点个数说明有回路，输出提示并返回0，否则该工程能顺利进行，返回。

4.求最短工期：按拓扑次序求每个事件的最早发生时间，所以要先调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回0。取得拓扑序列中顶点序号，指向依次更新顶点的所有邻接点的最早发生时间第一个邻接点，更新顶点的最早发生时间，指向下一个邻接点，循环直到遍历完成。

给每个事件的最迟发生时间初值置为最早发生时间ve[n-1]，所以最短工期为ve[n-1]。

5.求关键子工程：按逆拓扑次序求每个事件的最迟发生时间，取得拓扑序列中顶点序号。依次更新所有邻接点的最迟发生时间，更新顶点的最迟发生时间（注意取小值，否则会延误工期，需要考虑其他路线）指向下一个邻接点，循环直到遍历完成。

3. 判断每一活动是否为关键活动，计算活动<vi,vj>的最早开始时间,相当于边的最早发生时间，判断vet == vlt，若为关键活动，输出关键活动最早时间和<vi,vj>，指向下一个邻接点，循环直到遍历完成。

测试结果

1、工程无回路能否创建

 c++有向图实现_若一个有向图的邻接矩阵

图创建成功，邻接表正确

c++有向图实现_若一个有向图的邻接矩阵

2、工程有回路能否创建

一个简单的ABCD四个顶点五条边循环图。

图创建成功，邻接表正确

c++有向图实现_若一个有向图的邻接矩阵

3、工程无回路能否正常运行

1.判断该工程能否进行，判断正确，工程能顺利进行。

2.拓扑排序与顶点入度正确

c++有向图实现_若一个有向图的邻接矩阵

2.求最短工期与关键子工程，输出正确。

c++有向图实现_若一个有向图的邻接矩阵

结果写入文件，成功

c++有向图实现_若一个有向图的邻接矩阵

4、工程有回路能否正常运行

   提示工程有回路，输出正确

 c++有向图实现_若一个有向图的邻接矩阵

 测试数据

//测试数据1，成功的
11 14 A B C D E F G H I J K 5 A B 6 A C 3 B D 6 C D 3 C E 3 D E 4 D F 1 E G 4 E H 5 G I 2 H I 4 F J 2 I J 2 J K
//测试数据2，失败的有向有环图
4 5 A B C D 1 A B 1 B C 1 C D 1 D A 1 A B

今天的文章c++有向图实现_若一个有向图的邻接矩阵分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/89436.html

赞 (0)
编程小号编程小号
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注