目录
b)有向图第i行不为0/∞的元素个数是第i个ele的入度，i列不为0/∞的元素个数为第i个ele的出度
1）AOV网(Activity on vertex NetWork)
b)缩短关键路径上的活动的time，关键路径可能变为非关键path
c)当有多条关键path时，缩短全部关键path上关键活动的time才能缩短总time
一、概念
1.顶点Vertex
图的阶数，不可为空
2.边Edge
可以为空
3.边的权
带权图(网)
4.路径、回路、简单路径、简单回路
路径长度、最短路径
二、基本图
1.有向图 vs 无向图
图的边是否有箭头
考点：入度和出度
无向所有度sum = 2|E|
有向图 入度= 出度 = |E|
2.简单图 vs 多重图
路径无重复
attn：只考简单图
3.连通图 vs 强连通图
连通图:无向图各顶点之间直接or间接相连
强即有向图
考点：边与连通之间的关系
if 无向图是连通图 then |E|min = n-1
so if |E| <n -1 非连通图
4.连通分量 vs 强连通分量
连通分量：无向图极大连通子图：即每一个连着的子图
强即有向图
5.生成树 vs 生成森林
生成树：连通图，从一个顶点开始，包括所有结点和一些边
生成森林非连通图
三、特殊的图
1.无向完全图 vs 有向完全图
完全：每两个顶点都相连
无向： |E| = |V|(|V|-1)/2 = C|V|^2
有向：|E| = |V|(|V|-1) =2C|V|^2
2.稠密图 vs 稀疏图
稀疏：|E| < |V|log|V|
3.树、森林、有向树
四、存储结构
1.邻接矩阵法（顺序存储）
（1）思路
用一个|V|*|V|的矩阵表示各边与各边之间是否有边
if 有 1 无 0
（2）eg
1）无向图
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 2 | 1 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 0 | 1 | 1 |
| 4 | 1 | 0 | 1 | 0 | 0 |
| 5 | 0 | 1 | 0 | 0 | 0 |
实际只用写中间的即可，最左一列和最上面一列便于画矩阵
attn:无向图的邻接矩阵为对称矩阵
2）有向图
| 1 | 2 | 3 | 4 | |
| 1 | 0 | 1 | 1 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 1 |
| 4 | 1 | 0 | 0 | 0 |
3）带权图
无路径∞/0，有路径权值
| 1 | 2 | 3 | 4 | |
| 1 | ∞ | 2 | 3 | ∞ |
| 2 | ∞ | ∞ | ∞ | ∞ |
| 3 | ∞ | ∞ | ∞ | 1 |
| 4 | 10 | ∞ | ∞ | ∞ |
（3）代码实现（无向图）
n*n的二阶矩阵
//定义
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct {
VertexType vex[MaxVertexNum];//顶点
EdgeType edge[MaxVertexNum][MaxVertexNum];//边
int vexNum,edgeNum;//顶点个数、边个数
}MGraph;
//初始化
void InitGraph(MGraph &M){
for (int i = 1; i <= M.vexNum; ++i) {
M.vex[i] = i;
}
for (int i = 1; i <= M.vexNum; ++i) {
for (int j = 1; j <= M.vexNum; ++j) {
M.edge[i][j] = 0;
}
}
M.vexNum = 5;
M.edgeNum = 5;
}//添加ele
void AddValue(MGraph &M){
M.edge[1][2] = 1;
M.edge[1][4] = 1;
M.edge[2][1] = 1;
M.edge[2][3] = 1;
M.edge[2][5] = 1;
M.edge[3][2] = 1;
M.edge[3][4] = 1;
M.edge[3][5] = 1;
M.edge[4][1] = 1;
M.edge[4][3] = 1;
M.edge[5][2] = 1;
}//打印
void print(MGraph M) {
for (int i = 1; i <= M.vexNum; ++i) {
for (int j = 1; j <= M.vexNum; ++j) {
printf("%-3d", M.edge[i][j]);
}
printf("\n");
}
}(4)考点
a)无向图第i行(列)不为0的元素个数是第i个ele的度
b)有向图第i行不为0/∞的元素个数是第i个ele的入度，i列不为0/∞的元素个数为第i个ele的出度
2.邻接表法（顺序存储+链式存储）
（1）产生原因
邻接矩阵需要|V|^2的空间，Sn较大
so可以一个邻接表表示每个顶点及其指向
（2）eg
1）无向图
2）有向图
（3）代码实现
图包括顺序表和链表，顺序表存储顶点，包括data和下一条弧，链表存储弧，包括邻接顶点和下一条弧
typedef int VertexType;
#define MaxVertexNum 100
typedef struct ArcNode{//弧节点
VertexType adjvex;
struct ArcNode* nextarc;
// int info;
}ArcNode;
typedef struct VNode{//顶点结点
VertexType data;
ArcNode* firstArc;
}VNode,AdjList[MaxVertexNum];
typedef struct {//整体
AdjList vertices;
int vexnum,arcnum;
}ADGraph;3.十字链表法
因为邻接表法只能找出去的，不能找进来的，so添加一条指针指向入的顶点
4.邻接多表法
邻接表在执行删除操作时不方便，so用出和入两根链
5.基本操作（邻接矩阵 vs 邻接表）
1）FirstNeighbor(M,v)
返回第v个顶点的第一个邻接顶点
int FirstNeighbor(MGraph M,int v){
for (int i = 1; i <= M.vexNum; ++i) {
if(M.edge[v][i] == 1) return i;
}
return -1;
}2）NextNeighbor(M,v,w)（可能有误）
w = 第v个顶点的下一个邻接顶点
void NextNeighbor(MGraph M,int v,int &w){
w = -1;
int adj;
for (int i = 1; i <= M.vexNum; ++i) {//第1个
if( M.edge[v][i] == 1) {
adj = i;
break;
}
}
for (int i = adj+1; i <= M.vexNum; ++i) {//第二个
if( M.edge[v][i] == 1) {
w = i;
break;
}
}
}
五、图的遍历(手算+代码)
1.广度优先
（1）与树类比
层次遍历：运用辅助队列实现，依次入队，if不为null，则DeQueue，if有左右孩子，thenEnQueue，循环
图的广度优先遍历：运用一个辅助队列，从目标顶点开始入队，if队列非空则DeQueue并visit，if有相邻顶点，then入队，此处需要额外判断是否被visit过循环
（2）算法实现
事先准备:顺序队列，visited[]
void BFS(MGraph M,int v){
SqQueue Q;
InitQueue(Q);
visit(M,v);
visited[v] = true;
EnQueue(Q,v);
while(!isEmpty(Q)){
DeQueue(Q,v);
for (int w = 1; w <=M.vexNum ; ++w) {
if(!visited[w] && 1 == M.edge[v][w]){/.依次找相邻顶点
visit(M,w);
visited[w] = true;
EnQueue(Q,w);
}
}
}
}当图不是连接图时，需要再次遍历visited[]当遇到不是true的则再次BFS
void BFSTraverse(MGraph M,int i){
BFS(M,i);
//初始化visited if 不设置开始顶点值，则说明是从1or0开始
// for (int i = 1; i < M.vexNum; ++i) {//置为false,表示未visit
// visited[i] = false;
// }
// InitQueue(Q);
for (int i = 0; i < M.vexNum; ++i) {
if(!visited[i]){
BFS(M,i);
}
}
}（3）复杂度(无向图)
主要为visit顶点+找下一个结点
1）邻接矩阵
n个顶点，O(n)，遍历一行,Tn -> O(n^2) ~O(|V|^2)
2）邻接表
n个顶点，O(n)，遍历邻接表，一共2|E|条，Tn = O(n)+O(2|E|) ~O(|V|+|E|)
使用辅助队列 Sn = |V| ~O(|V|) = O(n)
（4）广度优先生成树
利用广度优先生成的树称为广度优先生成树
∵邻接表不唯一，so生成的广度优先生成树也不唯一
对非连通变量进行广度优先遍历成为广度优先生成森林
2.深度优先
（1）与树类比
先根遍历：从根节点开始，根左右，遇到则visit，之后遍历左孩子，再遍历右孩子,函数栈实现
深度优先遍历：找临近结点visit，当没有临近结点后退，找上一个结点的临近结点visit
（2）算法实现
void DFS(MGraph M,int i){
visit(i);
visited[i] = true;
for (int w = FirstNeighbor(M,i); w >=0 ; w =NextNeighbor(M,i,w) ) {
if(!visited[w]){
DFS(M,w);
}
}
}多个连接通量
void DFSTranverse(MGraph M,int i){
DFS(M,i);
for (int j = 1; j <= M.vexNum; ++j) {
if(!visited[j]){
DFS(M,j);
}
}
}（3）复杂度
visit顶点+找邻接顶点
1）邻接矩阵
n个顶点，O(n)，找出度以及出度的出度，O(n) + O(n^2) -> ~O(n^2)
2）邻接表
n个顶点，O(n)，找出度以及出度的出度，O(2|E|) -> Tn=O(|V|+|E|)
使用函数栈 Sn = O(|V|) =O(n)
（4）深度优先生成树
通过深度优先创建的生成树称为深度优先生成树
∵邻接表不唯一，so生成的深度优先生成树也不唯一
对非连通变量进行深度优先遍历成为深度优先生成森林
（5）图的遍历和图的连通性
1）无向图
执行BFS/DFS次数 == 连通分量个数
2）有向图
从某顶点开始都能到else顶点，1次
强连通图，任何结点都为1次
六、图的应用
1.最小生成树（最小代价树）
生成总代价最小的树
1）Prim算法（手算）
扩展树，选择与已定的子树相连的边
2）Kruskal算法（手算）
依次选择最小的边
2.最短路径
1）单源最短路径
从特定顶点开始，到每个顶点的长度min
a)无权图
i)思路
BFS:从某一顶点开始，进行BFS，距离依次+1，区别是多加两个arr
visited[]表示是否被visit,d[]表示与初始结点的距离
ii)代码实现
void BFS_MIN_Distance(MGraph G,int u){
for (int i = 1; i <= G.vexNum; ++i) {
d[i] = ∞;
}
visited[u] = true;
d[u] = 0;
EnQueue(Q,u);
while(!isEmpty(Q)){
DeQueue(Q);
for (int w = FirstNeighbor(Q,u); w >=0 ; w=NextNeighbor(Q,u,w)) {
if(!visited[w]){
visited[w] =true;
d[w] = d[u]+1;
EnQueue(Q,w);
}
}
}
}b)有权图（手算）
DijKstra算法：从第i个顶点开始，依次写出到每个顶点的距离，选择最小的，之后再根据这个顶点再比较与之前写好的距离。
so利用三个arr表示，final[]表示已经找到的最短path,dist[]表示结点之间的距离，path[]表示该结点在最短path中的前驱
2）每对顶点间的最短路径（手算A^(n-1)）
任何两个顶点间长度min
a)思路
Floyd算法：起初设定不可以中转，即一个顶点到另一个顶点只能直接到达。
so依次可以进行中转的话会有路径简短的情况
b)手算
利用两个矩阵，邻接矩阵+中转顶点矩阵，依次比较A[i][j] ？ A[i][k]+A[k][j] ，if > 则替换，并将中专顶点矩阵 path[i][j] = k
c)代码
void Floyd(MGraph G) {
for (int k = 1; k < G.vexNum; ++k) {
for (int i = 1; i <= G.vexNum; ++i) {
for (int j = 1; j < G.vexNum; ++j) {
if(A[i][j] > A[i][k]+A[k][j]){
A[i][j] = A[i][k]+A[k][j];
path[i][j] = k;
}
}
}
}
}3.有向无环图（手算）
DAG图：有向图无环
考点：根据表达式创建有向无环图，简化相同字符和运算符
做题步骤：
step1：找到操作数，排在最下面
step2：找运算符的先后运算顺序
step3：画图
step4：相同的运算符进行简化，左右符号相同才能简化
4.拓扑结构
1）AOV网(Activity on vertex NetWork)
有向无环图+顶点作为事件
2）拓扑排序(手算+代码)
找事件发生的先后顺序
a)思路
依次找入度为0的结点
b)实现
用栈or队列储存遍历顶点，入栈出栈，出栈之后相关结点的入度-1
bool TopologicalSort(MGraph G){
Stack S;
InitStack(S);
int i;
for (i = 0; i <G.vexNum ; ++i) {
if(indegree[i] == 0){
Push(S,i);
}
}
int count=0;
while(!isEmpty(S)){
Pop(S,i);
print[count++]=i;
}
//i指向的所有顶点入度-1
for (p = G.vertice[i].firstarc; p ; p=p->nextarc) {
v = p->adjvex;
if(!(--indegree[v])){
Push(S,v);
}
}
if(count<G.vexNum) return false;
else return true;
}
3）逆拓扑排序
依次找出度为0的结点
DFS实现逆拓扑排序，依次找到最深处的顶点，此结点一定出度=0
4）性质
a)排序可能不唯一
b)if有环路，应该如何改进
5.关键路径
1）AOE网+事件+活动
事件、活动、源点、汇点
2）求解方法
step1：求事件的最早发生时间ve、最晚发生时间vl
step2：求活动的最早发生时间e、最晚发生时间l
step3：求时间余量d
step4：判断关键path
ve:前->后，max{vl+活动持续时间}
vl:后->前，min{vl-活动持续时间}
e:==ve
l:后->前，vl-活动持续时间