广州网站seo营销模板,微信crm客户管理系统,实用网站的设计与实现,wordpress sql优化1. 图的应用总览 在数据结构中图的应用很广泛#xff0c;本文主要从以下四个方面介绍#xff1a; ①最小生成树#xff1a;给定一个无向网络#xff0c;在该网的所有生成树中#xff0c;使得各边权数之和最小的那棵生成树称为该网的最小生成树#xff0c;也叫最小代价…1. 图的应用总览 在数据结构中图的应用很广泛本文主要从以下四个方面介绍 ①最小生成树给定一个无向网络在该网的所有生成树中使得各边权数之和最小的那棵生成树称为该网的最小生成树也叫最小代价生成树。 ②拓扑排序由某个集合上的一个偏序得到该集合上的一个全序这个操作称之为拓扑排序。 ③关键路径在AOE-网中有些活动可以并行地进行所以完成工程的最短时间是从开始点到完成点的最长路径的长度路径长度最长的路径叫做关键路径(Critical Path)。 ④最短路径最短路径问题是图研究中的一个经典算法问题旨在寻找图由结点和路径组成的中两结点之间的最短路径。 2. 最小生成树 问题提出 要在n个城市间建立通信联络网。顶点表示城市权城市间通信线路的花费代价。希望此通信网花费代价最小。 问题分析 答案只能从生成树中找因为要做到任何两个城市之间有线路可达通信网必须是连通的但对长度最小的要求可以知道网中显然不能有圈如果有圈去掉一条边后并不破坏连通性但总代价显然减少了这与总代价最小的假设是矛盾的。 结论 希望找到一棵生成树它的每条边上的权值之和即建立该通信网所需花费的总代价最小 —— 最小代价生成树。 构造最小生成树的算法很多其中多数算法都利用了一种称之为 MST 的性质。 MST 性质设 N (V, E) 是一个连通网U是顶点集 V的一个非空子集。若边 (u, v) 是一条具有最小权值的边其中u∈Uv∈V-U则必存在一棵包含边 (u, v) 的最小生成树。 1普里姆 (Prim) 算法 算法思想 ①设 N(V, E)是连通网TE是N上最小生成树中边的集合。 ②初始令 U{u_0}, (u_0∈V), TE{ }。 ③在所有u∈Uu∈U-V的边(u,v)∈E中找一条代价最小的边(u_0,v_0 )。 ④将(u_0,v_0 )并入集合TE同时v_0并入U。 ⑤重复上述操作直至U V为止则 T(V,TE)为N的最小生成树。 代码实现
void MiniSpanTree_PRIM(MGraph G,VertexType u)//用普里姆算法从第u个顶点出发构造网G的最小生成树T输出T的各条边。//记录从顶点集U到V-U的代价最小的边的辅助数组定义//closedge[j].lowcost表示在集合U中顶点与第j个顶点对应最小权值
{int k, j, i;k LocateVex(G,u);for (j 0; j G.vexnum; j) //辅助数组的初始化if(j ! k){closedge[j].adjvex u;closedge[j].lowcost G.arcs[k][j].adj;
//获取邻接矩阵第k行所有元素赋给closedge[j! k].lowcost}closedge[k].lowcost 0;
//初始U {u}; PrintClosedge(closedge,G.vexnum);for (i 1; i G.vexnum; i) \
//选择其余G.vexnum-1个顶点因此i从1开始循环{k minimum(G.vexnum,closedge);
//求出最小生成树的下一个结点第k顶点PrintMiniTree_PRIM(G, closedge, k); //输出生成树的边closedge[k].lowcost 0; //第k顶点并入U集PrintClosedge(closedge,G.vexnum);for(j 0;j G.vexnum; j){ if(G.arcs[k][j].adj closedge[j].lowcost)
//比较第k个顶点和第j个顶点权值是否小于closedge[j].lowcost{closedge[j].adjvex G.vexs[k];//替换closedge[j]closedge[j].lowcost G.arcs[k][j].adj;PrintClosedge(closedge,G.vexnum);}}}
}2克鲁斯卡尔 (Kruskal) 算法 算法思想 ①设连通网 N (V, E )令最小生成树初始状态为只有n个顶点而无边的非连通图T(V, { })每个顶点自成一个连通分量。 ②在 E 中选取代价最小的边若该边依附的顶点落在T中不同的连通分量上即不能形成环则将此边加入到T中否则舍去此边选取下一条代价最小的边。 ③依此类推直至 T 中所有顶点都在同一连通分量上为止。 最小生成树可能不惟一 3. 拓扑排序 1有向无环图 无环的有向图简称 DAG (Directed Acycline Graph) 图。 有向无环图在工程计划和管理方面的应用除最简单的情况之外几乎所有的工程都可分为若干个称作“活动”的子工程并且这些子工程之间通常受着一定条件的约束例如其中某些子工程必须在另一些子工程完成之后才能开始。 对整个工程和系统人们关心的是两方面的问题 ①工程能否顺利进行 ②完成整个工程所必须的最短时间。 对应到有向图即为进行拓扑排序和求关键路径。 AOV网 用一个有向图表示一个工程的各子工程及其相互制约的关系其中以顶点表示活动弧表示活动之间的优先制约关系称这种有向图为顶点表示活动的网简称AOV网(Activity On Vertex network)。 例如排课表 AOV网的特点 ①若从i到j有一条有向路径则i是j的前驱j是i的后继。 ②若 i , j 是网中有向边则i是j的直接前驱j是i的直接后继。 ③AOV网中不允许有回路因为如果有回路存在则表明某项活动以自己为先决条件显然这是荒谬的。 问题 问题如何判别 AOV 网中是否存在回路 检测 AOV 网中是否存在环方法对有向图构造其顶点的拓扑有序序列若网中所有顶点都在它的拓扑有序序列中则该AOV网必定不存在环。 拓扑排序的方法 ①在有向图中选一个没有前驱的顶点且输出之。 ②从图中删除该顶点和所有以它为尾的弧。 ③重复上述两步直至全部顶点均已输出或者当图中不存在无前驱的顶点为止。 一个AOV网的拓扑序列不是唯一的 代码实现
Status TopologicalSort(ALGraph G)//有向图G采用邻接表存储结构。//若G无回路则输出G的顶点的一个拓扑序列并返回OK否则返回ERROR.//输出次序按照栈的后进先出原则删除顶点输出遍历
{SqStack S;int i, count;int *indegree1 (int *)malloc(sizeof(int) * G.vexnum);int indegree[12] {0};FindInDegree(G, indegree); //求个顶点的入度下标从0开始InitStack(S);PrintStack(S);for(i 0; i G.vexnum; i)if(!indegree[i]) //建0入度顶点栈Spush(S,i); //入度为0者进栈count 0; //对输出顶点计数while (S.base ! S.top){ArcNode* p;pop(S,i);VisitFunc(G,i);//第i个输出栈顶元素对应的顶点也就是最后进来的顶点 count; //输出i号顶点并计数for(p G.vertices[i].firstarc; p; p p-nextarc){ //通过循环遍历第i个顶点的表结点将表结点中入度都减1int k p-adjvex; //对i号顶点的每个邻接点的入度减1if(!(--indegree[k]))push(S,k); //若入度减为0则入栈}//for}//whileif(count G.vexnum){printf(\n该有向图有回路!\n);return ERROR; //该有向图有回路}else{printf(\n该有向图没有回路!\n);return OK;}
}关键路径 把工程计划表示为有向图用顶点表示事件弧表示活动弧的权表示活动持续时间。每个事件表示在它之前的活动已经完成在它之后的活动可以开始。称这种有向图为边表示活动的网简称为 AOE网 (Activity On Edge)。 例如 设一个工程有11项活动9个事件。 事件v_1——表示整个工程开始源点 事件v_9——表示整个工程结束汇点 对AOE网我们关心两个问题 ①完成整项工程至少需要多少时间 ②哪些活动是影响工程进度的关键 关键路径——路径长度最长的路径。 路径长度——路径上各活动持续时间之和。 v_i——表示事件v_i的最早发生时间。假设开始点是v_1从v_1到〖vi〗的最长路径长度。ⅇ(ⅈ)——表示活动a_i的最早发生时间。 l(ⅈ)——表示活动a_i最迟发生时间。在不推迟整个工程完成的前提下活动a_i最迟必须开始进行的时间。 l(ⅈ)-ⅇ(ⅈ)意味着完成活动a_i的时间余量。 我们把l(ⅈ)ⅇ(ⅈ)的活动叫做关键活动。显然关键路径上的所有活动都是关键活动因此提前完成非关键活动并不能加快工程进度。 例如上图中网从从v_1到v_9的最长路径是(v_1,v_2,v_5,v_8,ν_9 )路径长度是18即ν_9的最迟发生时间是18。而活动a_6的最早开始时间是5最迟开始时间是8这意味着如果a_6推迟3天或者延迟3天完成都不会影响整个工程的完成。因此分析关键路径的目的是辨别哪些是关键活动以便争取提高关键活动的工效缩短整个工期。 由上面介绍可知辨别关键活动是要找l(ⅈ)ⅇ(ⅈ)的活动。为了求ⅇ(ⅈ)和l(ⅈ)首先应求得事件的最早发生时间vⅇ(j)和最迟发生时间vl(j)。如果活动a_i由弧〈j,k〉表示其持续时间记为dut(〈j,k〉),则有如下关系 ⅇ(ⅈ) vⅇ(j) l(ⅈ)vl(k)-dut(〈j,k〉) 求vⅇ(j)和vl(j)需分两步进行 第一步从vⅇ(0)0开始向前递推 vⅇ(j)Max{vⅇ(i)dut(〈j,k〉)} 〈i,j〉∈T,j1,2,…,n-1 其中T是所有以第j个顶点为头的弧的集合。 第二步从vl(n-1)vⅇ(n-1)起向后递推 vl(i)Min{vl(j)-dut(〈i,j〉)} 〈i,j〉∈S,in-2,…,0 其中S是所有以第i个顶点为尾的弧的集合。 下面我们以上图AOE网为例先求每个事件v_i的最早发生时间再逆向求每个事件对应的最晚发生时间。再求每个活动的最早发生时间和最晚发生时间如下面表格 在活动的统计表中活动的最早发生时间和最晚发生时间相等的就是关键活动 关键路径的讨论 ①若网中有几条关键路径则需加快同时在几条关键路径上的关键活动。 如a11、a10、a8、a7。 ②如果一个活动处于所有的关键路径上则提高这个活动的速度就能缩短整个工程的完成时间。如a1、a4。 ③处于所有关键路径上的活动完成时间不能缩短太多否则会使原关键路径变成非关键路径。这时必须重新寻找关键路径。如a1由6天变成3天就会改变关键路径。
关键路径算法实现
int CriticalPath(ALGraph G)
{ //因为G是有向网输出G的各项关键活动SqStack T;int i, j; ArcNode* p;int k , dut;if(!TopologicalOrder(G,T))return 0;int vl[VexNum];for (i 0; i VexNum; i)vl[i] ve[VexNum - 1]; //初始化顶点事件的最迟发生时间while (T.base ! T.top) //按拓扑逆序求各顶点的vl值{for(pop(T, j), p G.vertices[j].firstarc; p; p p-nextarc){k p-adjvex; dut *(p-info); //dutj, kif(vl[k] - dut vl[j])vl[j] vl[k] - dut;}//for}//whilefor(j 0; j G.vexnum; j) //求ee,el和关键活动{for (p G.vertices[j].firstarc; p; p p-nextarc){int ee, el; char tag;k p-adjvex; dut *(p-info);ee ve[j]; el vl[k] - dut;tag (ee el) ? * : ;PrintCriticalActivity(G,j,k,dut,ee,el,tag);}}return 1;
} 4.最短路 典型用途交通网络的问题——从甲地到乙地之间是否有公路连通在有多条通路的情况下哪一条路最短 交通网络用有向网来表示顶点——表示城市弧——表示两个城市有路连通弧上的权值——表示两城市之间的距离、交通费或途中所花费的时间等。 如何能够使一个城市到另一个城市的运输时间最短或运费最省这就是一个求两座城市间的最短路径问题。 问题抽象在有向网中A点源点到达B点终点的多条路径中寻找一条各边权值之和最小的路径即最短路径。最短路径与最小生成树不同路径上不一定包含n个顶点也不一定包含n - 1条边。 常见最短路径问题单源点最短路径、所有顶点间的最短路径 1如何求得单源点最短路径 穷举法将源点到终点的所有路径都列出来然后在其中选最短的一条。但是当路径特别多时特别麻烦没有规律可循。 迪杰斯特拉Dijkstra算法按路径长度递增次序产生各顶点的最短路径。 路径长度最短的最短路径的特点 在此路径上必定只含一条弧 v_0, v_1且其权值最小。由此只要在所有从源点出发的弧中查找权值最小者。 下一条路径长度次短的最短路径的特点 ①、直接从源点到v_2v_0, v_2只含一条弧 ②、从源点经过顶点v_1再到达v_2v_0, v_1,v_1, v_2由两条弧组成 再下一条路径长度次短的最短路径的特点 有以下四种情况 ①、直接从源点到v_3v_0, v_3由一条弧组成 ②、从源点经过顶点v_1再到达v_3v_0, v_1,v_1, v_3由两条弧组成 ③、从源点经过顶点v_2再到达v_3v_0, v_2,v_2, v_3由两条弧组成 ④、从源点经过顶点v_1 ,v_2再到达v_3v_0, v_1,v_1, v_2,v_2, v_3由三条弧组成 其余最短路径的特点: ①、直接从源点到v_iv_0, v_i只含一条弧 ②、从源点经过已求得的最短路径上的顶点再到达v_i含有多条弧。 Dijkstra算法步骤 初始时令S{v_0}, T{其余顶点}。T中顶点对应的距离值用辅助数组D存放。 D[i]初值若v_0, v_i存在则为其权值否则为∞。 从T中选取一个其距离值最小的顶点v_j加入S。对T中顶点的距离值进行修改若加进v_j作中间顶点从v_0到v_i的距离值比不加 vj 的路径要短则修改此距离值。 重复上述步骤直到 S V 为止。
算法实现
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix P,ShortPathTable D)
{ // 用Dijkstra算法求有向网 G 的 v0 顶点到其余顶点v的最短路径P[v]及带权长度D[v]。// 若P[v][w]为TRUE,则 w 是从 v0 到 v 当前求得最短路径上的顶点。 P是存放最短路径的矩阵经过顶点变成TRUE// final[v]为TRUE当且仅当 v∈S,即已经求得从v0到v的最短路径。int v,w,i,j,min;Status final[MAX_VERTEX_NUM];for(v 0 ;v G.vexnum ;v){final[v] FALSE;D[v] G.arcs[v0][v].adj; //将顶点数组中下标对应是 v0 和 v的距离给了D[v]for(w 0;w G.vexnum; w)P[v][w] FALSE; //设空路径if(D[v] INFINITY){P[v][v0] TRUE;P[v][v] TRUE;}}D[v0]0;final[v0] TRUE; /* 初始化,v0顶点属于S集 */for(i 1;i G.vexnum; i) /* 其余G.vexnum-1个顶点 */{ /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */min INFINITY; /* 当前所知离v0顶点的最近距离 */for(w 0;w G.vexnum; w)if(!final[w]) /* w顶点在V-S中 */if(D[w] min){v w;min D[w];} /* w顶点离v0顶点更近 */final[v] TRUE; /* 离v0顶点最近的v加入S集 */for(w 0;w G.vexnum; w) /* 更新当前最短路径及距离 */{if(!final[w] min INFINITY G.arcs[v][w].adj INFINITY (min G.arcs[v][w].adj D[w])){ /* 修改D[w]和P[w],w∈V-S */D[w] min G.arcs[v][w].adj;for(j 0;j G.vexnum;j)P[w][j] P[v][j];P[w][w] TRUE;}}}
}
