0.PTA得分截图
1.本周学习总结
1.1 总结图内容
图的基本概念
1.有向图：
- 有向图称由顶点集和弧集构成的图。“弧”是有方向的边，用尖括号表示。
- 若存在一条边(i，j)，则称顶点i和顶点j互为邻接点。
- 每两个顶点之间都存在着一条边，称为完全无向图， 包含有n(n-1)/2条边。
- 若从顶点i到顶点j有路径，则称顶点i和j是连通的。若图中任意两个顶点都连通称为连通图，否则称为非连通图。无向图G中的极大连通子图称为连通分量。
2.无向图：
-
没有方向边。边用圆括号表示。
-
存在一条边<i，j>，则称此边是顶点i的一条出边，同时也是顶点j的一条入边；称顶点i 和顶点j 互为邻接点。
-
每两个顶点之间都存在着方向相反的两条边，称为完全有向图，包含有n(n-1)条边。
-
若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。 否则，其各个强连通子图称作它的强连通分量。
3.带权图(网)
-
图中每一条边都可以附有一个对应的数值，这种与边相关的数值称为权。
-
边上带有权的图称为带权图，也称作网。
图存储结构
邻接矩阵
1.有向图
设顶点i，j，若有一条边从i指向j，则将edges[i][j]赋为1，否则为0
2.无向图
设顶点i，j，若有一条边连接i和j，则将edges[i][j]和edges[j][i]赋为1，否则为0
3.带权图
设顶点i，j，若有一条边从i指向j或连接i和j，则按照有向图或无向图的方法将相应权值赋给二维数组，若i=j，则相应值为0，若i!=j，且不相连，则相应值为无穷大
4.结构体定义
typedef struct //图的定义
{ int edges[MAXV][MAXV]; //邻接矩阵
int n，e; //顶点数，边数
VertexType vexs[MAXV]; //存放顶点信息
} MatGraph;
MatGraph g;//声明邻接矩阵存储的图
5.创建图
void CreateMGraph(MGraph &g, int n, int e)
{
int i, j;
g.n = n;
g.e = e;
int a, b;
for (i = 1;i <= n;i++)
{
for (j = 1;j <= n;j++)
{
g.edges[i][j] = 0;
}
}
for (i = 0;i < e;i++)
{
cin >> a >> b;
g.edges[a][b] = g.edges[b][a] = 1;
}
}
- 时间复杂度为O(n²)
- 优点：可以快速查找到两个顶点之间有无边
- 缺点：浪费空间
- 若顶点数量过多，可以将edges[][]换为**edges。
邻接表
用链存储，将每个顶点所连接的顶点构成一条链，用一维数组将每个顶点存储起来，即将所有链集合
1.有向图
2.无向图
3.带权图
4.结构体定义
typedef struct Vnode
{ Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
} VNode;
typedef struct ANode
{ int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
InfoType info; //该边的权值等信息
} ArcNode;
typedef struct
{ VNode adjlist[MAXV] ; //邻接表
int n，e; //图中顶点数n和边数e
} AdjGraph;
AdjGraph *G；//声明一个邻接表存储的图G
5.创建图
void CreateAdj(AdjGraph *&G, int n, int e) //创建图邻接表
{
int i, j, a, b;
ArcNode *p;
G = new AdjGraph;
for (i = 1;i < n;i++)
{
G->adjlist[i].data = i;
G->adjlist[i].firstarc = NULL;
}
for (i = 1;i <= e;i++)
{
cin >> a >> b;
ArcNode *p = new ArcNode;
p->adjvex = b;
p->nextarc = G->adjlist[a].firstarc;
G->adjlist[a].firstarc = p;
/*p = new ArcNode;
p->adjvex = a;
p->nextarc = G->adjlist[b].firstarc;
G->adjlist[b].firstarc = p;*/无向图
}
}
- 时间复杂度O(n+e)
- 优点：空间利用率较高
- 缺点：不利于判断顶点之间是否有边
邻接表转邻接矩阵
void ListToMat(ALGraph *G，MGraph &g)
{ int i，j，n=G->n;ArcNode *p;
for (i=0;i<n;i++)
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ g.edges[i][p->adjvex]=1;
p=p->nextarc;
}
}
g.n=n;g.e=G->e;
}
图遍历及应用
深度优先遍历
1.过程
- 从图中某个初始顶点v出发，首先访问初始顶点v。
- 选择一个与顶点v相邻且没被访问过的顶点w为初始顶点，再从w出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。
2.邻接矩阵的深度优先遍历
void DFS(MGraph g, int v)//深度遍历
{
visited[v] = 1;
if (!flag)
{
flag = 1;
cout << v;
}
else cout << " " << v;
for (int i = 1;i <= g.n;i++)
{
if (g.edges[v][i] == 1 && (!visited[i]))
DFS(g, i);
}
}
3.邻接表的深度优先遍历
void DFS(AdjGraph *G, int v)//v节点开始深度遍历
{
ArcNode *p;
visited[v] = 1; //置已访问标记
if(!flag)
{
cout<<v;
flag=1;
}
else cout<<" "<<v;
p = G->adjlist[v].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] == 0) DFS(G, p->adjvex);
p = p->nextarc;
}
}
4.非连通图
图还存在非连通的可能，所以考虑该情况的代码
void DFSTraverse(Graph G) {
// 对非连通图 G 作深度优先遍历。
for (v=0; v<G.vexnum; ++v)
visited[v] = FALSE; // 访问标志数组初始化
for (v=0; v<G.vexnum; ++v)
if (!visited[v]) DFS(G，v); // 对尚未访问的顶点调用DFS
}
广度优先遍历
1.过程
- 访问初始点v，接着访问v的所有未被访问过的邻接点。
- 按照次序访问每一个顶点的所有未被访问过的邻接点。
- 依次类推，直到图中所有顶点都被访问过为止。
2.邻接矩阵的广度优先遍历
void BFS(MGraph g, int v)//广度遍历
{
int num, front, rear;
int Q[MAXV];
front = rear = -1;
cout << v;
visited[v] = 1;
Q[++rear] = v;
while (front != rear)
{
v = Q[++front];
for (int i = 1;i <= g.n;i++)
{
if (g.edges[v][i] == 1 && (!visited[i]))
{
cout << " " << i;
visited[i] = 1;
Q[++rear] = i;
}
}
}
}
3.邻接表的广度优先遍历
void BFS(AdjGraph *G, int v) //v节点开始广度遍历
{
ArcNode *p;
queue<int>qu;
visited[v] = 1;
cout << v;
qu.push(v);
while (!qu.empty())
{
v = qu.front();
qu.pop();
p = G->adjlist[v].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] == 0)
{
cout << " " << p->adjvex;
visited[p->adjvex] = 1;
qu.push(p->adjvex);
}
p = p->nextarc;
}
}
}
4.非连通图
void BFS1(AdjGraph *G)
{ int i;
for (i=0;i<G->n;i++) //遍历所有未访问过的顶点
if (visited[i]==0)
BFS(G，i);
}
判断图是否连通
1.过程
- 采用某种遍历方式来判断无向图G是否连通。这里用深度优先遍历方法，先给visited[]数组（为全局变量）置初值0，然后从0顶点开始遍历该图。
- 在一次遍历之后，若所有顶点i的visited[i]均为1，则该图是连通的；否则不连通。
2.代码
int visited[MAXV];
bool Connect(AdjGraph *G) //判断无向图G的连通性
{ int i;
bool flag=true;
for (i=0;i<G->n;i++) //visited数组置初值
visited[i]=0;
DFS(G，0);
for (i=0;i<G->n;i++)
if (visited[i]==0)
{ flag=false;
break;
}
return flag;
}
找到一条简单路径
1.过程
- 采用深度优先遍历的方法。
- 增加path[i],存放路径。
- 递归函数添加形参d，表示目前递归深度。path[d]=图结点
- 当从顶点u遍历到顶点v后，输出path并返回。
2.代码
void FindaPath(AGraph *G，int u，int v，int path[]，int d)
{ //d表示path中的路径长度，初始为-1
int w,i; ArcNode *p;
visited[u]=1;
d++; path[d]=u; //路径长度d增1，顶点u加入到路径中
if (u==v) //找到一条路径后输出并返回
{ printf("一条简单路径为:");
for (i=0;i<=d;i++) printf("%d ",path[i]);
printf("
");
return; //找到一条路径后返回
}
p=G->adjlist[u].firstarc; //p指向顶点u的第一个相邻点
while (p!=NULL)
{ w=p->adjvex; //相邻点的编号为w
if (visited[w]==0)
FindaPath(G，w，v，path，d);
p=p->nextarc; //p指向顶点u的下一个相邻点
}
}
找两个顶点中最短路径
1.过程
- 采用广度遍历
- 利用parent记录前驱
- 输出时逆向，利用parent关系输出
2.代码
typedef struct
{
int data; //顶点编号
int parent; //前一个顶点的位置
} QUERE; //非环形队列类型
void ShortPath(ALGraph *G,int u,int v)
{
//输出从顶点u到顶点v的最短逆路径
ArcNode *p;
int w,i;
QUERE qu[MAXV]; //非环形队列
int front=-1,rear=-1; //队列的头、尾指针
int visited[MAXV];
for (i=0; i<G->n; i++) //访问标记置初值0
visited[i]=0;
rear++; //顶点u进队
qu[rear].data=u;
qu[rear].parent=-1;
visited[u]=1;
while (front!=rear) //队不空循环
{
front++; //出队顶点w
w=qu[front].data;
if (w==v) //找到v时输出路径之逆并退出
{
i=front; //通过队列输出逆路径
while (qu[i].parent!=-1)
{
printf("%2d ",qu[i].data);
i=qu[i].parent;
}
printf("%2d
",qu[i].data);
break;
}
p=G->adjlist[w].firstarc; //找w的第一个邻接点
while (p!=NULL)
{
if (visited[p->adjvex]==0)
{
visited[p->adjvex]=1;
rear++; //将w的未访问过的邻接点进队
qu[rear].data=p->adjvex;
qu[rear].parent=front;
}
p=p->nextarc; //找w的下一个邻接点
}
}
}
应用
六度空间
伪代码
int BFS(int v, int N, int ** snap)
{
将第一个顶点v入队
最后顶点last=v
while 队列不空
出队顶点temp
for j=1toN
if temp和j之间有边且未访问过
入队j节点
记录访问过j顶点
该六度空间内人数+1
记录该节点为本层最后一个顶点tail=j
end if
end for
if 出队顶点等于该层最后一个顶点
层数加一
记录最后一个顶点last=tail
end if
if 层数等于6
结束循环
end if
end while
返回六度空间内的人数
}
代码：
最小生成树相关算法及应用
1.概念
1.一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点和构成一棵树的(n-1)条边。不能回路。
2.由深度优先遍历得到的生成树称为深度优先生成树。由广度优先遍历得到的生成树称为广度优先生成树。
3.对于带权连通图G ，n个顶点，n-1条边。根据深度遍历或广度遍历生成生成树，树不唯一。其中权值之和最小的生成树称为图的最小生成树。
4.非连通图：需多次调用遍历过程。每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树。所有连通分量的生成树组成非连通图的生成森林。
普里姆算法(Prim)
1.过程：
- 初始化U={v}。v到其他顶点的所有边为候选边；
- 从候选边中挑选权值最小的边输出，设该边在V-U中的顶点是k，将k加入U中；
- 考察当前V-U中的所有顶点j，修改候选边：若(j，k)的权值小于原来和顶点k关联的候选边，则用(k，j)取代后者作为候选边。
- 重复后两个步骤骤n-1次，使得其他n-1个顶点被加入到U中
2.具体设置2个辅助数组。 - closest[i]：最小生成树的边依附在U中顶点编号。
- lowcost[i]表示顶点i（i ∈ V－U）到U中顶点的边权重，取最小权重的顶点k加入U。并规定lowcost[k]=0表示这个顶点在U中
- （closest[k]，k）构造最小生成树一条边。
3.代码
#define INF 32767 //INF表示∞
void Prim(MGraph g,int v)
{ int lowcost[MAXV],min,closest[MAXV],i,j,k;
for (i=0;i<g.n;i++) //给lowcost[]和closest[]置初值
{ lowcost[i]=g.edges[v][i];closest[i]=v;}
for (i=1;i<g.n;i++) //找出(n-1)个顶点
{ min=INF;
for (j=0;j<g.n;j++) // 在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{ min=lowcost[j]; k=j; /k记录最近顶点的编号}
printf(" 边(%d,%d)权为:%d
",closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<g.n;j++) //修改数组lowcost和closest
if (lowcost[j]!=0 && g.edges[k][j]<lowcost[j])
{ lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
4.贪心算法：
- 算法原理：以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪心法不要回溯。
- 算法优点：因为省去了为寻找解而穷尽所有可能所必须耗费的大量时间，因此算法效率高。
- 贪心算法的精神就是“只顾如何获得眼前最大的利益”,有时不一定是最优解。
克鲁斯卡尔算法(Kruskal)
1.过程
- 置U的初值等于V（即包含有G中的全部顶点），TE的初值为空集（即图T中每一个顶点都构成一个连通分量）。
- 将图G中的边按权值从小到大的顺序依次选取： 若选取的边未使生成树T形成回路，则加入TE；否则舍弃，直到TE中包含(n-1)条边为止。
2.类型
typedef struct
{ int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
} Edge;
Edge E[MAXV];
3.代码
void Kruskal(AdjGraph *g)
{ int i，j，u1，v1，sn1，sn2，k;
int vset[MAXV]; //集合辅助数组
Edge E[MaxSize]; //存放所有边
k=0; //E数组的下标从0开始计
for (i=0;i<g.n;i++) //由g产生的边集E，邻接表
{ p=g->adjlist[i].firstarc;
while(p!=NULL)
{ E[k].u=i;E[k].v=p->adjvex;
E[k].w=p->weight;
k++; p=p->nextarc;
}
}
Sort(E，g.e); //用快排对E数组按权值递增排序
for (i=0;i<g.n;i++) //初始化集合
vset[i]=i;
k=1; //k表示当前构造生成树的第几条边，初值为1
j=0; //E中边的下标，初值为0
while (k<g.n) //生成的顶点数小于n时循环
{
u1=E[j].u;v1=E[j].v; //取一条边的头尾顶点
sn1=vset[u1];
sn2=vset[v1]; //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属于不同的集合
{ printf(" (%d，%d):%d
"，u1，v1，E[j].w);
k++; //生成边数增1
for (i=0;i<g.n;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++; //扫描下一条边
}
}
4.采用并查集的方法
void Kruskal(AdjGraph *g)
{ int i，j，k，u1，v1，sn1，sn2;
UFSTree t[MAXSize];//并查集，树结构
ArcNode *p;
Edge E[MAXSize];
k=1; //e数组的下标从1开始计
for (i=0;i<g.n;i++) //由g产生的边集E
{ p=g->adjlist[i].firstarc;
while(p!=NULL)
{ E[k].u=i;E[k].v=p->adjvex;
E[k].w=p->weight;
k++; p=p->nextarc;
}
HeapSort(E，g.e); //采用堆排序对E数组按权值递增排序
MAKE_SET(t，g.n); //初始化并查集树t
k=1; //k表示当前构造生成树的第几条边，初值为1
j=1; //E中边的下标，初值为1
while (k<g.n) //生成的边数为n-1
{ u1=E[j].u;
v1=E[j].v; //取一条边的头尾顶点编号u1和v2
sn1=FIND_SET(t，u1);
sn2=FIND_SET(t，v1); //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属不同集合
{ printf(" (%d，%d):%d
"，u1，v1，E[j].w);
k++; //生成边数增1
UNION(t，u1，v1);//将u1和v1两个顶点合并
}
j++; //扫描下一条边
}
}
本算法的时间复杂度是O(elog2e)。由于它与n无关，只与e有关，所以克鲁斯卡尔算法适合于稀疏图
5.比较
- 普里姆算法：O(n2)、适用于稠密图，克鲁斯卡尔算法：O(eloge)、适用于稀疏图
- 实现普里姆算法，用邻接矩阵。实现克鲁斯卡尔算法，用邻接表。
应用
1.伪代码
用vest数组作为集合辅助数组
while k不等于顶点数n
遍历寻找最小边
if 找到最小边权值为INF
非连通 输出-1
end if
if 该边两顶点集合不一
并查集改为同一集合
ans加上该边权值
记录边个数+1
end if
将该边权值修正为INF
end while
2.代码
最短路径相关算法及应用
狄克斯特拉(Dijkstra)算法
1.单源最短路径问题：Dijkstra算法
- S={入选顶点集合，初值V0},T={未选顶点集合}。
- 若存在<V0,Vi>，距离值为<V0,Vi>弧上的权值
- 若不存在<V0,Vi>，距离值为∞
- (1)从T中选取一个其距离值为最小的顶点W, 加入S
- (2)S中加入顶点w后，对T中顶点的距离值进行修改：重复上述步骤1，直到S中包含所有顶点，即S=V为止。
- (3)重复上述步骤1，直到S中包含所有顶点，即S=V为止。
2.最短路径证明
- 采用邻接矩阵存储
- 数组dist[]：源点V0到每个终点的最短路径长度。
- 数组path[]：最短路径序列的前一顶点的序号；初值或无路径用-1表示
- 数组s[]：表示最短路径顶点集合S。
- 算法过程
3.代码
void Dijkstra(MatGraph g，int v)
{ int dist[MAXV]，path[MAXV];
int s[MAXV];
int mindis,i,j,u;
for (i=0;i<g.n;i++)
{ dist[i]=g.edges[v][i]; //距离初始化
s[i]=0; //s[]置空
if (g.edges[v][i]<INF) //路径初始化
path[i]=v; //顶点v到i有边时
else
path[i]=-1; //顶点v到i没边时
}
s[v]=1; //源点v放入S中
for (i=0;i<g.n;i++) //循环n-1次
{ mindis=INF;
for (j=0;j<g.n;j++)
if (s[j]==0 && dist[j]<mindis)
{ u=j;
mindis=dist[j];
}
s[u]=1; //顶点u加入S中
for (j=0;j<g.n;j++) //修改不在s中的顶点的距离
if (s[j]==0)
if (g.edges[u][j]<INF &&dist[u]+g.edges[u][j]<dist[j])
{ dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
Dispath(dist,path,s,g.n,v); //输出最短路径
}
4.缺点及其他：
- 不适用带负权值的带权图求单源最短路径。
- 不适用求最长路径长度:最短路径长度是递增，顶点u加入S后，不会再修改源点v到u的最短路径长度
- 求每一对顶点之间的最短路径时，每次以一个顶点为源点，重复执行Dijkstra算法n次。时间复杂度为O(n3)。也可以用弗洛伊德(Floyd)算法：时间复杂性也是O(n3)，但形式上简单些。
弗洛伊德(Floyd)算法
1.过程：
- 有向图G=(V，E)采用邻接矩阵存储
- 二维数组A用于存放当前顶点之间的最短路径长度，分量A[i][j]表示当前顶点i到顶点j的最短路径长度。
- 递推产生一个矩阵序列A0，A1，…，Ak，…，An-1。Ak+1[i][j]表示从顶点i到顶点j的路径上所经过的顶点编号k+1的最短路径长度。
2.代码
void Floyd(MatGraph g) //求每对顶点之间的最短路径
{ int A[MAXVEX][MAXVEX]; //建立A数组
int path[MAXVEX][MAXVEX]; //建立path数组
int i, j, k;
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
{ A[i][j]=g.edges[i][j];
if (i!=j && g.edges[i][j]<INF)
path[i][j]=i; //i和j顶点之间有一条边时
else //i和j顶点之间没有一条边时
path[i][j]=-1;
}
for (k=0;k<g.n;k++) //求Ak[i][j]
{ for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
if (A[i][j]>A[i][k]+A[k][j]) //找到更短路径
{ A[i][j]=A[i][k]+A[k][j]; //修改路径长度
path[i][j]=k; //修改经过顶点k
}
}
}
应用
1.伪代码
建图
定义将结构体edges为距离，cost为花费资金
定义dist数组为到首顶点距离，costs数组为花费资金，s数组记录是否访问过
初始化dist，costs，s数组
for 1 to n
找到最短路径，记录距离、花费及下标
相应s数组值修改为1
for 0 to n
if 未访问且路径长小于之前的最短路径
更新最短路径及最少花费
dist[t] = min1 + g.edges[k][t];
costs[t] = min2 + g.cost[k][t];
else if 未被访问，路径长与之前相等且花费少
更新最少花费
end for
end for
输出路径长及花费
2.代码
拓扑排序、关键路径
拓扑排序
1.在一个有向无环图中找一个拓扑序列的过程称为拓扑排序。条件：
- 每个顶点出现且只出现一次。
- 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
2.过程 - 从有向图中选取一个没有前驱的顶点，并输出之；
- 从有向图中删去此顶点以及所有以它为尾的弧；
- 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。
3.结构体
typedef struct //表头节点类型
{ vertex data; //顶点信息
int count; //存放顶点入度
ArcNode *firstarc; //指向第一条弧
} VNode;
4.代码
void TopSort(AdjGraph *G) //拓扑排序算法
{ int i，j;
int St[MAXV]，top=-1; //栈St的指针为top
ArcNode *p;
for (i=0;i<G->n;i++) //入度置初值0
G->adjlist[i].count=0;
for (i=0;i<G->n;i++) //求所有顶点的入度
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ G->adjlist[p->adjvex].count++;
p=p->nextarc;
}
}
for (i=0;i<G->n;i++) //将入度为0的顶点进栈
if (G->adjlist[i].count==0)
{ top++;
St[top]=i;
}
while (top>-1) //栈不空循环
{ i=St[top];top--; //出栈一个顶点i
printf("%d ",i); //输出该顶点
p=G->adjlist[i].firstarc; //找第一个邻接点
while (p!=NULL) //将顶点i的出边邻接点的入度减1
{ j=p->adjvex;
G->adjlist[j].count--;
if (G->adjlist[j].count==0) //将入度为0的邻接点进栈
{ top++;
St[top]=j;
}
p=p->nextarc; //找下一个邻接点
}
}
}
关键路径
1.基本概念
- 用顶点表示事件，用有向边e表示活动，边的权c(e)表示活动持续时间。是带权的有向无环图
- 整个工程完成的时间为：从有向图的源点到汇点的最长路径。又叫关键路径（critical path）
- “关键活动(key activity)”指的是：关键路径中的边
2.AOE网关键词 - AOE网——带权的有向无环图
- 顶点－－事件或状态
- 弧(有向边)－－活动及发生的先后关系
- 权－－活动持续的时间
- 起点－－入度为０的顶点（只有一个）
- 终点－－出度为０的顶点（只有一个）
3.过程 - 事件的最早开始和最迟开始时间
事件v最早开始时间ve(v)：v作为源点事件最早开始时间为0。
v为源点事件最早开始时间一定是前驱事件x,y,z已完成。 - 事件v的最迟开始时间vl(v)：定义在不影响整个工程进度的前提下，事件v必须发生的时间称为v的最迟开始时间
4.活动：边 - 活动a(边)的最早开始时间e(a)指该活动起点x事件的最早开始时间，即：e(a)=ve(x)
- 活动a的最迟开始时间l(a)指该活动终点y事件的最迟开始时间与该活动所需时间之差，即：l(a)=vl(y)-c
- 关键活动：d(a)=l(a)-e(a)，若d(a)为0，则称活动a为关键活动。
- 关键活动不存在富余时间，适当增加对关键活动的投资，减少关键活动的持续时间，缩短工程工期。
5.例题
试对图所示的AOE-网：
① 求这个工程最早可能在什么时间结束；
② 求每个活动的最早开始时间和最迟开始时间；表格表示。
③ 确定哪些活动是关键活动。
1.2.谈谈你对图的认识及学习体会。
对于图的学习时间也比较长，但感觉图的内容很多，而且比较复杂。虽说相较于树来说，递归算法比较少，但算法比较多，刚学的时候一时间难以分清楚，在写代码的时候也不能很准确地完成，总是需要看课件。其实感觉这些算法比较固定，就像是一个模板，题目有浅有深，浅显的题目，直接套用算法，复杂的题目，在算法的基础之上拓展出满足题意的代码即可。其实仔细想想，大的知识点也就几个，缺少的是仔细钻研和总结。实验课上，看同学们集思广益，有各种巧妙的算法，不禁有些惭愧。五一假期没有规划好学习的时间，感觉理解还是很浅显，之后还要继续学习相关内容。
2阅读代码
2.1题目及解题代码
2.1.1该题的设计思路
时间复杂度：O(n²)
空间复杂度：O(n)
2.1.2该题的伪代码
定义flag判断数据走向
逻辑处理是一样的，x，y的上限值是相反的
for 0 to m+n
判断序列走向
找到该次序列起点
循环将序列存入vector容器
改变flag，下次反向
end for
返回该序列
2.1.3运行结果
2.1.4分析该题目解题优势及难点
优势：将两种情况融合在了一起解题，还有将不同方向的情况分开来讲。这样使代码更精简，时间和空间上也节约了不少。
难点：不能一眼看出来各个点之间以及输出序列之间的关系，需要仔细分析。而且将两种情况结合也是比较难的。
2.2题目及解题代码
2.2.1该题的设计思路
1.图中一个节点可以拥有任意数量的邻接点。为了避免在复制时陷入死循环，需要以某种方式跟踪已经复制的节点。
2.从给定节点开始遍历图。使用used数组存放已被访问过的节点
3.如果当前访问的节点不在used中，创建他的克隆节点存进used中
4.递归调用每个节点的邻接点。每个节点递归调用的次数等于邻接点的数量，每一次调用返回其对应邻接点的克隆节点，最终返回这些克隆邻接点的列表，将其放入对应克隆节点的邻接表中。这样就可以克隆给定的节点和其邻接点。
时间复杂度：O(n)
空间复杂度：O(n)
2.2.2伪代码
如果是空指针，返回空
若该节点已拷贝，返回该节点指针
创建拷贝节点
将拷贝后的指针放入used数组used[node->val]=p;
for 0 to 邻接点数量，将该节点的邻接节点放入拷贝节点邻接数组
递归实现每个节点的更新
返回该节点
2.2.3运行结果
2.2.4分析该题目解题优势及难点
优势：典型的深度优先遍历，不过是换了一种“克隆”方式，加上了创建节点等
难点：本题题意乍一看有点不知所云，感觉就是把输入的东西输出，实际上就是考查图的遍历的，容易被题目忽悠住。
2.3题目及解题代码
2.3.1该题的设计思路
使用广度优先搜索的方法得到从 start 开始能够到达的所有位置，如果其中某个位置对应的元素值为 0，那么就返回 True。
具体的将start加入队列。每次搜索过程中，取出队首的节点 u，它可以到达的位置为 u + arr[u] 和 u - arr[u]。
如果某个位置落在数组的下标范围 [0, len(arr)) 内，并且没有被搜索过，则将该位置加入队尾。只要搜索到一个对应元素值为 0 的位置，我们就返回 True。在搜索结束后，如果仍然没有找到符合要求的位置，我们就返回 False。
时间复杂度：O(n)
空间复杂度：O(n)
2.3.2伪代码
若初始节点为0，直接返回true
定义vector数组
定义队列q
初始节点入队，并记录
while 队不空
出队队头
if 跳跃后节点：后跳下标小于n，前跳下标大于等于0，且节点未访问过
if 节点值为0 返回true end if
入队节点，记录节点
end if
end while
返回 false
2.3.3运行结果
2.3.4分析该题目解题优势及难点
优势：巧妙运用广度优先搜索解决问题，将数组的问题转化为类似于图的问题
难点：有经验的话这题看来就是深度或广度优先搜索问题，但不熟练的话，刚开始会不知道如何下手