一.有向无环图(DAG图)
二.拓扑排序(AOV网，顶点表示活动)
- 由集合上的一个偏序得到集合上的一个全序的操作叫拓扑排序
- 在有向无环图中判断工程是否能完成
1.说明
- 采用了邻接表存储树结构
- 运用了栈来存储所有入度为0的元素下标，在出栈时将他们输出并遍历减少所有与他们相连的点的入度
2.代码
void topologicalsort(Graph*g)
{
//创建一个count数组用来存储所有顶点的入度
int*count=(int *)malloc(sizeof(int)*g->numv);
for(int i=0;i<g->numv;i++)
{
count[i]=0;
}
Edge*p;
//遍历邻接表，将所有点的入度进行存储
for(int i=0;i<g->numv;i++)
{
p=g->NodeTable[i].adj;
if(p!=NULL)
{
count[p->dest]++;
p=p->link;
}
}
//相当于入栈
int top=-1;
for(int i=0;i<g->numv;i++)
{
if(count[i]==0)
{
count[i]=top;//该点的count值等于上一个点的坐标值
top=i;//top记录了点的下标
}
}
int v,w;
for(int i=0;i<g->numv;i++)//这层遍历主要是遍历栈中所有元素，而用count[]中的元素只会查找所有未入过栈的，因此count[i]可以等于0
{
if(top==-1)
{
printf("网络中有回路\n");
return;
}
else
{
v=top;//找到栈顶元素的下标
top=count[top];//找到栈中下一个元素下标，即count数组中该点前一个入度为0的数,将top重新赋值，相当于栈中的出栈操作
printf("%c-->",g->NodeTable[v]);
//广度遍历，在邻接表中查找所有与该点相连的点，在count数组中将他们的入度都减1
w=getfirstneighbor(g,g->NodeTable[v].data);
while(w!=-1)
{
count[w]--;
if(count[w]==0)//只会检查所有未入过栈的，因此count中有些记录下标，有些记录入度不冲突
{
count[w]=top;//将count[w]赋值为栈中下一个元素的坐标
top=w;//记录该点的坐标，便于以后输出
}
w=getnextneighbor(g,g->NodeTable[v].data,g->NodeTable[w].data);
}
}
}
}
总结
- 运用了栈的思想，但没有引入栈，利用count数组和top记录，count数组记录了当前入栈点的上一个点的下标，而top记录了当前点的下标，入栈就把top赋值给count[i],然后将top=i就将该点设为了栈顶元素，而出栈时，用v记录栈顶元素坐标top，将top改为count[top]，即栈中栈顶元素的下一个元素。
- count中既记录了点的入度，又记录了栈中元素的下面元素的坐标，但这两个并不冲突，因为在遍历时只遍历了栈中元素，将栈顶元素不断输出，并减去相关的入度，在减少入度的过程中判断这些点的入度是否为0，若为0就入栈。
- 运用了栈先进先出的思想，在拓扑排序中就是如果找到一个入度为0的点，就不再去管其他入度为0的点，但要先将他们入栈，然后按该点一直找邻接点，看看这条路是否能走通，若可以一直在邻接点中找到入度为0的点，就沿这条路一直走下去。
- 在初始化时先将top=-1，需要遍历得到起始入度为0的点，并将它们入栈，这样才能保证栈不空。
三.关键路径(AOE网，顶点表示时间，边表示活动)
- 可以求工程完成的时间。
- 入度为0的点即为工程的起点，也叫源点；出度为0的点为工程的终点，也叫汇点。
- 寻求完成这项活动至少需要多长时间，哪些活动是影响工程进度的关键。
- 关键路径：边的最早开始时间和最晚开始时间相等即为关键路径；边的最早开始时间=点的最早开始时间，边的最晚开始时间=下一个点的最晚开始时间-边的权值；点的最早开始时间为权值最长的路径的值，点的最晚开始时间为从终点的最晚开始时间-权值的最小值
- 运用邻接矩阵表示图
#define MAX_COST 0x7FFFFFFF
//初始化时，将存储边的矩阵上无边的点改为0
void CriticalPath(Grapg*g)
{
//创建存储点的最早开始时间和点的最晚开始时间的数组，并为其初始化
int *ve=(int*)malloc(sizeof(int)*g->numv);
int *vl=(int*)malloc(sizeof(int)*g->numv);
for(int i=0;i<g->numv;i++)
{
ve[i]=0;
vl[i]=MAX_COST;
}
int j,w;
//求ve[]
for(i=0;i<g->numv;i++)
{
j=getfirstneighbor(g,g->list[i]);
while(j!=-1)//找到i的所有邻接点，并为邻接点的ve[]赋值
{
w=getweight(g,i,j);
if(ve[i]+w>ve[j])//找到最大的值
{
ve[j]=ve[i]+w;
}
j=getnextneighbor(g,g->list[i],g->list[j]);
}
}
//求vl[]
int n=g->numv;
//共有n个点，最后一个点的下标为n-1,故倒数第二个点的下标为n-2
for(i=n-2;i>0;i--)
{
j=getfirstneighbor(g,g->list[i]);
while(j!=-1)
{
w=getweight(g,i,j);
if(vl[i]<vl[j]-w)//找到最小值
{
vl[i]=vl[j]-w;
}
j=getnextneighbor(g,g->list[i],g->list[j]);
}
}
//求边的最早开始时间和边的最晚开始时间,判断是否相等后进行输出
int Ae,Al;
for(i=0;i<n;i++)
{
j=getfirstneighbor(g,g->list[i]);
while(j!=-1)
{
int w=getweight(g,i,j);
Ae=ve[i];
Al=vl[j]-w;
if(Ae==Al)
{
printf("<%c,%c>是关键路径\n",g->list[i],g->list[j]);
}
j=getnextneighbor(g,g->list[i],g->list[j]);
}
}
free(ve);
free(vl);
}
总结
- 清楚如何找关键路径之后创建ve,vl,Ae,Al进行操作即可。其中较麻烦的是为ve[]和vl[]赋值。
- 通过for循环和while()就可以遍历所有边并对其操作
四.最短路径(Dijkstra)
- 用邻接矩阵
- 设置path[i]表示i的起始点，即path[i]为起始点，i为终点
- 设置dist[i]表示起始点到i的最短路径，即路径长度
设置两个数组
int *dist=(int *)malloc(sizeof(int));
int *path=(int *)malloc(sizeof(int));
创建函数查找最短路径
void ShortestPath(Graph*g, char v,int dist[],int path[])
{
int n=g->numv;
bool*S=(bool*)malloc(sizeof(bool)*n);//记录是否被访问过
int v=getvpos(g,v);//获得起始顶点的位置坐标
for(int i=0;i<n;i++)
{
dist[i]=getweight(g,v,i);//更新起始点到所有点的路径权重
S[i]=false;//初始化所有点都未被访问过
if(i!=v&&dist[i]<MAX_COST)//初始化path函数，如果不是自身，并且到起始点有路径，就更新它们的起始点数组中的内容，否则就设为-1
{
path[i]=v;
}
else
{
path[i]=-1;
}
}
S[v]=true;
int min;
for(i=0;i<n-1;i++)//除起始点外，所有点都被访问一遍
{
min=MAX_COST;
int u=v;
for(int j=0;j<n;j++)//找到未被访问的点中路径最短的点，遍历了dist[]
{
if(!S[j]&&dist[j]<min)//找到未被访问过的点的路径最小值
{
u=j;
min=dist[j];
}
}
//将点找到之后，更新数组中的数据
S[u]=true;
for(int k=0;k<n;k++)//循环所有未被访问过的点，更新u到他们的所有数据
{
w=getweight(g,u,k);//得到与u相连的所有点的路径
if(!S[k]&&w<MAX_COST&&dist[u]+w<dist[k])//如果它未被访问过，并且有路径，并且从起点到k的路大于经过u到k的路，就重新为其赋值
{
dist[k]=dist[u]+w;
path[k]=u;
}
}
}
}
总结
- 设置两个数组，最后的数据也保存在这两个数组之中，不断遍历循环其实是将所有点都遍历一遍，实现对这两个数组内数据的全部更新
- 在更新时分为两步：第一步先在dist[]数组中找到最小值，并记录该点；第二步将dis[]中原本数据与dist[]中该点数据到各个点的权重进行比较后更新成为更小的那一个。