包头 网站制作,一个地址能注册几个公司,服务器512m内存做网站,静安网站建设关键词优化seo文章目录一、图的基本概念二、图的储存邻接矩阵邻接表十字链表邻接多重表三、图的基本操作四、图的遍历广度优先搜索#xff08;BFS#xff09;深度优先搜索#xff08;DFS#xff09;图的遍历和图的连通性五、最小生成树Prim算法Kruskal算法六、最短路径Dijkstra求单源最短…
文章目录一、图的基本概念二、图的储存邻接矩阵邻接表十字链表邻接多重表三、图的基本操作四、图的遍历广度优先搜索BFS深度优先搜索DFS图的遍历和图的连通性五、最小生成树Prim算法Kruskal算法六、最短路径Dijkstra求单源最短路径Floyd算法求解各顶点间的最短路径问题七、有向无环图DAG图描述表达式八、拓扑排序九、关键路径一、图的基本概念
图G有定点集V和边集E组成记为GVE其中VG表示图G中顶点的有限非空集EG表示图G中顶点之间的关系边集合。用∣V∣|V|∣V∣表示图G中顶点个数用∣E∣|E|∣E∣表示图G中边的条数。图不能是空图最少要有一个顶点。
对于无向图|E|的取值范围为0到n(n−1)/2n(n-1)/2n(n−1)/2有n(n−1)/2n(n-1)/2n(n−1)/2条边的无向图称为完全图。 对于有向图|E|的取值范围为0到n(n−1)n(n-1)n(n−1)有n(n−1)n(n-1)n(n−1)条弧的有向图称为完全图。
若图G和图G’顶点相同E(G’)是E(G)的子集则成G’是G的生成子图。
无向图中任意两个顶点都是连通的。称为连通图。无向图中的极大连通子图称为连通分量。假设一个图有n个顶点如果边数小于n-1其必定是非连通图。
有向图中如果有一对顶点v、w从v到w和从w到v之间都有路径称这两个顶点是强连通的。若图中任何一对顶点都是强连通的称此图为前连通图。有向图的极大强连通子图称为强连通分量。假设一个图有n个顶点至少需要n-1条边构成强连通分量此时为一个环路。
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n则它的生成树有n-1条边。
无向图的全部顶点度之和等于边数的两倍 有向图全部顶点的入度之和与出度之和相等并且等于边数。有向图顶点的度为入度和出度之和。
一个顶点的入度为0、其余顶点入度均为1的有向图称为有向树。
二、图的储存
邻接矩阵
用一个一维数组储存图中顶点的信息有一个二维数组邻接矩阵储存图中边的信息。 无向图的邻接矩阵是对称矩阵实际储存时只需储存三角矩阵元素。
邻接矩阵的空间复杂度为O(∣V∣2)O(|V|^2)O(∣V∣2)
可以很方便地确定两个顶点之间是否有边相连但要确定图中有多少条边必须遍历每个元素。
适合表示稠密图。
邻接矩阵储存结构定义如下
typedef struct{vertexType vex[MaxVertexNum]; // 顶点表edgeType edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵边表int vexNum, edgeNum; // 当前顶点数和边数
}MGraph;邻接表
对图中每个顶点建立一个单链表边表、出边表每个单链表中的结点表示依附与该顶点的边对于有向图表示以该顶点为尾的弧。边表的头指针和顶点的数据采用顺序存储顶点表。
对于无向图所需储存空间为O(2∣E∣∣V∣)O(2|E||V|)O(2∣E∣∣V∣) 对于有向图所需存储空间为O(∣E∣∣V∣)O(|E||V|)O(∣E∣∣V∣)。
可以很方便找到一个顶点的所有临边。 在有向图中求顶点的出度只需计算邻接表的结点个数但求入度需要遍历所有邻接表。
适合表示稀疏图能极大节省存储空间。
邻接表储存结构定义如下
typedef struct{ // 顶点结点vertexType data;ArcNode *first; // 指向第一个依附该顶点的弧
}VerNode, VerList[MaxVertexNum];struct ArcNode{ // 边结点int vertex; // 该边指向的顶点序号edgeType data;struct ArcNode *next; // 指向下一个边
}typedef struct{VerList VerList; // 邻接表int vexNum, edgeNum;
}AlGraph;十字链表
是有向图的一种链式储存结构。每条弧和每个顶点都有一个结点表示。顶点结点顺序存储。
弧结点结构tailvexheadveshlinktlinkinfo作用尾域标识弧尾顶点头域标识弧头顶点指向弧头相同的下一条弧指向弧尾相同的下一条弧携带弧的相关信息
顶点结点结构datafirstinfirstout作用存放顶底数据信息指向以该顶点为弧头的第一个弧结点指向以该顶点为弧尾的第一个弧结点在十字链表中既容易找到以一个顶点为尾的弧又容易找到以一个顶点尾头的弧因而容易求得入度和出度。
邻接多重表
是无向图的一种链式存储结构。每条边和每个顶点也各用一个结点表示。
顶点结点结构markivexilinkjvexjlinkinfo作用标志域记录该边是否被搜索过标识边依附的第一个顶点指向下一条依附ivex的边标识边依附的另一个顶点指向下一条依附jvex的边携带相关信息在邻接多重表中所有依附域同一顶点的边串联在同一链表中。由于每条边依附于两个顶点所以每个边结点同时链接在两个链表中。 对于无向图其邻接多重表和邻接表的差别仅在于同一条表在邻接表中用两个结点表示而在邻接多重表中只有一个结点。
三、图的基本操作
adjacent(G, x, y)判断图G中是否存在边x, yneighbor(G, x)列出图G中于顶点x相邻的边insertVertex(G, x)在图中插入顶点xdeleteVertex(G, x)在图中删除顶点xaddEdge(G, x, y)在图中添加边x, yremoveEdge(G, x, y)在图中删除边x, yfirstNerghbor(G, x)求顶点x的第一个邻接点nextNerghbor(G, x, y)返回除y以外的顶点x的下一个邻接点getEdgeValue(G, x, y)setEdgeValue(G, x, y, v)
四、图的遍历
在遍历图的过程中必须记下每个已访问过的顶点。
广度优先搜索BFS
类似树的层序遍历广度优先搜索是一个分层的查找过程没有回退的过程必须借助一个辅助队列记忆正在访问的顶点的下一层顶点。
int visited[MAX_VERTEX_NUM];void BFSTraverse(Graph G){for(int i0; iG.vexNum; i)visited[i] 0;for(int i0; iG.vexNum; i)if( !visit[i] )BFS(G, i);
}void BFS(Graph G, int v){initQueue(Q);visit(v);visited[v] 1;enQueue(Q, v);while( !isEmpty(Q) ){deQueue(Q, v);for(wfirstNeighbor(G, v); w0; wnextNeighbor(G, v, w)){if(!visited[w]){visit(w);visited[w] 1;enQueue(Q, w);}}}}无论采用邻接表还是邻接矩阵BFS都需要借助一个辅助队列所有顶点均需入队一次。最坏情况下空间复杂度为O(∣V∣)O(|V|)O(∣V∣)。 采用邻接表存储时每个顶点均需被搜索依次时间复杂度为O(∣V∣)O(|V|)O(∣V∣)在搜索任一顶点的边时每一条边至少访问依次总时间复杂度为O(∣E∣)O(|E|)O(∣E∣)。算法总的时间复杂度为O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣) 采用邻接矩阵存储时查找每个顶点的所有邻接点的时间为O(V)O(V)O(V)算法总的时间复杂度为O(∣V∣2)O(|V|^2)O(∣V∣2)。
借助BFS可以求解非带权图的单源最短路径问题。
在广度遍历中可以得到一棵遍历树称为广度优先生成树。邻接矩阵产生的生成树是唯一的而邻接表产生的生成树不唯一。
深度优先搜索DFS
类似树的先序遍历先尽可能“深”的搜索一个图当不能继续向下访问时依次退回最近被访问的顶点若其还有未被访问的邻接顶点则从这个邻接顶点继续该搜索过程。
DFS是一个递归的过程需要借助一个递归工作栈空间复杂度为O(∣V∣)O(|V|)O(∣V∣)。 采用邻接表存储时访问所有顶点的时间复杂度为O(∣V∣)O(|V|)O(∣V∣)查找所有顶点的邻接点的总时间复杂度为O(∣E∣)O(|E|)O(∣E∣)故算法总的时间复杂度为O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)。 采用邻接表存储是查找一个顶点的所有邻接点所需时间为O(|V|)故总的时间复杂度为O(∣V∣2)O(|V|^2)O(∣V∣2)。
借助DFS可以求解有向无环图的拓扑排序问题。
在深度遍历中可以得到一棵遍历树称为深度优先生成树。邻接矩阵产生的生成树是唯一的而邻接表产生的生成树不唯一。
图的遍历和图的连通性
对于无向图若图是连通的则从任一顶点出发仅需一次遍历就可以访问图中的所有顶点。 对于有向图若从初始顶点到图中每个顶点都有路径则能访问到图中的所有顶点。一个有向图的连通子图分为强连通分量和非强连通分量非强连通分量调用一次搜索过程无法访问到所有顶点。
五、最小生成树
最小生成树具有如下特征
最小生成树不是唯一的。但图中各边的权值互不相等是生成树唯一。若无向连通图的边数比顶点数少1它本身就是其的最小生成树。最小生成树边的权值之和总是唯一的且是最小的。
Prim算法
初始时从图中任取一顶点加入树T此时树中只含有一个顶点。之后选择一个与T中顶点距离最近的顶点将顶点和相应的边加入T中。每次操作T中的顶点数和边数都增加1直到所有顶点都加入T。 prim算法基于贪心策略其简单实现如下
def prim(G):T set() # 初始化空边集U {w} # 初始化顶点集添加任一顶点w# 若树中未包含全部顶点选择一个加入while not (V - U): # uv是u∈Uv∈V-U且权值最小的边# 此处最坏情况需要遍历所有n个顶点时间复杂度为Onfind a edge (u, v) U.add(v) # 将选定的点加入顶点集T.add((u, v)) # 将选定的边加入边集算法的时间复杂度为O(∣V∣2)O(|V|^2)O(∣V∣2)适合求解稠密图的最小生成树。
Kruskal算法
初始时只有n个顶点而无边的非连通图T{ V{ } }每个顶点自成一个连通分量。然后按边权值从小到大的顺序查看当前为被选取且权值最小的边若该边依附的两个顶点落在T中不同的连通分量中则将此边加入T。 kruskal算法基于贪心策略其简单实现如下
def kruskal(G):T V # 初始化树仅含所有顶点numS n # 连通分量数while numS 1:# 从边集中找到权值最小的边pop a edge with shortest length (u, v)if (u ,v) belong to different connected components:T.add((u, v)) # 将此边加入生成树中numS numS - 1通常在kruskal算法中采用堆来存放边的集合每次选择边只需O(log∣E∣)O(\log |E|)O(log∣E∣)的时间。此外由于生成树T中的所有边可视为一个等价类每次添加新边的过程类似求解等价类的过程可以采用并查集的数据结构来描述T构造T总的时间复杂度为O(∣E∣log∣E∣)O(|E|\log |E|)O(∣E∣log∣E∣)。适合求解稀疏图的最小生成树。
六、最短路径
把带权路径长度最短的那条路径称为最短路径。 重要性质两点之间的最短路径也包含了路径上其他点间的最短路径。
Dijkstra求单源最短路径
设置一个集合S记录已求得的最短路径的顶点。初始时把源点v0v_0v0放入SSS。集合S每并入一个新顶点viv_ivi都要修改v0v_0v0到集合V−SV-SV−S中顶点的当前最短路径长度。 设置两个辅助数组
dist[]记录从源点v0v_0v0到其他各顶点当前的最短路径长度。它的初态为若从v0v_0v0到viv_ivi有弧则dist[i]设为弧上权值否则置为∞\infty∞。path[]path[i]表示从源点到顶点i最短路径的前驱结点。在算法结束时可根据其值追溯到源点的最短路径。
假设从顶点0出发即v00v_00v00集合SSS最初只包含顶点0邻接矩阵arcs表示带权有向图arcs[i][j]表示有向边i, j的权值。若不存在有向边arcs[i][j]置为∞\infty∞。
Dijkstra算法基于贪心策略步骤如下
初始化集合S初始为{0}dist[]初始值为dist[i] arcs[0][i]。从顶点集合V−SV-SV−S中选出vjv_jvjvjv_jvj是集合V−SV-SV−S中到v0v_0v0距离最短的顶点即满足dist[j]min{dist[i]∣vi∈V−S}dist[j] min \{dist[i]\mid v_i\in V-S\}dist[j]min{dist[i]∣vi∈V−S}此时 vjv_jvj就是当前求得的一条从v0v_0v0出发的最短路径的终点。再令SS∪{j}SS\cup\{j\}SS∪{j}。修改从v0v_0v0到集合V−SV-SV−S上所有顶点vkv_kvk可达的最短路径长度 若dist[j] arcs[j][k] dist[k] 更新dist[k] dist[j] arcs[j][k]。重复二、三步n-1次直到所有顶点都包含在S中。
Djkstra算法并不适用于带负权值的有向图。
算法时间复杂度为O(∣V∣2)O(|V|^2)O(∣V∣2)。
Floyd算法求解各顶点间的最短路径问题
递推产生一个n阶方阵序列A(−1),A(0),...,A(k),...,A(n−1)A^{(-1)}, A^{(0)},...,A^{(k)},...,A^{(n-1)}A(−1),A(0),...,A(k),...,A(n−1)其中A(k)[i][j]A^{(k)}[i][j]A(k)[i][j]表示从顶点viv_ivi到vjv_jvj的路径长度k表示绕行第k个顶点的运算步骤。 初始时对于任意两个顶点若它们之间存在弧则以此边上的权值作为它们之间的最短路径长度若它们不存在有向边则置为∞\infty∞。 以后逐步尝试在原路径中加入顶点k作为中间顶点若增加中间顶点后它们之间的路径长度比原来的路径减少了则以此新路径代替原路径。
算法描述如下 定义一个n阶反正序列A(−1),A(0),...,A(n−1)A^{(-1)}, A^{(0)},...,A^{(n-1)}A(−1),A(0),...,A(n−1)其中
A(−1)[i][j]arcs[i][j]A^{(-1)}[i][j]arcs[i][j]A(−1)[i][j]arcs[i][j]A(k)min{A(k−1)[i][j],A(k−1)[i][k]A(k−1)[k][j]}A^{(k)}\min\{A^{(k-1)}[i][j],A^{(k-1)}[i][k]A^{(k-1)}[k][j]\}A(k)min{A(k−1)[i][j],A(k−1)[i][k]A(k−1)[k][j]}
Floyd算法是一个迭代的过程每迭代一次在从viv_ivi到vjv_jvj的最短路径上就多考虑一个顶点。经过n次迭代后所得到的A(n−1)[i][k]A^{(n-1)}[i][k]A(n−1)[i][k]就是viv_ivi到vjv_jvj的最短路径方阵A(n−1)A^{(n-1)}A(n−1)保存了任意一对顶点之间的最短路径长度。
Floyd算法允许图中有带负权值的边但不允许有包含带负权值边的回路。 Floyd算法同样适合带权无向图因为无向图可视为权值相同往返二重边的有向图。
算法的时间复杂度为O(∣V∣3O(|V|^3O(∣V∣3)但对于中等规模的输入仍然有效。
七、有向无环图DAG图描述表达式
DAG图是描述含有公共子式的表达式的有效工具。 用二叉树描述表达式时相同的子式会重复出现使用DAG图可以对相同子式的共享从而节省存储空间。
八、拓扑排序
AOV网若用DAG图表示一个工程其顶点表示活动用有向边vi,vjv_i,v_jvi,vj表示活动ViV_iVi必须先于ViV_iVi进行则间这种有向图称为顶点表示活动的网络记为AOV网。 拓扑排序由一个有向无环图的顶点组成的序列当且仅当满足下列条件时
每个顶点出现且仅出现一次若顶点A在序列中排在B的前面则在图中不存在从B到A的路径。
称这个序列为该图的一个拓扑排序。每个AOV网都有一个或多个拓扑排序序列。
拓扑排序常用算法如下
从AOV网中选择一个没有前驱的顶点并输出从网中删除该顶点和以该顶点为起点的所有边重复前面两部直到AOV网为空或网中不存在无前驱的顶点位置。后一种情况说明有向图中存在环。
由于输出每个顶点的同时还有删除以它为起点的边故拓扑排序的时间复杂度为O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)。
由于AOC网中各顶点地位平等每个顶点的编号都是人为的因此可以按拓扑排序的结果重新编号生成AOV网的新的邻接存储矩阵这种邻接矩阵可以时三角矩阵。对于一个图若其邻接矩阵是三角矩阵其必存在拓扑排序。
九、关键路径
AOE网在带权有向无环图中若以顶点表示事件以有向边表示活动以边上的权值代表活动的开销则称其为用边表示活动的图记为AOE网。 在AOE网中仅有一个入度为0的点称为开始顶点源点表示整个工程的开始仅有一个出度为0的点称为结束顶点汇点表示整个工程的结束。 从源点到汇点的所有路径中具有最大路径长度的路径称为关键路径它决定了完成整个工程的最短时间。关键路径上的活动称为关键活动。
事件最早发生时间ve(k)ve(k)ve(k) 指从源点viv_ivi到顶点vkv_kvk的最长路径长度决定了所有从vkv_kvk开始的活动能够开工的最早时间。可以用下面的递推公式计算 {ve(源点)0ve(k)max{ve(j)weight(vj,vk)},vk为vj的任意后继\left\{ \begin{array}{l} ve(源点)0\\ ve(k)\max\{{ve(j)}weight(v_j,v_k)\},v_k为v_j的任意后继 \end{array} \right.{ve(源点)0ve(k)max{ve(j)weight(vj,vk)},vk为vj的任意后继 计算ve()ve()ve()时按从前往后的顺序进行可以在拓扑排序的基础上进行。事件最迟发生时间vl(k)vl(k)vl(k) 指在不推迟整个工程完成的前提下即保证它的后继事件在其最迟发生时间内能够发生该事件最迟必须发生时间。可以用下面的递推公式计算 {vl(汇点)ve(汇点)vl(k)min{vl(j)−weight(vk,vj)}vk为vj的任意前驱\left\{ \begin{array}{l} vl(汇点)ve(汇点) \\ vl(k)\min\{vl(j)-weight(v_k,v_j)\}v_k为v_j的任意前驱 \end{array} \right. {vl(汇点)ve(汇点)vl(k)min{vl(j)−weight(vk,vj)}vk为vj的任意前驱 在计算vl()vl()vl()时按从后往前的顺序进行可以在逆拓扑排序的基础上计算可以在计算ve()时设置一个栈记录拓扑序列拓扑排序结束后从栈顶至栈底变为逆拓扑排序序列活动最早开始时间e(i)e(i)e(i) 指活动弧的起点所表示的事件的最早发生时间。若vk,vjv_k,v_jvk,vj表示活动aia_iai则有e(i)ve(k)e(i)ve(k)e(i)ve(k)。活动最迟开始时间l(i)l(i)l(i) 指活动弧的终点所表示的事件的最迟发生事件与该活动所需时间的差值。若vk,vjv_k,v_jvk,vj表示活动aia_iai则有l(i)vl(j)−weight(vk,vj)l(i)vl(j)-weight(v_k,v_j)l(i)vl(j)−weight(vk,vj)。活动最早开始时间和最迟开始时间的差额d(i)d(i)d(i) 指该活动完成的时间余量即在不增加整个工程所需总时间的情况下活动aia_iai可以拖延的时间。d(i)l(i)−e(i)d(i)l(i)-e(i)d(i)l(i)−e(i) 若一个活动的时间余量为0即l(i)e(i)l(i)e(i)l(i)e(i)说明该活动必须要如期完成否则就会拖延整个工程的进度称其为关键活动。
求解关键路径的算法步骤如下
从源点出发令ve(源点)0ve(源点)0ve(源点)0按拓扑有序求其余顶点的最早发生时间从汇点出发令le(汇点)ve(汇点)le(汇点)ve(汇点)le(汇点)ve(汇点)按逆拓扑有序求其余顶点的最迟发生时间根据各顶点的ve()ve()ve()值求所有弧的最早开始时间根据各顶点的vl()vl()vl()值求所有弧的最迟开始时间求AOE网中所有活动的差额找出所有d()0d()0d()0的活动构成关键路径。
关键路径上的所有活动都是关键活动可以通过加快关键活动来缩短整个工程的工期。但不能任意缩短关键活动因为一旦缩短到一定程度关键活动就可能会变成非关键活动。 AOE网中的关键路径不是唯一的对于有多条关键路径的AOE网只提高一条关键路径上的关键活动速度并不能缩短整个工期。
可以判断一个有向图是否有环的算法
深度优先遍历拓扑排序求关键路径预先要使用拓扑排序判断是否有环
