文件

文件是性质相同的记录的集合。
记录是文件中存取的基本单位,数据项是文件可使用的最小单位。
操作系统研究的文件是一维的无结构连续字符序列,数据库中研究的文件是带有结构的记录集合。

文件在外存上的4种基本组织方式:顺序、索引、散列、链(多关键字)。
磁带和磁盘分别是顺序存取设备和直接存取设备。

顺序文件

顺序文件按记录进入文件的顺序存储。
顺序有序文件和顺序无序文件。
顺序文件多用在磁带上。

索引文件

索引表指明逻辑记录和物理记录的对应关系,索引表和主文件一起构成索引文件,在存储器上分为索引区和数据区。
主文件分为索引顺序文件和索引非顺序文件,索引非顺序文件适合随机存取,索引顺序文件适合于顺序存取。
索引表分为稠密索引和稀疏索引。
还可以对索引表建立索引,称为查找表。查找表可以有多级。
这种多级顺序表索引是一种静态索引。而动态索引采用二叉排序树、AVL树、B-树等树表结构,插入和删除方便。

索引顺序文件

两种常用的索引顺序文件:ISAM文件和VASM文件。
ISAM:索引顺序存取方法,为磁盘存取设计,采用静态索引结构。ISAM文件由多级主索引、柱面索引、磁道索引、主文件组成。
VSAM:虚拟存储存取方法,采用B+树作为动态索引结构。VSAM文件由索引集、顺序集、数据集组成。

散列文件

也称为直接存取文件,散列文件主要采用拉链法处理冲突。
散列文件只能按关键字随机存取,不能顺序存取。

多关键字文件

多重表文件,对每个次关键字也建立一个索引,并且将具有相同次关键字的记录的物理地址链接起来,次关键字索引表的一条记录包括次关键字、链表的头指针、链表长度。
倒排文件,与多重表文件相比,倒排文件把链表的物理地址放在了次关键字索引表中了。
与单关键字索引文件相比,倒排文件是按给定次关键字查找记录,而不是在已查找记录中找次关键字。

概论

1946年首台计算机ENIAC问世。
计算机软件相对硬件发展缓慢。软件的核心是算法,算法是加工数据的过程。
数据的存储结构是逻辑结构用计算机语言的实现。本课程数据结构主要是讨论存储结构,并且我们只在高级语言的层次上讨论存储结构。

时间复杂度

时间复杂度是省去了系数的,平均查找长度则是有系数的。
n!的算法的时间复杂度是O(n)。
{i=s=0;while(s<=n){i++;s+=i;}}时间复杂度O(n1/2)

docker-php

测试docker下nginx + php-fpm

部署配置文件
/alidata/docker_work/nginx/下
conf目录中存放nginx-vhost配置文件
ssl目录中存放ssl证书
www目录中存放html和php文件

nginx-vhost配置文件,其中/host会在启动时被映射到主系统/alidata/docker_work/nginx/目录,php-fpm-alias是容器php-fpm1的别名,也可以使用php-fpm1的地址。

server {
        listen 80;
        listen 443 ssl;

        #server_name localhost;
        server_name  www.
xxx.cn;

        ssl_certificate /host/ssl/wwkssl.crt;
        ssl_certificate_key /host/ssl/wwkssl.key;

        index index.html index.htm index.php;

        #root /alidata/docker_work/nginx/www;
        root /host/www/brogrammer;

        location ~ .*\.(php|php5)?$
        {
                #fastcgi_pass  unix:/tmp/php-cgi.sock;
                fastcgi_pass  php-fpm-alias:9000;
                fastcgi_index index.php;
                #include fastcgi.conf;
                include fastcgi_params;
                fastcgi_param SCRIPT_FILENAME $document_root$fastcgi_script_name;
                #fastcgi_param SCRIPT_NAME $fastcgi_script_name;
        }
        location ~ .*\.(gif|jpg|jpeg|png|bmp|swf)$
        {
                expires 30d;
        }
        location ~ .*\.(js|css)?$
        {
                expires 1h;
        }

        #include /alidata/server/nginx/conf/rewrite/default.conf;
        #access_log  /alidata/log/nginx/access/default.log;
}

启动服务

#启动php-fpm。一定要加上项目文件目录映射,否则访问web页面会报File not found。
docker run --name php-fpm1 -v /alidata/docker_work/nginx/www:/host/www -d bitnami/php-fpm

#启动nginx。其中会link上php-fpm1。
docker run --name nginx1 -p 81:80 -p 444:443 --link php-fpm1:php-fpm-alias -v /alidata/docker_work/nginx/conf:/etc/nginx/conf.d -v /alidata/docker_work/nginx:/host -d nginx

破解Docker初学者的迷惑,多容器配合实现开发环境(nginx、php、memcached、mysql)
http://www.arkulo.com/2015/04/25/dockerlnmp/

Spring Boot 异步

当某个请求执行非常耗时,当有大量访问该请求的时候,再访问请求其他服务时,会出现没有连接使用的情况。造成这种现象的主要原因是,容器中线程的数量是一定的,例如500个,当这500个线程都正在用来处理请求服务的时候,再有请求进来,没有多余的连接可用了,只能拒绝连接。

SpringBoot异步机制可以使请求到controller中时,容器线程直接返回,同时使用系统内部的线程来执行耗时的服务,处理结束后果再将请求返回给客户端。

Servlet 3.0 新增了请求的异步处理,Spring 3.2 也在此基础上做了封装处理。
Spring通过任务执行器(TaskExecutor)来实现多线程和并发编程。使用ThreadPoolTaskExecutor可实现一个基于线程池的TaskExecutor。Executor框架是在 Java 5 中引入的,其内部使用了线程池机制。

在 Spring Boot 框架中,可以在配置类中添加@EnableAsync开始对异步任务的支持,并将相应的方法使用@Async注解来声明为一个异步任务。

对于@Transactional、@Async等注解,spring扫描时具有这些注解方法的类时,生成一个代理类,由代理类去执行,所以异步方法必须在类外部调用,并且@Async所修饰的不能是static方法。获取得到执行结果则可设置异步函数返回类型为Future。

@Component  
public class MyAsyncTask {  
    @Async  
    public Future task1() throws InterruptedException{  
        return new AsyncResult("task1执行完毕");  
    }  

Controller的方法可以很快返回一个java.util.concurrent.Callable或Deferredresult,同时Servlet容器的主线程退出和释放,这并不意味着客户端收到了一个响应。

//Callable
@Controller
public class DefaultController {
    @RequestMapping("/async/test")
    @ResponseBody
    public Callable callable() {
        //调用后生成一个非web线程来执行部分代码。
        return new Callable() {
            @Override
            public String call() throws Exception {
                Thread.sleep(3 * 1000L);
                return "finish" + System.currentTimeMillis();
            }
        };
    }
}

//DeferredResult
@RestController  
public class AsyncDeferredController {  
    private final TaskService taskService;  
      
    @Autowired  
    public AsyncDeferredController(TaskService taskService) {  
        this.taskService = taskService;  
    }  
      
    @RequestMapping(value = "/deferred", method = RequestMethod.GET, produces = "text/html")  
    public DeferredResult executeSlowTask() {  
        DeferredResult deferredResult = new DeferredResult<>();  
        CompletableFuture.supplyAsync(taskService::execute).whenCompleteAsync((result, throwable) -> deferredResult.setResult(result));  

        return deferredResult;  
    }  
}  

Callable的其它示例:

 public static void main(String[] args) throws ExecutionException, InterruptedException {
        Callable callable = new CallableImpl("my callable test!");
        FutureTask task = new FutureTask<>(callable);
        new Thread(task).start();
        //调用get()会阻塞主线程。
        String result = task.get();
    }

Callable和Deferredresult的区别:
Callable和Deferredresult效果都是释放容器线程,在另一个线程中运行长时间的任务。不同的是谁管理执行任务的线程:Callable在执行线程完毕时返回;Deferredresult是通过设置返回对象值返回,可以在任何地方控制返回。

https://blog.csdn.net/he90227/article/details/52262163
Spring MVC 异步处理请求,提高程序性能

定时任务

1.在程序入口类上添加类注解 @EnableScheduling 来启用计划任务
2.在定时任务的类上加上类注解 @Component,在具体的定时任务方法上加上注解 @Scheduled 启动该定时任务。
@Scheduled(initialDelay=10000, fixedDelay=10000) //10 seconds, or use cron express

默认所有的@Scheduled都是串行执行的,并行需要继承SchedulingConfigurer类并重写其方法,实现并行任务。

@Configuration
@EnableScheduling
public class ScheduleConfig implements SchedulingConfigurer {
    @Override
    public void configureTasks(ScheduledTaskRegistrar taskRegistrar) {
        taskRegistrar.setScheduler(taskExecutor());
    }

    @Bean(destroyMethod="shutdown")
    public Executor taskExecutor() {
        return Executors.newScheduledThreadPool(100);
    }
}

测试发现,RestController中接收处理请求每次所处的线程不一样,Mqtt处理请求也是单独的线程。

详解SpringBoot Schedule配置
http://www.cfei.net/archives/88832
Spring Boot 异步请求(Servlet 3.0)
https://blog.csdn.net/catoop/article/details/51034866

线性表

Linear List,运算受限的线性表
Sequential List
Link List

在表长为n的顺序表中插入一个数据元素,平均需要移动约n/2个数据元素。这句话是指顺序表中低地址区已经连续存在了n个元素了,并且其空间可以无限增大。插入元素的位置可以是n个元素现有的位置及其右侧的一个位置,则可选插入位置数是n+1。对于删除操作,可选删除位置数是n。

出栈和取栈顶元素操作是分开的。
顺序表实现的栈,元素出栈后不用free。
顺序表的岗哨是在n个元素之外的位置上。

数组

数组是线性表的一种推广。
二维数组a[m][n],每个元素占k个存储单元,以行序为主序的存储中,a[i][j]的位置索引L=i*n+j,存储地址loc[i,j]=loc[0,0]+L*k。

矩阵的压缩存储

对称矩阵:满足n阶方阵中a[i,j]=a[j,i],以行为主序存储下三角中的元素,a[i,j]的位置K:
当i>=j,即下三角中的元素,k=i(i+1)/2+j;
当i<j,即上三角中的元素,k=j(j+1)/2+i;

三角矩阵:上(下)三角矩阵的下(上)三角全为固定值。
上三角矩阵中前i行的元素个数=i(2n-i+1)/2。a[i,j]的位置K:
当i<=j,即上三角中的元素,k=i(2n-i+1)/2+j-i;
当i>j,即下三角中的元素,k=n(n+1)/2;
下三角矩阵中a[i,j]的位置K:
当i>=j,即下三角中的元素,k=i(i+1)/2+j;
当i<j,即上三角中的元素,k=n(n+1)/2;

顺序栈初始top=0,此时栈空。用了一个元素空间来表示栈底,实现数组的空间MaxSize值比栈空间大小多一个。

已知栈的输入顺序,判断给出的输出顺序的可能性,快速方法是:把输入序列和输出序列做一段消除,若消除后的结果相同,则有可能为真。消除的这一段序列是在输出序列中头部或尾部的一段,在输入序列中是正序连续或逆序连续的子序列。消除后的结果不能是输入顺序的右边部分。

队列

非循环顺序队列,为记忆数组索引关系,可以理解为队头出口开在了顺序栈的底部。并且也用了一个元素空间来指示队首。
链队列头指针头结点指向队列首元素。
循环队列长度=(rear-front+Max) % Max;

信息系统开发与管理

题型要点

1.数据流图题型要点
把流程描述中的动词转为加工处理。
处理和存储分别标上Pn和Dn。
系统内的参与者根据其是否有承接的处理操作来决定其是否需要出现在图中,或出现其处理操作。
数据流不能是生产实物,一般是单据等。
加工处理生成的信息如果主动传递到其它环节,而是由其它环节主动使用,则将此生成信息归档。例如:制作的记账凭证、登记的会计账簿。
除了开头和结尾的数据源点和终点,流程中间可能也会出现外部实体,也可能会没有终点的外部实体。例如:申请采购流程中间的供应商发货,输出发货单…
外部实体也可能出现在加工处理环节和文件节点之间。即加工处理依据的数据也可能来自外部实体。
2.模块结构图题型要点
题图的含义是,上方的主模块调用下方的各个子模块,来实现功能。明确了调用方向,就明确了数据方向。
多个数据同时传递时,注意它们可能有顺序要求。
模块结构图中主模块对子模块的调用是从左到右的顺序。
3.实体关系图和数据库逻辑模式题型要点
实体关系图中在实体间写上关系的名称,根据要求看是否要在实体上加上其各个属性。
对于多对多的关系,要设计其数据库逻辑模式,其主键是组合字段,它可能也有自己的属性。
数据库逻辑模式中主键要加上下划线。
4.数据流图->变换分析->简单模块结构图
主模块的三个从属模块,从左到各分别是:输入模块、变换模块、输出模块。

软件开发工具题型要点

1.应用题题型要点
应用题中如果函数需要在其实现之前调用,则需要在调用有对其声明。
2.年代题题型要点
60年代初,高级程序设计语言成熟和普及,计算机走出难以应用的困窘局面;此阶段也称为程序设计自动化;
60年代末,非过程化语言思想出现;结构化程序设计思想产生;人们认识到“软件危机”问题;
70年代,Smalltalk语言出现;
70年代末,利用通用软件作为辅助工具的阶段开始
80年代以来,专用软件开发工具陆续问世;时序网络得到了广泛应用;软件工具(软件工程)的思想与方法广泛宣传;
80年代初期,宁波软件学术会议
80年代中期,软件开发工具兴起,专项的、支持某一工作环节的专用工具大量涌现;
80年代末,人们发现了专用开发工具的弱点,提出了一体化的要求,一体化的趋势明显;1989年IBM的AD/Cycle理论框架标志着进入集成软件开发环境阶段。
90年代,软件开发进入了大量应用软件开发工具的阶段
90年代,1992年已有30余种一体化开发工具产品推向市场;1994年IBM停止了AD/Cycle计划;1994年UML工作在Rational公司开始,1997年Rational提出了UML。
21世纪以来,软件开发工具发展到了互联网阶段;软件开发进入了规模更大、应用更广的阶段;
21世纪,2008年美国电气与电子协会发现以“软件开发工具”为题的一期专刊;2002年Rational初IMB收购。
3.近义混淆词
速度和效率
错误视图和断点视图
表示层和用户接口层

kubernetes

k8s是容器集群管理系统。

Kubernetes将一个集群中的机器划分为一个Master节点和一群工作节点(Node)。其中,Master节点上运行着集群管理相关的一组进程etcd、API Server、Controller Manager、Scheduler,后三个组件构成了Kubernetes的总控中心,这些进程实现了整个集群的资源管理、Pod调度、弹性伸缩、安全控制、系统监控和纠错等管理功能,并且全都是自动完成。在每个Node上运行Kubelet、Proxy、Docker daemon三个组件,负责对本节点上的Pod的生命周期进行管理,以及实现服务代理的功能。

https://www.cnblogs.com/menkeyi/p/7134460.html
https://www.jianshu.com/p/63ffc2214788

在Kubernetes中,Node、Pod、Replication Controller、Service等概念都可以看作一种资源对象,通过Kubernetes提供的Kubectl工具或者API调用进行操作,并保存在etcd中。

k8s的Node

Node:主机节点,一个node就是一台pc服务器或一个虚拟机,它是Kubernetes集群中相对于Master而言的工作主机,在较早的版本中也被称为Minion。Node可以是一台物理主机,也可以是一台虚拟机(VM)。在每个Node上运行用于启动和管理P
od的服务Kubelet,并能够被Master管理。在Node上运行的服务进程包括Kubelet、kube-proxy和docker daemon。

Node信息有:
Node地址,即主机的IP地址,或者Node ID。
Node运行状态:包括Pending、Running、Terminated三种状态。
Node Condition(条件):描述Running状态Node的运行条件,目前只有一种条件—-Ready。Ready表示Node处于健康状态,可以接收从Master发来的创建Pod的指令。
Node系统容量:描述Node可用的系统资源,包括CPU、内存数量、最大可调度Pod数量等。
其他:Node的其他信息,包括实例的内核版本号、Kubernetes版本号、Docker版本号、操作系统名称等。

Node的管理
Node通常是物理机、虚拟机或者云服务商提供的资源,并不是由Kubernetes创建的。我们说Kubernetes创建一个Node,仅仅表示Kubernetes在系统内部创建了一个Node对象,创建后即会对其进行一系列健康检查,包括是否可以连通、服务是否正确启动、是否可以创建Pod等。如果检查未能通过,则该Node将会在集群中被标记为不可用(Not Ready)。

1. 使用Node Controller对Node进行管理
Node Controller是Kubernetes Master中的一个组件,用于管理Node对象。它的两个主要功能包括:集群范围内的Node信息同步,以及单个Node的生命周期管理。
Node信息同步可以通过kube-controller-manager的启动参数–node-sync-period设置同步的时间周期。

2. Node的自注册
当Kubelet的–register-node参数被设置为true(默认值即为true)时,Kubelet会向apiserver注册自己。这也是Kubernetes推荐的Node管理方式。

3. 手动管理Node
Kubernetes集群管理员也可以手工创建和修改Node对象。当需要这样操作时,先要将Kubelet启动参数中的–register-node参数的值设置为false。这样,在Node上的Kubelet就不会把自己注册到apiserver中去了。

4.另外,Kubernetes提供了一种运行时加入或者隔离某些Node的方法。

Label

Label以key/value键值对的形式附加到各种对象上,如Pod、Service、RC、Node等。Label定义了这些对象的可识别属性,用来对它们进行管理和选择。
在为对象定义好Label后,其他对象就可以使用Label Selector(选择器)来定义其作用的对象了。

Replication Controller(RC)

Replication Controller用于定义Pod副本的数量。在Master内,Controller Manager进程通过RC的定义来完成Pod的创建、监控、启停等操作。

Pod

Pod:k8s最小单位,包含多个容器,当有两个程序必须相互依赖,可以使用一个pod管理。
Pod是Kubernetes的最基本操作单元,包含一个活多个紧密相关的容器,一个Pod中的多个容器应用通常是紧耦合的。Pod在Node上被创建、启动或者销毁。
一个Pod可以被一个容器化的环境看作应用层的“逻辑宿主机”(Logical Host)。
为什么Kubernetes使用Pod在容器之上再封装一层呢?一个很重要的原因是,Docker容器之间的通信受到Docker网络机制的限制。在Docker的世界中,一个容器需要link方式才能访问另一个容器提供的服务(端口)。大量容器之间的link将是一个非常繁重的工作。通过Pod的概念将多个容器组合在一个虚拟的“主机”内,可以实现容器之间仅需要通过Localhost就能相互通信了。

一个Pod中的应用容器共享同一组资源,如下所述:
PID命名空间:Pod中的不同应用程序可以看到其他应用程序的进程ID;
网络命名空间:Pod中的多个容器能够访问同一个IP和端口范围;
IPC命名空间:Pod中的多个容器能够使用SystemV IPC或者POSIX消息队列进行通信;
UTS命名空间:Pod中的多个容器共享一个主机名;
Volumes(共享存储卷):Pod中的各个容器可以访问在Pod级别定义的Volumes。

Pod的生命周期是通过Replication Controller来管理的。Pod的生命周期过程包括:通过模板进行定义,然后分配到一个Node上运行,在Pod所含容器运行结束后Pod也结束。

Kubernetes为Pod设计了一套独特的网络配置,包括:为每个Pod分配一个IP地址,使用Pod名作为容器间通信的主机名等。
另外,不建议在Kubernetes的一个Pod内运行相同应用的多个实例。

Service

Service:集群内部的Pod访问方式,通过service名字可以访问到pod里面包含的应用。
每个Pod都会被分配一个单独的IP地址,但这个IP地址会随时Pod的销毁而消失。这就引出一个问题:如果有一组Pod组成一个集群来提供服务,那么如何来访问它们?
Kubernetes的Service(服务)就是用来解决这个问题的核心概念。
一个Service可以看作一组提供相同服务的Pod的对外访问接口。Service作用于哪些Pod是通过Label Selector来定义的。

Volume(存储卷)

Volume是Pod中能够被多个容器访问的共享目录。Kubernetes的Volume概念与Docker的Volume比较类似,但不完全相同。Kubernetes中的Volume与Pod生命周期相同,但与容器的生命周期不相关。当容器终止或者重启时,Volume中的数据也不会丢失。另外,Kubernetes支持多种类型的Volume,并且一个Pod可以同时使用任意多个Volume。
存储:pv和pvc,pod可以通过pvc挂载外部的存储,将应用程序产生的数据或配置文件存储起来

Namespace(命名空间)

通过将系统内部的对象“分配”到不同的Namespace中,形成逻辑上分组的不同项目、小组或用户组,便于不同的分组在共享使用整个集群的资源的同时还能被分别管理。
Kubernetes集群在启动后,会创建一个名为“default”的Namespace,通过Kubectl可以查看到。
使用Namespace来组织Kubernetes的各种对象,可以实现对用户的分组,即“多租户”管理。对不同的租户还可以进行单独的资源配额设置和管理,使得整个集群的资源配置非常灵活、方便。
Namespaces:命名空间,用于一个集群内,系统的隔离。

Annotation(注解)

Annotation与Label类似,也使用key/value键值对的形式进行定义。Label具有严格的命名规则,它定义的是Kubernetes对象的元数据(Metadata),并且用于Label Selector。Annotation则是用户任意定义的“附加”信息,以便于外部工具进行查找。

spring cloud与K8S

微服务有六个基本必须实现:1.进程通讯2.服务注册与发现3.负债均衡4.配置中心5.熔断器6.网关路由。

k8s和spring cloud 的出发点不同,一个是基于容器管理的概念,一个是基于程序的注册与发现(我个人认为Netflix 的核心在于注册中心)。二者都可以达到我们的目的。就拿实现一个高可用的注册中心Eureka 来说,单纯从Netflix的设计思想来说,eureka 是一个AP 系统,要保证数据的同步,可以采用注册中心(Eureka server )相互注册的方案,实现一个集群,但是集群每加入一个节点,要更新所有的client的配置。常规的思想,我们可以通过负载均衡的轮询算法实现,然而这个思路正是k8s 的出发点。可能Spring Cloud +K8s二者皆用是一个最好的方案,但是二者择其一一样可以达到目的。

https://blog.csdn.net/educast/article/details/78328981

https://blog.csdn.net/qq_32971807/article/details/56489609

图结构中,圆圈称为顶点,连线称为边,有向图的边称为弧。
有序偶对用尖括号,无序偶对用圆括号。
简单路径:序列中顶点不重复出现的路径。
n个顶点的无向完全图的边数=n(n-1)/2,n个顶点的有向完全图的边数=n(n-1)。

图的存储结构

邻接矩阵:图的n的顶点的相邻关系用n阶方阵来表示,其中用1表示顶点间存在的边或弧,用0表示顶点间不存在边。
除了用0、1表示是否有边外,对于带权图,还可以用边的权值来替代1,用无穷替代0。
还需要另一个数组来存储n个顶点的附带信息。
对于有向图,矩阵中行表示出度,列表示入度。
无向图的邻接矩阵是一个对称矩阵。
无向图的边数=值为1的个数/2,有向图边数=值为1的个数。
无向图某顶点的度数=邻接矩阵中对应行或列的值之和。

邻接表:
对每个顶点建立一个单链表,这个单链表称为顶点v的邻接表。再用一个数组存储所有的单链表的头结点。
对于无向图,单链表中的每个结点都和顶点v之间存在边。
对于有向图,单链表中的每个结点都和顶点v之间存在边,且是这条边的终点。
对于有向图,有时还需要建立逆邻接表,它较容易求出顶点v的入度。

遍历和搜索

图的遍历是从某个顶点出发,访问图的每个顶点一次。
图的搜索是从某个顶点出发,访问能访问到的每个顶点一次。
遍历图的两种基本方法:深度优先搜索和广度优先搜索。
由于顶点间都可能相邻接,在遍历的过程中,需要增设一个辅助数组,标记各顶点是否被访问过。

连通图的深度优先搜索:
类似于树的先序遍历,可以看成一个递归过程。
当某个顶点的所有邻接点都被访问过时,搜索过程要加到前一个顶点寻找未被访问的顶点。
深度搜索的顶点访问序列不是唯一的。
以邻接表为存储结构,时间复杂度为O(n+e)。
以邻接矩阵为存储结构,时间复杂度为O(n2)。

连通图的广度优先搜索:在访问完所有邻接点后,要依次从这些邻接点出发继续广度搜索。
类似于树的按层次遍历。
广度优先搜索具有先进先出的特征,可以用队列暂存访问过的顶点。

最小生成树(最小遍历树)

连通图的一次遍历所经过的顶点和边就构成了图的一棵生成树。连通图的遍历序列不是唯一的,其中权总和最小的生成树叫做最小生成树。
生成树是连通图的极小连通无环子图,不是连通分量。
n个顶点的无向图,所有生成树中都有n-1条边。构建最小生成树的过程,即找到这n-1条权总和最小的边。

构造最小生成树的Prim(普里姆)算法:原状列出带权图的各顶点,从顶点v0出发,在已通路径的任意点中向外连接上新的最小权边,最终得到图的最小生成树。
树造最小生成树的Kruskal(克鲁斯卡尔)算法:原状列出带权图的各顶点,在所有连通分量(顶点)间按权从小到大找边并连接,最终得到图的最小生成树。
单源最短路径Dijkstra(迪杰斯特拉)算法:从只包含最初源顶点的源集出发,每趟把上一趟列出的权值最小路径点加入到源集中,接着列出源集到除了最初源点的各点的最小权值。最终得到最短路径序列。

拓扑

AOV网:用图中的顶点表示活动,有向边表示活动之间的优先关系,这种表示活动关系的有向图称为AOV网。
拓扑排序,即输出有向图顶点的拓扑序列:
1.在无环有向图中选择一个入度为0的顶点,输出该顶点,然后在图中删除该顶点及和其关系的弧。
2.重复上一条直到图中只剩最后一个顶点。这样的顶点输出序列即为拓扑序列。
邻接表拓扑排序算法的时间复杂度为O(n+e)。

拓扑序列: