技术标签: 数据结构
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
屏幕输出:
文章浏览阅读771次,点赞22次,收藏11次。只记得我在一个昏暗潮湿的地方喵喵地哭泣着。——夏目漱石《我是猫》到目前为止,我们看到的神经网络都是前馈型神经网络。(feedforward)是指网络的传播方向是单向的。具体地说,先将输入信号传给下一层(隐藏层),接收到信号的层也同样传给下一层,然后再传给下一层……像这样,信号仅在一个方向上传播。虽然前馈网络结构简单、易于理解,而且可以应用于许多任务中。不过,这种网络存在一个大问题,就是不能很好地处理时间序列数据(以下简称为“时序数据”)。
文章浏览阅读2.5k次。1本地数据传输类似cp的复制,实现文件,目录的增量复制。#语法模式rsync命令 参数 src源文件/目录 dest目标文件/目录1.本地文件复制# 复制hosts文件[root@chaogelinux ~]# rsync /etc/hosts /tmp/2.复制目录内容-r, --recursive 对子目录以递归模式处理# 复制/data下所有内容到/tmp[root@lb01 ~]# rsync -r /data/ /tmp/# 复制/data整个文件夹到/tmp_rsync本地拷贝
文章浏览阅读1.4k次,点赞3次,收藏11次。约瑟夫环问题: 问题描述:设有编号为1,2,3……n的n个人顺时针方向围坐一圈,每人有一密码(正整数)。开始时给出一初始密码m,从编号为1的人开始报数,报m的人出列;以后将出列者的密码作为新的m,从顺时针方向紧挨着他的下一个人开始报数……直至所有人出列。试编算法,求出出列顺序。要求:用不带头结点的单向循环链表实现从键盘输入n,m各人的密码由计算机随机产生(1~10的正整数,也可以自定义_py约瑟夫环问题n,k,m要求由键盘输入值,每个人持有的密码随机生成。 2、每个函数完
文章浏览阅读1.7k次,点赞21次,收藏17次。这项研究介绍了一种自主运动规划的新方法,在Frenet坐标系内用强化学习(RL)代理通知分析算法。这种结合直接解决了自动驾驶中适应性和安全性的挑战。运动规划算法对于导航动态和复杂的场景至关重要。然而,传统方法缺乏不可预测环境所需的灵活性,而机器学习技术,特别是强化学习(RL),提供了适应性,但存在不稳定性和缺乏可解释性。我们独特的解决方案将传统运动规划算法的可预测性和稳定性与RL的动态适应性相结合,使系统能够有效地管理复杂的情况并适应不断变化的环境条件。_frenetix rl
文章浏览阅读335次。springboot整合shardingshere+druid 读写分离和分库分表,mybatis-plus_spring.shardingsphere.sharding.master-slave-rules
文章浏览阅读1.5k次,点赞2次,收藏4次。OSPF特殊区域NSSA配置实验一、实验目的二、实验内容三、实验流程四、查看和验证**OSPF特殊区域NSSA和Total NSSA配置实验总结:**一、实验目的1.掌握OSPF协议的工作原理及其LSA的类型划分;2.掌握OSPF特殊区域的概念、分类和特点;3.掌握路由器中OSPF特殊区域NSSA区域的基本配置方法和结果验证;二、实验内容完成思科路由器OSPF特殊区域NSSA区域的基本配置和结果验证;三、实验流程(一)配置任务说明如下图所示:区域0是骨干域,将区域1设置为nssa区域,完成_ospf naas区域实验
离散数学中的命题逻辑,包括命题的表示和联结词的运用,推理理论和常用的证明方法,如真值表法和直接证明法。还介绍了附加前提证明法或CP规则。
文章浏览阅读8.6k次。Spring Expression Language(SpEL)spring的一种表达式。用来动态的获取,值、对象等。 样式: #{ …} 使用既定的规则放置在花括号中。式中的规则得以运行,可以反馈结果。理论上可以返回任何类型。 说说两种方式去设置SpELAnnotation注解。@Value()方便快捷。 你可以在里面方式任何符合SpEL规范的语句,并把它的返回值注..._spring expression language
文章浏览阅读1.7k次。ansible最大并发 Ansible是一种功能强大的无代理(但易于使用且轻巧)的自动化工具,自2012年推出以来一直稳步流行。这种流行在一定程度上是由于其简单性。 默认情况下,Ansible的最基本依赖项(Python和SSH)几乎在所有地方都可用,这使得Ansible可以轻松用于各种系统:服务器,工作站,Raspberry Pi,工业控制器,Linux容器,网络设备等。 Ansible可..._ansible 提升 高并发
文章浏览阅读479次。应我的客户要求,需要找到一款可以在极短时间识别二维条码的软件以应对他们现在极其迅速的货品入库需求。正好听说过一款Dynamsoft Barcode Reader的开发包,根据其官网介绍最新版对条码检测速度比以前的版本快2倍以上。根据对Dynamsoft Barcode Reader8.8SDK包拆解,其中含了JavaScript Package /.NET Package /C/C++ Package /Python Package /Java Package /iOS Package /A..._barcode reader
文章浏览阅读1.2k次。前人栽树,后人乘凉,文章参考https://blog.csdn.net/TsingSee/article/details/108618054,我要感谢此博客主,mediasoup-demo很多文章都是关于在linux系统下的,很多在windows都有问题,而唯独此博客主的文章正确。我学习此博客的文章对比才知道主要问题在于三点:1.node,npm版本最好是要高版本的。2.python版本问题,这个是最关键的,一定不能是python3版本,我这里用的是TSING博客主建议的python-v2.7.17_npm安装那个版本最好
文章浏览阅读1.0k次。关于Spacy安装遇到的错误_pip install spacy python -m spacy download en_vectors_web_lg