创建: 2018/06/01 图的概念
有向边 有向图 无向边 无向图 点的次数: 点连接的边的数量 闭路: 起点和重点一样 连接图: 任意两点之间都可到达 无闭路有向图: 没有闭路的有向图 森林: 互素的树的集合 生成树: 含有图里所有点的树 生成树林: 所有生成树的并集 图论算法的应用 ● 电路的元件关系 ● 交通网 ● 电脑网络(本地网络, 互联网, web等) ● 数据库(实体关系图(ER图)) 原文：https://www.cnb...
分层图，很简单举个例题https://www.luogu.com.cn/problem/P4822所谓分层图，可能会有k种情况来改变图的边权状况等，这时可以建k层图对于每一层中，按照第一层即初始状况去建图然后在相邻两层中对于可能会发生变化的边的两点，或者是按照意义需要额外连接的两点之间，再建一次边对于数据范围，开k倍大小，然后每一层即为u+（k-1）*n当然，具体情况自己得手推确定。那么对于例题，就是建了k层图后，对于终点n，每一层都要去比较，以...
图论算法复习笔记
目录图论算法复习笔记最短路最短路树最小环判负环差分约束系统k短路同余最短路最小生成树次小生成树非严格次小生成树严格次小生成树最优比率生成树最小瓶颈生成树Kruskal重构树生成树计数连通分量无向图的割点与桥割点与桥e-DCC的求法与缩点v-DCC的求法与缩点,圆方树有向图强连通分量有向图的缩点2-SAT二分图二分图判定二分图匹配二分图最小点覆盖,最大团,最大独立集欧拉图树论网络流
最短路
最短路算法概述.算法...
目录约定一般连通无向图的信息、操作遍历联通块二分图判定割点割边点双边双有向图信息、操作拓扑排序强连通分量、缩点简单树论直径重心约定
我是怎么存图的呢？ 普通的邻接表。
const int N = 1e5+15; // 点数
const int M = 1e6+15; // 边数
int ct,hd[N],nt[M<<1],vr[M<<1],vl[M<<1];
void ad(int a,int b,int c) { // 加一条 e = a->b, w(e)=c 的有向边 evr[++ct]=b,vl[ct]=c;nt[ct]=hd[a],hd[a]=ct;
}一般连通无向图的信息、...
有向图的可达性
利用了有向图的深度优先算法，它解决了单点连通性的问题，可以判定其他顶点和给定的起点是否连通。
package com.algorithms.graph;/*** @author yjw* @date 2019/5/20/020*/
public class DirectedDFS {private boolean[] marked;public DirectedDFS(DiGraph g, int s) {marked = new boolean[g.vertexNum()];dfs(g, s);}/*** 在有向图中找到从sources中的所有顶点可达的所有顶点** @param g* @param sources*/publ...
本节内容——2-SAT
dijstra算法的一些应用
SPFA算法的一些应用例题9 飞机调度
有n架飞机需要着陆。每架飞机都可以选择“早着陆"和”晚着陆“两种方式之一，且必须选择一种。第i架飞机的早着陆时间为\(E_i\)，晚着陆时间为\(L_I\),不得在其他时间着陆。现在需要安排这些飞机的着陆方式，使得整个着陆计划尽量安全。换句话说，如果把所有飞机的实际着陆时间按照从早到晚的顺序排列，相邻两个着陆时间间隔的最小值（成为安全间隔）尽量...
spfa
题目描述
给定n个点，m条边，计算从第x点到第y点的最短路径
输入格式
第一行为n和m，表示有n个点和m条边
接下来m行每行有a，b，c，表示从a到b间的长度为c
接下来1行x和y，表示计算从x到y间最短路的长度
输出格式
一个整数，表示x到y间最短路的长度，若不存在则输出-1
输入样例4 5
1 2 1
2 4 5
2 3 1
3 4 1
3 4 5
2 4
输出样例2
模板 1 #include<stdio.h>2 #include<string.h>3 #include<queue>4 using namespace std;5 ...
