技术标签: 数据结构
1.课程设计内容与要求
用字符文件提供数据建立AOE网络的存储结构。编写程序,计算并输出工程的最短完成时间。
实验目的:掌握图的存储结构;掌握图的拓扑排序算法以及AOE网络顶点最早开始时间的计算方法。
1.课程设计内容与要求
用字符文件提供数据建立AOE网络的存储结构。编写程序,计算并输出工程的最短完成时间。
实验目的:掌握图的存储结构;掌握图的拓扑排序算法以及AOE网络顶点最早开始时间的计算方法。
程序采用C++语言进行开发,完成用字符文件提供数据建立AOE网络的存储结构,计算并输出工程的最短完成时间。
程序使用邻接表结构来存储图数据结构,借助栈数据结构完成对图的正逆拓扑排序,并求出个顶点的最早开始时间和最晚开始时间,最后计算并输出工程的最短完成时间。
执行过程如下:
关于拓扑排序,先初始化两个存储int类型下标的栈,st用于存储入度为0的点,topOrder用于存储拓扑排序的顺序,先将所有入度为0的点存入st中,若栈st中存在入度为0的结点,则继续进行拓扑排序,从栈顶弹出一个图中的顶点,存入topOrder中,遍历该顶点的所有邻接点, 先使所有邻接点的入度减一(逻辑上做删除操作),判断入度是否为0,为0则压入栈st中,如果邻接点事件的的最早发生时间小于当前顶点事件的最早发生时间加上当前顶点到邻接点的权值,则将邻接点的最早发生时间更新为当前顶点事件的最早发生事件加上两点间活动持续时间。将栈topOrder中的元素依次弹出,获得拓扑排序的逆序列,求解last数组,初始化所有事件的最迟开始时间数组last为汇点的最早发生时间,获取栈顶元素并遍历当前顶点的所有临接点,如果邻接点事件的最晚发生时间大于当前顶点事件的最晚发生时间减去当前顶点到邻接点的权值,则将邻接点的最晚发生时间更新为当前顶点事件的最晚发生时间减去两点间活动持续时间。
求解关键路径,就是遍历当前顶点的邻接点,如果最早发生时间和最晚发生时间相同的话,说明当前活动是关键活动,则输出当前活动,并从p->adjVertex出发寻找下一个关键活动,当前顶点事件邻接点的最晚开始时间减去当前活动[u, p -> adjacencyVertex]的权值就是当前活动的最晚开始时间,求得一关建路径后退出。
创建链表结点的结构体ArcNode,
成员变量int adjVertex,为该弧所指向的顶点的位置,
int weight表示有向边的路径长度(权值),
struct ArcNode* nextArc;指向下一个和头结点存在有向边的链表结点。
创建顶点结点结构体VertexNode,
成员变量,char data 存储结点上的数据,
ArcNodePtr firstArc,指向该顶点结点的第一个链表结点。
2.创建ALGraph类
成员变量:AdjList vertexes,表示图,early数组记录每个事件的最早发生时间,last数组记录每个事件的最晚发生时间。vexNum表示图中顶点的数量,arcNum表示边的数量,minTime表示工程的最短完成时间。
再定义一系列相关的成员函数,
void addEdge(ALGraph* g, int u, int v, int w);
用头插法在编号为u, v的顶点间增加一条边。
void createALGraph(ALGraph* g);
从文件输入中创建邻接表存储的有向图。
void getInDegree(ALGraph* g, int* inDegree);
求图中每个顶点的入度。
void topOrder(ALGraph* g);
拓扑排序求early和last。
void getCriticalPath(ALGraph* g, int u, int& minTime);
求解关键路径。
void criticalPath(ALGraph* g);
求解最短完成时间。
3.输入文件test01.txt格式
9 11 (结点数 边数)
0 1 6 (结点序号, 邻接点, 有向边的权值)
......
7 8 4 (共9个)
4.输出在屏幕上的信息
early数组和last数组的值,关键路径与工程完成所需的最短时间。
getInDegree(g, inDegree);求每个顶点的入度数组inDegree,
for (int i = 0; i < g->vexNum; ++i)
if (!inDegree[i]) st.push(i);先将所有入度为0的点存入st中,
while (!st.empty()) { 若栈st中存在入度为0的结点,则继续进行拓扑排序,
int curVex = st.top();
topOrder.push(curVex);
st.pop();
遍历该顶点的所有邻接点
for (ArcNodePtr p = g->vertexes[curVex].firstArc; p != nullptr; p = p->nextArc) {
先使所有邻接点的入度减一(逻辑上做删除操作)
if (!(--inDegree[p->adjVertex]))
如果入度减一后该邻接点的入度为0,则加入栈st中作为下一次排序的起点
st.push(p->adjVertex);
如果邻接点事件的的最早发生时间小于当前顶点事件的最早发生时间加上当前顶点到邻接点的权值,则将邻接点的最早发生时间更新为当前顶点事件的最早发生事件加上两点间活动持续时间,
if (early[curVex] + p->weight > early[p->adjVertex])
early[p->adjVertex] = early[curVex] + p->weight;}}
for (int i = 0; i < g->vexNum; i++) 初始化所有事件的最迟开始时间数组last为汇点的最早发生时间,
last[i] = early[g->vexNum - 1];
while (!topOrder.empty()) {
int curVex = topOrder.top();
topOrder.pop();
for (ArcNodePtr p = g->vertexes[curVex].firstArc; p; p = p->nextArc) {
如果邻接点事件的最晚发生时间大于当前顶点事件的最晚发生时间减去当前顶点到邻接点的权值, 则将邻接点的最晚发生时间更新为当前顶点事件的最晚发生时间减去两点间活动持续时间。
if (last[p->adjVertex] - p->weight < last[curVex])
last[curVex] = last[p->adjVertex] - p->weight;}}
算法复杂度:对有n个顶点和e条弧的有向图而言,建立求各顶点的入度的时间复杂度为O(e);建零入度顶点栈的时间复杂度为O(n);在拓扑排序过程中,若有向图无环,则每个顶点进一次栈、出一次栈,入度减1的操作在while语句中总共执行e次,所以总的时间复杂度为O(n+e)。 拓扑排序初始参数只有邻接表,所以第一步建立入度数组,因为每1入度对应一条弧,总共e条弧,建立入度数组的复杂度为O(e)。每个节点输出一次,n个节点遍历一次,时间复杂度为O(n)。然后节点入度减1的操作,也是一条弧对应一次,e条弧总共O(e)。即对每条弧要建立入度数组操作和删除操作,每个顶点要遍历一次并删除。故时间复杂度为O(n+e)。
遍历当前顶点u的所有邻接点
for (ArcNodePtr p = g->vertexes[u].firstArc; p != nullptr; p = p->nextArc) {
如果最早发生时间和最晚发生时间相同的话,说明当前活动是关键活动,则输出当前活动,并从p->adjVertex出发寻找下一个关键活动, 当前顶点事件邻接点的最晚开始时间减去当前活动[u, p -> adjacencyVertex]的权值就是当前活动的最晚开始时间,
if (early[u] == last[p->adjVertex] - p->weight) {
minTime += p->weight;
vec.push_back(u); 将关键活动存入vec中,
vec.push_back(p->adjVertex);
getCriticalPath(g, p->adjVertex, minTime);递归寻找下一个关键活动
找到一条关键路径,结束循环
break;}}
算法时间复杂度为:O(n+e)。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
using namespace std;
#define MAX_VERTEX_NUM 20
// 链表结点
typedef struct ArcNode {
// 该弧所指向的顶点的位置
int adjVertex;
// 有向边的路径长度(权值)
int weight;
// 下一个和头结点存在有向边的链表结点
struct ArcNode* nextArc;
}ArcNode, * ArcNodePtr;
// 顶点结点
typedef struct VertexNode {
// 存储结点上的数据
char data;
// 指向该顶点结点的第一个链表结点
ArcNodePtr firstArc;
}AdjList[MAX_VERTEX_NUM];
class ALGraph
{
public:
ALGraph() = default;
// early数组记录每个事件的最早发生时间
int early[MAX_VERTEX_NUM] = { 0 };
// last数组记录每个事件的最晚发生时间
int last[MAX_VERTEX_NUM] = { 0 };
// 存储图上所有顶点的数组
AdjList vertexes;
// 图中顶点的数量、边的数量
int vexNum, arcNum;
// 定义minTime表示工程的最短完成时间
int minTime = 0;
vector<int> vec ;
void addEdge(ALGraph* g, int u, int v, int w);
void createALGraph(ALGraph* g);
void getInDegree(ALGraph* g, int* inDegree);
void topOrder(ALGraph* g);
void getCriticalPath(ALGraph* g, int u, int& minTime);
void criticalPath(ALGraph* g);
~ALGraph() = default;
};
// 用头插法在编号为u, v的顶点间增加一条边
void ALGraph::addEdge(ALGraph* g, int u, int v, int w) {
// 创建一个新的链表结点
ArcNodePtr p = new ArcNode();
// 有向边的狐头
p->adjVertex = v;
// 新结点指向头结点后继
p->nextArc = g->vertexes[u].firstArc;
// 有向边<u,v>的权值
p->weight = w;
// 头结点指向新结点
g->vertexes[u].firstArc = p;
}
// 从文件输入中创建邻接表存储的有向图
void ALGraph::createALGraph(ALGraph* g) {
// 文件输入
ifstream input("test01.txt");
// 输入顶点数和边数
input >> g->vexNum >> g->arcNum;
// 输入每个顶点的值并初始化指针为nullptr
for (int i = 0; i < g->vexNum; ++i) {
//让顶点存储的数据为顶点的编号
g->vertexes[i].data = i + '0';
g->vertexes[i].firstArc = nullptr;
}
// 读入<u, v>的一条带权有向边
for (int i = 0; i < g->arcNum; ++i) {
int u, v, w;
input >> u >> v >> w;
addEdge(g, u, v, w);
}
}
// 求图中每个顶点的入度
void ALGraph::getInDegree(ALGraph* g, int* inDegree) {
// 遍历图
for (int i = 0; i < g->vexNum; ++i)
for (ArcNodePtr p = g->vertexes[i].firstArc; p != nullptr; p = p->nextArc)
// 每条有向边的终点顶点入度加一
inDegree[p->adjVertex]++;
}
// 拓扑排序求early和last
void ALGraph::topOrder(ALGraph* g) {
// 每个结点的入度初始化为0
int inDegree[MAX_VERTEX_NUM] = { 0 };
// 求每个顶点的入度数组inDegree
getInDegree(g, inDegree);
// 初始化两个存储int类型下标的栈,st用于存储入度为0的点,topOrder用于存储拓扑排序的顺序
stack<int> st, topOrder;
// 先将所有入度为0的点存入st中
for (int i = 0; i < g->vexNum; ++i)
if (!inDegree[i]) st.push(i);
// 若栈st中存在入度为0的结点,则继续进行拓扑排序
while (!st.empty()) {
// 从栈顶弹出一个图中的顶点,存入topOrder中
int curVex = st.top();
topOrder.push(curVex);
st.pop();
// 遍历该顶点的所有邻接点
for (ArcNodePtr p = g->vertexes[curVex].firstArc; p != nullptr; p = p->nextArc) {
if (!(--inDegree[p->adjVertex]))
// 如果入度减一后该邻接点的入度为0,则加入栈st中作为下一次排序的起点
st.push(p->adjVertex);
if (early[curVex] + p->weight > early[p->adjVertex])
early[p->adjVertex] = early[curVex] + p->weight;
}
}
//初始化所有事件的最迟开始时间数组last为汇点的最早发生时间
for (int i = 0; i < g->vexNum; i++)
last[i] = early[g->vexNum - 1];
while (!topOrder.empty()) {
// 获取栈顶元素
int curVex = topOrder.top();
topOrder.pop();
// 遍历当前顶点的所有邻接点
for (ArcNodePtr p = g->vertexes[curVex].firstArc; p; p = p->nextArc) {
if (last[p->adjVertex] - p->weight < last[curVex])
last[curVex] = last[p->adjVertex] - p->weight;
}
}
// 输出所有顶点的early值
cout << "early: ";
for (int i = 0; i < g->vexNum; ++i)
cout << early[i] << " ";
// 输出所有顶点的last值
cout << endl << "last: ";
for (int i = 0; i < g->vexNum; ++i)
cout << last[i] << " ";
}
// 求解关键路径
void ALGraph::getCriticalPath(ALGraph* g, int u, int& minTime) {
// 遍历当前顶点u的所有邻接点
for (ArcNodePtr p = g->vertexes[u].firstArc; p != nullptr; p = p->nextArc) {
if (early[u] == last[p->adjVertex] - p->weight) {
minTime += p->weight;
// 将关键活动存入vec中
vec.push_back(u);
vec.push_back(p->adjVertex);
getCriticalPath(g, p->adjVertex, minTime);
// 找到一条关键路径,结束循环
break;
}
}
}
void ALGraph::criticalPath(ALGraph* g) {
cout << endl << "关键路径:";
getCriticalPath(g, 0, minTime);
for (int i = 0; i < vec.size(); i = i + 2) {
cout << "V" <<vec[i] <<"->";
}
cout << "V" << vec[vec.size() - 1];
cout << endl << "工程最短完成时间: " << minTime;
}
int main() {
ALGraph* G = new ALGraph();
G->createALGraph(G); // 创建图的图的邻接表存储
G->topOrder(G); //拓扑排序
G->criticalPath(G); //求关键路径
G->~ALGraph();
return 0;
}
test01.txt文件输入为:
7 8
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
4 6 7
5 6 4
屏幕输出:
文章浏览阅读3.1k次。1. 打开配置文件Mac 如下图2. 在文件内部添加这段文字,就可以了:"update_check":false _mac sublime text 取消更新提示
文章浏览阅读548次,点赞10次,收藏6次。Linux系统下DNS配置指南_linux 服务器修改网络dns
文章浏览阅读779次,点赞19次,收藏24次。springboot微信小程序的小疾病问诊服务系统的设计与实现。springboot基于spring的物业管理系统的设计与实现。springboot基于Java的高校学生请假系统。ssm基于Android的购物商场APP设计与实现。springboot基于微信小程序的智慧校园系统。ssm基于Android的英语词典的设计与开发。ssm基于SSM+Vue的学生实践管理平台开发。ssm基于android的企业员工考勤系统。ssm基于web的暗香小店系统的设计与实现。ssm基于Web的高等学校公费医疗管理系统。
文章浏览阅读2.3w次,点赞15次,收藏63次。hover属性用不同的书写方式,来改变不同关系的元素样式。元素:hover 表示聚焦后改变自己元素:hover 元素 表示聚焦后改变其子元素元素:hover + 元素 表示聚焦后改变其指定的“亲兄弟”(条件是该兄弟元素与其相邻)元素元素:hover ~ 元素 表示聚焦后改变其指定的兄弟元素,两个元素相不相邻都行。示例:.first:hover {color: white;}/* 聚焦我改变自己 */.three:hover .three-son {font-size: 20px._css hover的用法
文章浏览阅读6k次,点赞3次,收藏15次。coursera-斯坦福-机器学习-吴恩达-第8周笔记-无监督学习coursera-斯坦福-机器学习-吴恩达-第8周笔记-无监督学习1聚类算法clutering1聚类算法简介2K-means21kmeans的目标函数22随机初始化23选择类别数3考试quiz维数约减 dimensionality reduction1数据压缩2数据可视化3维度约简-主成分分析法PCA1 PCA_pca反向压缩
文章浏览阅读5.2k次。一、插件安装Vundle是vim的一个插件管理器, 同时它本身也是vim的一个插件。插件管理器用于方便、快速的安装、删除、Vim更新插件。mkdir -p ~/.vim/bundlegit clone https://github.com/gmarik/Vundle.vim.git ~/.vim/bundle/Vundle.vim管理器安装完成后,vim ~/.vimrc命令创建.vimrc文件syntax on" tab宽度和缩进同样设置为4set tabstop=4set softta_bxbx.vim
文章浏览阅读226次,点赞2次,收藏3次。本项目设计了一款可以触摸控制的天气显示器。主要由Wemos D1 Mini Pro和TFT显示屏组成,利用Wemos D1 Mini Pro作为设备的主控芯片,发出Wi-Fi信号并接收相应指令,通过调用API将接收到的信息传输到TFT显示屏,TFT显示屏将接收到的信息显示出来。该天气显示器实现对所在地区当前的时间与日期;当日的天气信息,如温度、压力、湿度、降雨量;七天的未来预测等功能的显示。设计采用Wemos D1 Mini Pro,利用API将实时获取的天气信息,通过TFT显示屏显示出来。_arduino wemos d1 mini
文章浏览阅读653次。public void initDiffDisplay() { try { DisplayManager displayManager = (DisplayManager) getSystemService(Context.DISPLAY_SERVICE); Display[] presentationDisplays = displayManager.getDisplays(); if (presentationDi._android service 检测是否双屏
文章浏览阅读530次,点赞23次,收藏10次。springboot+mybatisplus+mysql 用户端 uniapp(vue语法)管理后台 vue+elementUi。后台服务 springboot+mybatisplus+mysql。一、我们技术使用JAVA后台服务 前后端分离。管理后台 vue+elementUi。用户端 uniapp(vue语法)适配小程序+H5+公众号。私信客服获取演示地址。私信客服获取演示地址。
文章浏览阅读3.3k次,点赞3次,收藏5次。# -*- coding: UTF-8 -*-year = int(input("输入一个年份:"))if year % 100 == 0: if year % 400 == 0: print('%d年是闰年' % year) else: print('%d年不是闰年' % year)else: if year % 4 == 0: print('%d年是闰年' % year) else: print('%d_判断闰年的python程序直接输入一个代表年份的正整数
文章浏览阅读987次,点赞20次,收藏19次。偏微分方程PDE图像去噪(含SNR)完整的代码,方可运行;可提供运行操作视频!适合小白!_pdnet 深度学习 偏微分方程 去噪
文章浏览阅读6.6w次,点赞128次,收藏962次。Ubuntu18.0详尽版安装教程下载Ubuntu18.04下载VMware Workstation安装虚拟机下载Ubuntu18.04官方网站:http://old-releases.ubuntu.com/releases/18.04.4/?_ga=2.44113060.1243545826.1617173008-2055924693.1608557140下载VMware Workstation这个在网上有很多教程下载,这里我就不写了,我用的版本是14 pro。如下图:安装虚拟机1、打开_ubuntu18安装