图
图
图是由两个集合V和E构成，V表示有限的非空顶点集合，E表示两个“顶点对”边的集合。
有向图：顶点之间有指向的图<A,B>
无向图：顶点之间没有指向或者说顶点之间双向的图(A,B)
V(G1)={1,2,3,4,5}
E(G1)={(1,2),(2,3),(2,5),(3,5),(3,4),(4,1)}
V(G2)={1,2,3,4}
E(G2)={<1,3>,< 3,2>,<2,3>,<2,1>}
度
- 无向图：顶点的连线数量
- 无向图：入度+出度
入度：指向该顶点的连线
出度：该节点指出的连线
完全图
在无向图中完全图：每个顶点之间都有一条边相连
在无向图中完全图：每个顶点之间都有两条有向边相连
路径和回路
路径长度：一个顶点到达另一顶点所经过的路径数量
回路：从一个顶点出发回到这个顶点
简单回路：回路中没有经过重复的顶点
连通图
无向图的连通图：任意顶点之间都有路径可以到达
有向图：任意顶点之间都有路径可以到达 如:2和4之间2->3->4，4->2
连通分量
网络
图的存储
1.邻接矩阵
设图G有n (n1) 个顶点，则邻接矩阵是一个n阶方阵。
当矩阵中的 [i,j] !=0（下标从1开始） ,代表其对应的第i个顶点与第j个顶点是连接的。
特点：
无向图的邻接矩阵是对称矩阵，n个顶点的无向图需要n*(n+1)/2个空间大小
有向图的邻接矩阵不一定对称，n个顶点的有向图需要n²的存储空间
无向图中第i行的非零元素的个数为顶点Vi的度
有向图中第i行的非零元素的个数为顶点 Vi 的出度，第i列的非零元素的个数为顶点 Vi 的入度
无向存储：
有向存储：
网络存储：
2.邻接表
为图G中的每一个顶点建立一个单链表，每条链表的结点元素为与该顶点连接的顶点。
特点
无向图顶点 Vi 的度为第 i 个单链表中的结点数
无向图中
顶点 Vi 的出度为第 i 个单链表中的结点个数
顶点 Vi 的入度为全部单链表中连接点域值是 i 的结点个数
逆邻接表：有向图中对每个结点建立以 Vi 为头的弧的单链表
3. 十字链表
可以看成是有向图的邻接表和逆邻接表结合起来的一种链表
图的遍历
广度优先遍历和深度优先遍历不唯一有多种方式，上图只是列举了几种
图的最小生成树
1. 普里姆（Prim）算法
第一步：选取出发点（任意选）a，并连接与a点最小距离的点c
第二步：将a和c看为一个整体，选择与a连接和c连接最小距离的点b
第三步：将a,b和c看为一个整体，选择与a连接,b连接和c连接最小距离的点d
第四步：
第五步：
- 克鲁斯卡尔（Kruskal）算法
第一步：寻找最小边
第二步：寻找第二小的边
第三步：寻找第三小的边
第四步：寻找第四小的边，构成回路放弃
第五步：寻找下一个，并连接最后一个
拓扑排序与关键路径
拓扑排序
第一步：删除1或2输出（每次找寻入度为0的顶点，删除该顶点的入度）
第二步：删除2或3以及对应边
第三步：删除3或者4以及对应边
第四步：重复以上规则步骤
顺序：1 2 4 3 6 5 7 9（不唯一）
其中1，2的顺序可以随意。3，4的顺序可以随意。5，6的顺序可以随意。
关键路径
关键路劲也就是最长路径（一个项目的周期时间也就是最长路径）
顶点j的最早发生时间：从源点到顶点j的最长路径，记作Ve(j)。
活动ai最早开始时间：Ve(j)是以顶点j为起点的出边所表示的活动ai的最早开始时间，记作e(i)。
顶点j的最迟发生时间：在不推迟工程完成的前提下，一个事件j允许最迟发生的时间，记作Vi(j)。
活动ai最迟开始时间：Vi(j)-（ai所需的时间），就是活动ai最迟开始时间，j是ai活动的终点，记作I(i)