首页 > 其他分享 >数据结构之图

数据结构之图

时间:2023-04-27 17:23:20浏览次数:34  
标签:AOE 源点 活动 路径 顶点 数据结构 网中 之图

定义

 

无向图、有向图

 

 子图、入度、出度

 连通图、强连通图

 

 总结:

连通无向图的最小生成树中,顶点数 = 边数 + 1 

强连通有向图的 边数 至少等于 顶点数。

 

AOV网

AOV网(顶点表示活动的网)顶点表示活动,弧表示活动发生优先关系的有向图。在AOV网中,通过进行拓扑排序可以得到一个有序序列或可以判断出该图中是否存在有向环。

AOE网

AOE网(边表示活动的网)是一个带权的有向无环图,其中顶点表示事件,弧表示活动,权表示活动持续的时间。通常,AOE网可以用来估算工程的完成时间。在一个工程AOE网中,应该不存在回路,网中有且仅有一个入度为0的顶点,称做源点(或开始点),用来表示整个工程的开始;有且仅有一个出度为0的顶点,称做汇点(或结束点),用来表示整个工程的结束。而且在AOE网中,有些活动可以并行地执行,所以完成工程的最短时间是从源点(开始点)到汇点(结束顶点)的最长路径的长度(路径长度即指路径上各种活动持续时间之和)。路径长度最长的路径就称为关键路径。

通常,AOE网可以用来估算工程的完成时间。关键路径是指AOE网中从源点到汇点(结束顶点)的最长路径。

 

标签:AOE,源点,活动,路径,顶点,数据结构,网中,之图
From: https://www.cnblogs.com/htj10/p/17359414.html

相关文章

  • 数据结构——并查集
    并查集的作用:可以在近乎O(1)的时间内完成以下两个操作1、将两个集合合并2、询问两个元素是否在一个集合中 基本原理:用“树”的形式来维护每一个集合,树根的编号就是整个集合的编号,每个结点存储它的父结点(如:p[x]表示x的父结点)问题1:如何判断树根?  A:if(p[x]==x),当前x就是......
  • OpenJ_Bailian 4081 树的转换 数据结构
    题目:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=412663题意:我们都知道用“左儿子右兄弟”的方法可以将一棵一般的树转换为二叉树,如:00/|\/123===>1/\......
  • 山东大学数据结构实验11 搜索树
    描述创建带索引的二叉搜索树类。存储结构使用链表,提供操作:插入、删除、按名次删除、查找、按名次查找、升序输出所有元素。格式输入格式输入第一行一个数字m(m<=1000000),表示有m个操作。接下来m行,每一行有两个数字a,b:当输入的第一个数字a为0时,输入的第二个数字b表示......
  • 山东大学数据结构实验10 堆及其应用
    内容创建最小堆类。最小堆的存储结构使用数组。提供操作:插入、删除、初始化。题目第一个操作是建堆操作,接下来是对堆的插入和删除操作,插入和删除都在建好的堆上操作。格式输入第一行一个数n(n<=5000),代表堆的大小。第二行n个数,代表堆的各个元素。第三行一个数m(m<=1000),代......
  • 山东大学数据结构实验9 二叉树操作
    描述创建二叉树类。二叉树的存储结构使用链表。提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。格式输入格式第一行为一个数字n(10<=n<=100000),表示有这棵树有n个节点,编号为1~n。之后n行每行两个数字,第i行的两个数字a、b表示编号......
  • 山东大学数据结构实验8 散列表
    要求使用线性开型寻址实现描述给定散列函数的除数D和操作数m,输出每次操作后的状态。有以下三种操作:插入x,若散列表已存在x,输出“Existed”,否则插入x到散列表中,输出所在的下标。查询x,若散列表不含有x,输出“-1”,否则输出x对应下标。删除x,若散列表不含有x,输出“NotFound”,否......
  • C++数据结构(树)
    树是一种递归定义的数据结构,如果树中节点的各子树从左到右是有次序的,不能互换,则称该树为有序树,否则叫无序树。关于树的节点:节点拥有的子树的个数叫做节点的度如果度为0,那么该节点叫做叶节点或终端节点,除了根节点外的分支节点称为内部节点树的度是各节点度的最大值。节点的子......
  • 什么是数据结构?
    数据结构研究计算机数据间关系,包括数据的逻辑结构和存储结构及其操作。我们接触一种数据结构,一定要掌握这三个方面基本概念1.数据(Data)数据即信息的载体,是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称。2.数据元素(DataElement)数据......
  • 初识数据结构
    什么是数据结构,数据结构可以理解为我们规定数据元素之间具有某种关系或规则,程序员根据这些规则能够更好的管理和操作这些数据。数据元素的关系包括三种:线性关系——1:1线性关系即为数据是一对一的关系,即除了开头的数据元素和最后的数据元素,其他如何应该数据元素有......
  • 2023年电子科技大学ACM-ICPC暑假前集训-数据结构
    Preface学校针对大一新生的暑假前集训的第一个专题DS,由于要求集体写题解就顺便把写好的发上来了由于下面都写了题意所以直接看也能有很多收获,当然非电专的学生的话就没法交题了代码的话由于专题还没结束怕放上来然后被CV导致被爆破,所以应该在这周六专题结束后会放上来下面都是......