【数据结构】拓扑网络(AOE算法举例+源码)

简介: 【数据结构】拓扑网络(AOE算法举例+源码)

一、拓扑网络定义

拓扑网络是计算机网络中的一个重要概念,指的是连接在一起的网络设备之间的物理或逻辑结构。拓扑结构决定了网络中各个节点之间的连接方式,对网络的性能、可靠性和扩展性都有重要影响。

1. 什么是拓扑网络?

拓扑网络描述了计算机网络中设备之间的连接方式,包括它们之间的物理布局或逻辑结构。这种结构定义了网络中数据流动的路径,以及各个节点之间的关系。拓扑网络的选择直接影响了网络的性能、可靠性和维护难度。

2. 常见的拓扑结构

2.1 星型拓扑

星型拓扑所有设备都连接到一个中心节点(如交换机或集线器)。这种结构简单易于维护,但如果中心节点故障,整个网络可能受到影响。

2.2 总线拓扑

总线拓扑中,所有设备都连接到一根共享的传输介质,如一根电缆。数据通过总线传输,但当设备数量增加时,总线可能成为瓶颈。

2.3 环形拓扑

环形拓扑中,设备通过连接成一个环形。数据沿着环路传输,但如果某个设备出现故障,可能会导致整个网络中断。

2.4 网状拓扑

网状拓扑中,每个设备都连接到网络中的其他设备,形成多条路径。这种结构具有高度的冗余和可靠性,但是布线复杂,成本较高。

2.5 混合拓扑

混合拓扑是以上拓扑的组合形式,可以根据网络的需求和规模选择不同的结构。

二、拓扑网络的应用

拓扑网络广泛应用于各种领域,包括企业网络、数据中心、云计算等。在实际应用中,需要根据具体情况权衡各种因素,选择最合适的拓扑结构来构建网络。

三、AOE算法

AOE(Activity On Edge)算法是一种用于求解工程网络中最早开始时间和最晚开始时间的算法。工程网络是一种用图表示的项目计划,其中节点表示活动,有向边表示活动之间的依赖关系。AOE算法通常用于项目管理,帮助确定项目中各个活动的最早和最晚开始时间,以及关键路径。

以下是AOE算法的主要步骤:

  1. 绘制工程网络图: 根据项目计划,绘制工程网络图,其中节点表示活动,有向边表示活动之间的依赖关系。
  2. 确定活动持续时间: 为每个活动确定其持续时间,并将这些信息标记在相应的节点上。
  3. 确定事件的最早开始时间(ES): 从网络的起始节点开始,按照拓扑排序的顺序,计算每个事件(节点)的最早开始时间。对于每个活动,最早开始时间等于其所有前驱活动的最早完成时间的最大值。
  4. 确定活动的最早开始时间和最早完成时间(EF): 根据最早开始时间,计算每个活动的最早开始时间和最早完成时间。最早完成时间等于最早开始时间加上活动持续时间。
  5. 确定事件的最晚完成时间(LF): 从网络的终点节点开始,按照逆拓扑排序的顺序,计算每个事件的最晚完成时间。对于每个活动,最晚完成时间等于其所有后继活动的最晚开始时间的最小值。
  6. 确定活动的最晚开始时间和最晚完成时间(LS): 根据最晚完成时间,计算每个活动的最晚开始时间和最晚完成时间。最晚开始时间等于最晚完成时间减去活动持续时间。
  7. 计算活动的浮动时间: 活动的浮动时间是指活动可以推迟的时间,而不影响整个项目的完成时间。浮动时间等于最晚开始时间减去最早开始时间。
  8. 找到关键路径: 关键路径是指总浮动时间为零的路径,即对整个项目的完成时间有最大影响的路径。关键路径上的活动是项目的关键活动。

 

#include<iostream>
#include<string.h> 
using namespace std;
 
#define pointMax 100
 
struct VtNode                 //权值信息
{
  VtNode *nextVt;           //入度链表下一个结点
  int peace;                //入度下一顶点的值
 
  VtNode *nextVtt;          //出度链表下一个结点
  int peaceE;               //出度下一顶点的值
 
  int len;
};
struct PoNode                  //顶点信息
{
  char data;
  VtNode *firstPo;          //入度
  VtNode *Out;              //出度
};
 
struct ATgroup
{
  PoNode vertices[pointMax];     //每一个verticse代表一个顶点
  int point, vert;               //point顶点数,vert弧数
};
 
struct Node
{
  int data;
  Node *next;
};
 
struct SqStack          //栈
{
  Node *base;          //栈底
  Node *top;           //栈顶
  int data;
};
 
void Push(SqStack &S, int i)       //入栈
{
  Node *m = new Node;
  m->data = i;
  m->next = S.top;             //入栈过程
  S.top = m;
}
 
int Pop(SqStack &S)              //出栈
{
  int n = S.top->data;
  S.top = S.top->next;         //出栈过程
  return n;
}
 
 
int ATlocate(ATgroup A, char x)             //找到位置
{
  for (int i = 0; i < A.point; i++)       //依次遍历点的信息
  {
    if (A.vertices[i].data == x)        //找到x的位置
    {
      return i;
    }
  }
}
 
void show(ATgroup &A)                      //显示当前所有点入度出度的顶点
{
  //cout << endl;
  for (int i = 0; i < A.point; i++)
  {
    //cout << i;
    if (A.vertices[i].firstPo != NULL)          //入度位置
    {
    //  cout << "    " << A.vertices[i].firstPo->peace << "   ";
    }
    //else
    //  cout << "    -1" << "    ";
 
    if (A.vertices[i].Out != NULL)             //出度位置
    {
    //  cout << A.vertices[i].Out->peaceE << endl;
    }
    //else
    //  cout << "    -1" << endl;
  }
}
 
void CreatAT(ATgroup &A)
{
  cout << "输入邻接矩阵顶点数:";
  cin >> A.point;
  cout << "输入邻接矩阵边数:";
  cin >> A.vert;
  getchar();
  char q[100];
  cout << "输入顶点信息:";
  gets(q);
//  这里作了一个修改 
  for (int i = 0; i < A.point; i++)
  {
    A.vertices[i].data = q[i];               //输入顶点值
    A.vertices[i].firstPo = NULL;            //初始化头结点为空
    A.vertices[i].Out = NULL;
  }
  char v1, v2; int m, n; int len;
  for (int i = 0; i < A.vert; i++)            //输入各边,构造邻接表
  {
    cout << "输入第" << i << "条边的依附的两个顶点:";
    int Q;
    cin >> v1 >> v2 >> Q;
    m = ATlocate(A, v1);                  //确定位置
    n = ATlocate(A, v2);
    //第一个
    VtNode *p1 = new VtNode;
    VtNode *p2 = new VtNode;
    p1->peace = m;                             //入度
    p1->nextVt = A.vertices[n].firstPo;
    A.vertices[n].firstPo = p1;
 
    p2->peaceE = n;                            //出度
    p2->nextVtt = A.vertices[m].Out;
    p2->len = Q;
    A.vertices[m].Out = p2;
  }
  //show(A);
}
 
void FindIn(ATgroup *A, int *in)           //统计所有点的入度数并存入到in数组中
{
  int n = 0;
  for (int i = 0; i < A->point; i++)     //遍历每一个点
  {
    VtNode *p = new VtNode;
    p = A->vertices[i].firstPo;
    while (p != NULL)                  //将入度链表进行遍历
    {
      n++;
      p = p->nextVt;          //下一结点
    }
    in[i] = n;          //存入in数组
    n = 0;
  }
}
 
void SHOW(int *a, ATgroup *A)           //显示当前所有顶点入度数量还有几个
{
  for (int i = 0; i < A->point; i++)
  {
    //cout << a[i] << "  ";
  }
  //cout << endl;
}
 
int M[pointMax] = { 0 };
int topo[pointMax];           //拓扑遍历存入
 
void TPsort(ATgroup *A, SqStack &S)           //拓扑排序过程
{
  int Indegree[pointMax];
  FindIn(A, Indegree);             //将入度赋值给数组
 
  for (int i = 0; i < A->point; i++)
  {
    if (Indegree[i] == 0)         //将所有入度等于0的入栈
    {
      //cout << "Push=" << i << endl;
      Push(S, i);
    }
  }
 
  int m = 0;                //统计入度的顶点数
  int n, k;
 
  while (S.base != S.top)       //判断是否遍历完
  {
    //cout << endl;
    n = Pop(S);         //栈顶出栈
    //cout << "Pop=" << n << endl;
    topo[m] = n;        //存入topo
    m++;
    VtNode* p = new VtNode;
    p = A->vertices[n].Out;             //出度链表的结点
    while (p != NULL)            //遍历出度链表
    {
      k = p->peaceE;          //某结点的位置
      //cout << "出度下一结点k=" << k << endl;
      Indegree[k]--;          //将该结点顶点位置入度减一
      //SHOW(Indegree, A);       //显示当前所有点的入度
      if (Indegree[k] == 0)      //当等于0时,入栈
      {
        //cout << "Push=" << k << endl;
        Push(S, k);
      }
      p = p->nextVtt;     //下一个
    }
  }
}
 
 
 
int ve[pointMax];      //最早发生时间
int vl[pointMax];      //最晚发生时间
 
void CritPath(ATgroup *A)
{
  int n = A->point;          //n为顶点个数
  for (int i = 0; i < n; i++)        //将每个事件的最早事件为0
    ve[i] = 0;
 
  //---按拓扑次序求每个事件的最早发生时间---//
  int k, j;
  for (int i = 0; i < n; i++)
  {
    k = topo[i];                 //取的拓扑排序中的顶点序号
    cout <<"K=F"<< k << "  "<<endl;
    VtNode *p = A->vertices[k].Out;     //指向K的第一个邻接结点
    while (p != NULL)
    {
      j = p->peaceE;
      if (ve[j] < ve[k] + p->len)
      {
        ve[j] = ve[k] + p->len;
        cout << ve[j] << "  " << ve[k] << "   " << p->len << endl;
      }
      p = p->nextVtt;
    }
    cout << ve[j] << endl;
  }
  for (int i = 0; i < A->point; i++)
  {
    cout << ve[i] << "   ";
  }
  cout << endl;
  cout << endl;
 
  for (int i = 0; i < n; i++)       //初始化
  {
    vl[i] = ve[topo[n - 1]];
  }
  //---按逆拓扑排序求每个事件的最迟发生时间----//
  for (int i = n - 1; i >= 0; i--)
  {
    k = topo[i];                 //取的拓扑排序中的顶点序号
    VtNode *p = A->vertices[k].Out;     //指向K的第一个邻接结点
    //cout << k << endl;
    while (p != NULL)
    {
      j = p->peaceE;
      if (vl[k] > vl[j] - p->len)
      {
        vl[k] = vl[j] - p->len;
        //cout << vl[k] << "  " << vl[j] << "   " << p->len << endl;
      }
      p = p->nextVtt;
    }
    //cout << vl[j] << endl;
  }
 
  for (int i = 0; i < A->point; i++)
  {
    cout << vl[i] << "   ";
  }
  cout << endl;
  cout << endl;
 
  //----判断每一活动是否为关键活动-----//
  int e, l;
  for (int i = 0; i < n; i++)
  {
    VtNode *p = A->vertices[i].Out;
    while (p != NULL)
    {
      j = p->peaceE;
      e = ve[i];
      l = vl[j] - p->len;
      if (e == l)
      {
        cout << A->vertices[i].data << "   " << A->vertices[j].data << endl;
      }
      p = p->nextVtt;
    }
  }
}
 
int main()
{
  ATgroup *A = new ATgroup;
  SqStack *S = new SqStack;
  S->top = S->base;
  S->data = pointMax;
  CreatAT(*A);
  TPsort(A, *S);
  CritPath(A);
  system("pause");
}

 


相关文章
|
5天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
64 9
|
24天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
61 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
4天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
43 16
|
4天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
32 8
|
7天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
32 4
|
8天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
32 3
|
11天前
|
机器学习/深度学习 人工智能 算法
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
车辆车型识别,使用Python作为主要编程语言,通过收集多种车辆车型图像数据集,然后基于TensorFlow搭建卷积网络算法模型,并对数据集进行训练,最后得到一个识别精度较高的模型文件。再基于Django搭建web网页端操作界面,实现用户上传一张车辆图片识别其类型。
33 0
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
|
13天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-LSTM网络的数据分类识别算法matlab仿真
本项目展示了基于贝叶斯优化(BO)的CNN-LSTM网络在数据分类中的应用。通过MATLAB 2022a实现,优化前后效果对比明显。核心代码附带中文注释和操作视频,涵盖BO、CNN、LSTM理论,特别是BO优化CNN-LSTM网络的batchsize和学习率,显著提升模型性能。
|
21天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
31 4
|
24天前
|
Java C++ 索引
让星星⭐月亮告诉你,LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表,适合频繁的插入和删除操作,但按索引访问元素效率较低。`ArrayList` 基于动态数组,支持快速随机访问,但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口,`LinkedList` 还额外实现了 `Deque` 接口,提供了更多队列操作。
21 3