图-笔记

zz/2024/2/26 0:34:52

1.E是有向边也称为弧的有限集合时则图G为有向图E是无向边简称边的有限集合时则图G为无向图

2.n(n-1)/2条边的无向图称为完全图具有n(n-1)条弧的有向图称为有向完全图

3.简单路径序列中顶点不重复出线的路径称为简单路径

4.简单回路除了第一个顶点和最后一个顶点之外其余顶点不重复出线的回路称为简单回路或简单环

5.回路第一个顶点和最后一个顶点相同的路径称为回路或环

6.无向图中任意两个顶点都是连通的则称图G为连通图连通分量指的是无向图中的极大连通子图

7.有向图中G对于每一对Vi,Vj(Vi≠Vj),ViVj和从VjVi都存在路径则称G是强连通图

8.一个连通图的生成树是一个极小连通子图它含有途中全部顶点但只有足以构成一棵树的n-1条边一棵有n个顶点的生成树有且仅有n-1条边但有n-1条边的图不一定是生成树

9.用邻接矩阵构造一个具有n个顶点和e条边的无向网G的时间复杂度为O(n^2+e·n),其中对邻接矩阵的初始化耗费了O(n^2)的时间

10.若无向图中有n个顶点、e条边则它的邻接表需n个头结点和2e个表结点

11.图的遍历从图中某一顶点出发访遍图中其余顶点且使每一个顶点仅被访问一次这个过程就叫做图的遍历

12.对于同一个图基于邻接矩阵的遍历所得到的DFS序列和BFS序列式唯一的基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的

13.用邻接矩阵作图的存储结构时,DFSBFS的时间复杂度为O(n^2),用邻接表作图的存储结构时,DFSBFS的时间复杂度为O(n+e)。

14.判断有向图中是否存在回路拓扑排序和深度优先遍历算法

15.最小生成树不是唯一的即最小生成树的树形不唯一但最小生成树的代价即树上各边的代价之和是唯一的

16.Prim算法的时间复杂度为O(n^2),与网中的边数无关因此适用于求边稠密的最小生成树而克鲁斯卡尔算法的时间复杂度为O(eloge)(e为网中边的数目),适合于求边稀疏的最小生成树

17.拓扑排序:①在有向图中选一个没有前驱的顶点且输出之;②从图中删除该顶点和所有以它为尾的弧;③重复上述两步直至全部顶点均已输出或者当前图中不存在无前驱的顶点为止

18.拓扑排序的时间复杂度为:O(n+e).

19.AOV顶点表示活动弧表示活动间优先关系;AOE边表示活动

20.AOV网中的关键路径路径长度最长的路径关键路径上的所有活动都是关键活动因此提前完成非关键活动并不能加快工程的进度

21.关键路径的算法:(p184)

22.求关键路径的时间复杂度为O(n+e)。

23.迪杰斯特拉求单源最短路径的时间复杂度是O(n^2),弗洛伊德求每一对顶点之间的最短路径的时间复杂度为O(n^3)。


http://www.ngui.cc/zz/2689562.html

相关文章

《计算机网络》-数据链路层笔记及部分课后习题

第三章 3-1.数据链路(即逻辑链路)与链路(即物理链路)有何区别? “电路接通了”与”数据链路接通了”的区别何在? 答:数据链路与链路的区别在于数据链路出链路外,还必须有一些必要的规程来控制数据的传输,因此,数据链路比链路多…

c#数字华容道

代码如下: using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Threading.Tasks;using System.Windows.Forms;namespace WindowsFormsApp6{ …

从键盘输入一个年份,判断这一年是否为闰年

import java.util.Scanner; class Demo2 { public static void main(String[] args) { Scanner scnew Scanner(System.in); System.out.println("请输入一个年份:"); int yearsc.nextInt(); //判断是否为闰年 if((year%40&&year%100!0)||(yea…

练习把一个整数逆序输出

代码如下: /* 练习把一个整数逆序输出 分别把个位,十位,百位,千位等各位的数字取出来*/import java.util.Scanner;class Demo18 { public static void main(String[] args) { Scanner scnew Scanner(System.in); System.out.p…

定义方法,把一个偶数表示为两个素数之和

import java.util.Scanner; /* * 把一个偶数表示为两个素数之和 */ public class Demo33 { public static void main(String[] args) { Scanner scnew Scanner(System.in); System.out.println("请输入一个偶数:"); int nsc.nextInt(); ou(n); } public…

练习定义分数 类

如图所示,在一个包中定义两个类。通过创建对象实现类的调用 相关代码如下: package com.gradedefinition.demo01;public class Demo01 { public static void main(String[] args) { Fraction f1new Fraction(); //创建分数对象 f1.numerator3; f1.deno…

定义一个日期类:包括年、月、日三个成员变量,显示日期的方法

/*定义一个日期类:包括年、月、日三个成员变量,显示日期的方法 * 提供构造方法:定义无参构造方法,和有参构造方法 */ 代码如下: public class Demo { public static void main(String[] args) { Date date1…

单例设计模式编程练习

单例设计模式:是指在程序的运行过程中,只有一个实例的存在。 同一个类的若干对象需要访问同一个数据,这个数据保存在静态变量中; 如果不同的类的若干对象访问同一个数据,其中一个解决方案就是单例。 ① 把构造方法私有…

字父类中构造方法的调用练习

Person类:(父类) public class Person { private String name; private int age; public Person(){ this("李四", 20); } public Person(String name,int age){ this.namename; this.age…

集合的嵌套

代码如下: import java.util.HashMap;import java.util.Map;import java.util.Set;import java.util.Iterator;/*Map集合的嵌套,Map中存储的还是Map集合 *要求: * 传智播客 * java基础班: 001 张三 * …