wordpress缓存插件对比,福州网络营销推广产品优化,华为网络营销案例分析,wordpress分类信息发布系统专栏#xff1a;数据结构复习之路
复习完上面四章【线性表】【栈和队列】【串】【数组和广义表】【树和二叉树】#xff0c;我们接着复习 图#xff0c;这篇文章我写的非常详细且通俗易懂#xff0c;看完保证会带给你不一样的收获。如果对你有帮助#xff0c;看在我这么辛…专栏数据结构复习之路
复习完上面四章【线性表】【栈和队列】【串】【数组和广义表】【树和二叉树】我们接着复习 图这篇文章我写的非常详细且通俗易懂看完保证会带给你不一样的收获。如果对你有帮助看在我这么辛苦整理的份上三连一下啦
目录
一 、图的定义和术语
二、图的存储结构
2.1 邻接矩阵数组表示法
2.2 邻接表类似于树的孩子链表表示法
2.3 十字链表 存储有向图
2.4 邻接多重表存储无向图
2.5 总结
三、图的遍历
3.1 广度优先遍历BFS
复杂度分析基于连通图
广度优先生成树
3.2 深度优先遍历DFS
复杂度分析基于连通图
深度优先生成树 四、最小生成树
4.1 普里姆 (Prim) 算法
算法代码分析选择性掌握
4.2 克鲁斯卡尔 (Kruskal) 算法 算法代码分析选择性掌握
五、最短路径
5.1 BFS算法
5.2 Dijkstra 算法
⚠️注意
5.3 Floyd算法
5.4 总结
六、有向无环图及其应用 6.1 DAG描述表达式
咸鱼学长分析法 6.2 拓扑排序
算法代码分析
逆拓扑排序的DFS算法
6.3 关键路径
【例子】详细解题步骤5步骤
结尾 一 、图的定义和术语
图 (Graph) 是一种复杂的非线性数据结构 由顶点集合及顶点间的关系也称弧或边集合组成。可以表示为 G( V , VR )
其中 V 是顶点的有穷非空集合 VR 是顶点之间关系的有穷集合也叫做弧或边集合。弧是顶点
的有序对边是顶点的无序对。
⚠️注意线性表可以是空表树可以是空树但图不可以是空。 上图中画红叉的图是不符合图的定义的
1.1 有向图
若 v, w∈VR则 v, w 表示从 v 到 w 的一条弧且称 v 为弧尾称 w 为弧头此时的图称为有向图。 1.2 无向图
若 v, w∈VR 必有w, v∈VR则以无序对 (v, w) 代表这两个有序对表示 v 和 w 之
间的一条边此时的图称为无向图。 图也分简单图和多重图但在数据结构这门课里基本只探讨简单图解决大多数问题是足够了。
简单图
不存在重复边不存在顶点到自身的边
简单图如下左图多重图如下右图 1.3 完全图
有 n(n-1)/2 条边的无向图即每两个顶点之间都存在着一条边)称为完全图。 1.4 有向完全图
有 n (n - 1) 条弧的有向图 即每两个顶点之间都存在着方向相反的两条弧称为有向完全图。 1.5 稀疏图 与 稠密图
稀疏图含有很少条边或弧的图。
稠密图含有很多条边或弧的接近完全图的图。
1.6 权
与图的边或弧相关的数这些数可以表示从 一个顶点到另一个顶点的距离或耗费。
1.7 网 带权的图。
1.8 子图 1.9 邻接点
若 (v, v´) 是一条边则称顶点 v 和 v´互为邻接点或称 v 和 v´相邻接称边 (v, v´) 依附于顶点 v
和 v´或称 (v, v´) 与顶点 v 和 v´ 相关联。
若 v, v´ 是一条弧则称顶点 v 邻接到 v´顶点 v´邻接自顶点 v。并称弧 v, v´ 与顶点 v 和 v´ 相关联。
1.10 度
无向图中顶点 v 的度是和 v 相关联的边的数目记为 TD(v)。 对于有向图 入度有向图中以顶点 v 为头的弧的数目称为 v 的入度 记为ID(v)。
出度有向图中以顶点 v 为尾的弧的数目称为 v 的出度 记为OD(v)。
那么有向图中顶点 v 的度为入度和出度之和即TD(v) ID(v) OD(v)。 【重要的知识】 1.11 路径
顶点 和 顶点之间的一条路径是指顶点序列如vi到vj的一条路径是vi, v0, v1, v2, …, v7, vj
对于有向图路径也是有向的。
路径长度路径上边或弧的数目。
1.12 简单路径
简单路径序列中顶点两端点除外不重复出现的路径。
1.13 回路
回路环第一个顶点和最后一个顶点相同的路径。
简单回路简单环前后两端点相同的简单路径。
1.14 点到点的距离
从顶点 vi 出发到顶点 vj 的最短路径如果从vi到vj根本就不存在路径则记该距离为无穷
1.15 连通 与 强连通
无向图中若从顶点vi 到 vj 有路径存在则称vi 和 vj 是连通的。
连通图图中任意两个顶点都是连通的。
【考点】对于 n 个顶点的无向图G
若G是连通图则最少有n - 1条边若G是非连通图则最多可能有 条边
有向图中若从顶点vi 到 vj 和 从顶点vj 到 vi 之间都有路径存在则称这两个顶点是强连通的。
强连通图图中任意两个顶点都是强连通的。
【考点】对于 n 个顶点的有向图G
若G是强连通图则最少有n 条边形成回路 1.16 连通分量
连通分量无向图的极大连通子图不存在包含它的更大的连通子图任何连通图的连通分量只有一个即其本身
非连通图有多个连通分量非连通图的每一个连通部分其实就是每个独立的最大连通子图。 1.17 强连通分量
强连通分量有向图的极大强连通子图任何强连通图的强连通分量只有一个即其本身
非强连通图有多个强连通分量。 1.18 生成树
生成树所有顶点均由边连接在一起但不存在回路的图。一个图可以有许多棵不同的生成树。 所有生成树具有以下共同特点 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图 一个有 n 个顶点的连通图的生成树有 n-1 条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路。 ⚠️注意含 n 个顶点 n-1 条边的图不一定是生成树。
1.18 生成森林
对于非连通图其每个连通分量可以构造 一棵生成树合成起来就是一个生成森林。
1.19 带权路径长度
当图是带权图时一条路径上所有边的权值之和称为该路径的带权路径长度。
1.20 有向树
有向树如果一个有向图恰有一个顶点的入度为 0 其余顶点的入度均为 1 则是一棵有向树。
二、图的存储结构
2.1 邻接矩阵数组表示法 一个有 n 个顶点的图可用两个数组存储。其中一个 一维数组存储数据元素顶点的信息另一个二维数组 邻接矩阵存储数据元素之间的关系边或弧的信息。 #define MaxVertexNum 100 //顶点数目的最大值
typedef char VertexType; //顶点的数据类型下文我用的字母表示
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{VertexType Vex[MaxVertexNum]; //顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵边表int vexnum, arcnum; //图的当前顶点数 和 边数/弧数
} MGraph;邻接矩阵设 G (V, VR) 是具有 n 个顶点的图顶点 的顺序依次为 {v1, v2, …, vn}则 G 的邻接矩阵是具有如下性质的 n 阶方阵 在讲解之前不妨带着如下问题思考下去 观察无向图的邻接矩阵的表示不难看出
第 i 个结点的度 第 i 行或第 i 列的非零元素个数。需要O (| v |) 的时间复杂度。
对于有向图
第 i 个结点的出度 第 i 行的非零元素个数
第 i 个结点的入度 第 i 列的非零元素个数
第 i 个结点的度 第 i 行 和 第 i 列的非零元素个数之和。需要O (| v |) 的时间复杂度。 观察上述邻接矩阵的表示
该邻接矩阵的空间复杂度只和顶点数相关和实际的边数无关。
适合用于存储稠密图。 观察无向图的邻接矩阵的表示不难看出
无向图的邻接矩阵对称可压缩存储有 n 个顶点的无向图所需存储空间为 n(n-1)/2。
对称矩阵的相关知识我已经在这篇博客讲解【数据结构复习之路】数组和广义表严蔚敏版
这里的邻接矩阵的压缩存储没有存储主对角线。 如何存储带权图 邻接矩阵法的性质矩阵相乘 2.2 邻接表类似于树的孩子链表表示法
当为稀疏图时邻接矩阵的存储显然很浪费空间因此适用于稀疏图的邻接表结构如下 实际上邻接表就是由一个顺序表和多个单链表组成的顺序表用来存储图中的所有顶点各个单链表存储和当前顶点有直接关联的边或弧。 #define MAX_VERTEX_NUM 20//图中顶点的最大数量
#define VertexType char//图中顶点的类型
#define InfoType int*//图中弧或者边包含的信息的类型
typedef struct ArcNode{int adjvex;//存储边或弧即另一端顶点在数组中的下标struct ArcNode * nextarc;//指向下一个结点InfoType info;//记录边或弧的其它信息 对于非网图可以不需要
}ArcNode;
typedef struct VNode{VertexType data;//顶点的数据域ArcNode * firstarc;//指向下一个结点
}VNode,AdjList[MAX_VERTEX_NUM];//存储各链表首元结点的数组
typedef struct {AdjList vertices;//存储图的邻接表int vexnum,arcnum;//记录图中顶点数以及边或弧数int kind;//记录图的种类可忽略
}ALGraph; 无向图存储结构示意图考试可能要让你画图哦 无向图的邻接表特点 若无向图中有 n 个顶点、 e 条边则其邻接表需 n 个头结点和 2 e 个表结点。适宜存储稀疏图。 无向图中顶点 v i 的度为第 i 个单链表中的结点数。 有向图存储结构示意图 对于有向图邻接表特点 顶点 v i 的 出度 为第 i 个 单链表中的结点个数。 顶点 v i 的 入度 为整个 单 链表中邻接点域值是 i -1 的结点个数 。
对于有向图逆邻接表特点 顶点 v i 的 入度 为第 i 个 单链表中的结点个数。 顶点 v i 的 出度 为整个 单 链表中邻接点域值是 i -1 的结点个数 。 【考点】有些时候可能会考察你写一个求有向图中某个顶点V的入度和出度的函数。 //计算某个顶点 V的入度
int InDegree(ALGraph graph, char V) {int i, j, index -1;int count 0;//找到 V 在顺序表中的下标for (j 0; j graph.vexnum; j) {if (V graph.vertices[j].data) {index j;break;}}if (index -1) { //找不到就返回-1 return -1;}//遍历每个单链表找到存储 V 下标的结点并计数for (j 0; j graph.vexnum; j) {ArcNode* p graph.vertices[j].firstarc;while (p) {if (p-adjvex index) {count;}p p-nextarc;}}return count;
} 不难看出时间复杂度为 //计算某个顶点的出度
int OutDegree(ALGraph graph, char V) {int j;int count 0;for (j 0; j graph.vexnum; j) {if (V graph.vertices[j].data) {ArcNode* p graph.vertices[j].firstarc;while (p) {count;p p-nextarc;}break;}}//如果查找失败返回 -1 表示计算失败if (j graph.vexnum) {return -1;}return count;
} 可能一个结点V和其他结点都有边相连时间复杂度为 上图邻接表的存储结构中表结点的顺序可以随意变化取决于建立邻接表的算法及边的输入次序。所有图的邻接表表示方式并不唯一而邻接矩阵一定是唯一的。
【总结】 2.3 十字链表 存储有向图
十字链表(Orthogonal List)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。
这种存储方式完美的解决了计算有向图的出度、入度的复杂性。
这种十字链表的存储结构和上上章讲《数组和广义表》里面稀疏矩阵的链式存储非常相似只是结点中各字段的含义发生了变化。 基于上述结点结构我们可以画出如下有向图的十字链表的存储示意图
不难看出空间复杂度为
从上图的存储结构可以看出
● 顺着绿色的线路找就能找到指定顶点的所有出边计算出度。
● 顺着橙色的线路找就能找到指定顶点的所有入边计算入度。 存储结构代码 #define MAX_VERTEX_NUM 20 //图中顶点的最大数量
#define InfoType int* //表示弧额外信息的数据类型
#define VertexType char //图中顶点的数据类型
//表示链表中存储弧的结点
typedef struct ArcBox {int tailvex, headvex; //弧尾、弧头对应顶点在顺序表中的位置下标struct ArcBox* hlik, * tlink; //hlik指向下一个以当前顶点为弧头的弧结点//tlink 指向下一个以当前顶点为弧尾的弧结点//InfoType info; //存储弧相关信息的指针
}ArcBox;//表示顺序表中的各个顶点
typedef struct VexNode {VertexType data; //顶点的数据域ArcBox* firstin, * firstout; //指向以该顶点为弧头和弧尾的链表首个结点
}VexNode;//表示十字链表存储结构
typedef struct {VexNode xlist[MAX_VERTEX_NUM]; //存储顶点的顺序表int vexnum, arcnum; //记录图的顶点数和弧数
}OLGraph; 【考点】有些时候可能会考察你写一个基于十字链表存储求有向图中某个顶点V的入度和出度的函数。 //计算某顶点的出度和有向图邻接表基本一样
int outdegree(OLGraph G, VertexType x) {int i;int num 0;//遍历整个顺序表for (i 0; i G.vexnum; i) {//找到目标顶点if (x G.xlist[i].data) {//从该顶点的 firstout 指针所指的结点开始遍历ArcBox* p G.xlist[i].firstout;while (p){num;//遍历 tlink 指针指向的下一个结点p p-tlink;}break;}}if (i G.vexnum) {printf(图中没有指定顶点\n);return -1;}return num;
} 时间复杂度为 //计算某顶点的入度
int indegree(OLGraph G, VertexType x) {int i;int num 0;//遍历整个顺序表for (i 0; i G.vexnum; i) {//找到目标顶点if (x G.xlist[i].data) {//从该顶点的 firstin 指针所指的结点开始遍历ArcBox* p G.xlist[i].firstin;while (p){num;//遍历 hlink 指针指向的下一个结点p p-hlik;}break;}}if (i G.vexnum) {printf(图中没有指定顶点\n);return -1;}return num;
} 时间复杂度为 有些时候info权值字段省略而简画成这样的存储结构 考试可没有那些橙色和绿色的结点颜色帮助你区分所有要理解每个结点和其字段的作用。 2.4 邻接多重表存储无向图 实际场景中如果需要对无向图中的边做大量的插入或删除操作不推荐使用邻接表存储结构因为每条边在邻接表都存有两份同样的操作需要处理两次。这种情况下可以优先考虑邻接多重表存储结构。 邻接多重表(adjacent multiList)是无向图网的另一种链式存储结构。
在此存储结构中图的顶点信息存放在顶点数组中数组元素有两个域
● data域存放与顶点相关的信息
● firstedge域指向一个单链表此单链表存储所有依附于该顶点的边的信息。 这些单链表的一个表结点对应一条边表结点有六个域
● mark为标志域用来标记该边是否被访问过。例如遍历无向图中的所有边借助 mark 标志域可以避免重复访问同一条边
● ivex和jvex分别存放该边两个顶点在无向图中的位置
● info域存放该边相关的信息实际上就是弧的权值对于无向图info域可省略;
● ilink指向下一条依附于顶点ivex的边对应的表结点;
● jlink指向下一条依附于顶点jvex的边对应的表结点。 根据上述结点结构可画出如下的邻接多重表结构 空间复杂度
解析上图
如果要找依附于B结点的结点这是是A、C、E首先通过B结点的 firstedge指针域找到AB这条边结点然后通过这条边结点的 jlink指针域指向下一条依附于顶点jvexB结点的边对应的边结点CB同理再找到边结点EB。
对于其他结点分析同上。
代码实现 #define MAX_VERTEX_NUM 20 //图中顶点的最大数量
#define InfoType int* //边结点中info域的数据类型
#define VertexType int //顶点的数据类型
typedef enum { unvisited, visited }VisitIf; //边标志域
//表示链表中的各个结点
typedef struct EBox {VisitIf mark; //标志域int ivex, jvex; //边两边顶点在顺序表中的位置下标struct EBox* ilink, * jlink; //分别指向与ivex、jvex相关的下一个边结点InfoType* info; //边的其它信息
}EBox;
//存储图中的各个顶点
typedef struct VexBox {VertexType data; //顶点数据域EBox* firstedge; //指向当前顶点对应的链表
}VexBox;
//表示邻接多重表结构
typedef struct {VexBox adjmulist[MAX_VERTEX_NUM]; //存储图中顶点的顺序表int vexnum, edgenum; //记录图中的顶点数量和边数量
}AMLGraph; 【考点】将(V1,V2)这条边插入到邻接多重表中画图也必须掌握
Status InsertEdge(AMLGraph* G, VertexType V1, VertexType V2);
假设如图所示现在要插入AB这条边 插入完成后应为下图所示
代码实现非常容易理解 int LocateVex(AMLGraph* G, VertexType v) {int i;//遍历一维数组找到变量vfor (i 0; i G-vexnum; i) {if (G-adjmulist[i].data v) {break;}}//如果找不到输出提示语句返回 -1if (i G-vexnum) {printf(no such vertex.\n);return -1;}return i;
}Status InsertEdge(AMLGraph* G, VertexType V1, VertexType V2) {int V1Add LocateVex(G, V1);int V2Add LocateVex(G, V2);EBox* node NULL;if (V1Add 0 || V2Add 0) {printf(输入边信息有误\n);exit(-1);}//构建一个新结点node (EBox*)malloc(sizeof(EBox));node-mark unvisited;node-ivex V1Add;node-jvex V2Add;//用头插法将 node 结点链接到 V1 顶点的链表中node-ilink G-adjmulist[V1Add].firstedge;G-adjmulist[V1Add].firstedge node;//用头插法将 node 结点链接到 V2 顶点的链表中node-jlink G-adjmulist[V2Add].firstedge;G-adjmulist[V2Add].firstedge node;return 1;
} 对于删除一条边的操作你只需要掌握如何画图就行了考试让你写其实现的代码这个的确要比插入操作难所以多半不会考察的。 如果是删除一个结点比如删除下图中的E结点然后画出最终的邻接多重表 除了删除与E结点本身的数据之外还要删除所有这些与E相连的边的信息最后要在ilink和jlink无指向边结点时将其设置为NULL。 2.5 总结
必须记住 到这里图的存储结构就基本讲完了考试时可能还会结合邻接矩阵和邻接表的存储结构考察
大家图的一些基本操作基于十字链表和邻接多重表的基本操作考察不是很多比如 我就随便挑几个实现一下吧剩下的可以自行完成。
【1】对于第2个函数Neighbors(G , x)若基于邻接表实现的求与结点x邻接的边这和求结点的度没有区别这我已经在上文实现了。其实你把求度的操作思想搞懂了上述基本操作都是非常简单的
【2】下面的这两个函数一般用于基于邻接矩阵存储的图中这里我只写了基于邻接表存储的函数是因为我把基于邻接矩阵存储的这两个函数写到了下面的图的遍历那一章。 //基于邻接表存储的无向图
int FirstNeighbor(ALGraph G, char x) {int j;for (j 0; j G.vexnum; j) {if (x graph.vertices[j].data) {ArcNode* p graph.vertices[j].firstarc;if (p NULL){return -1; //x没有邻接点 } else {return p-adjvex;}}}//如果图中不存在 x if (j graph.vexnum) {return -1;}
} 【3】 //基于邻接表存储的无向图
int NextNeighbor(ALGraph G, char x, char y) {int j;for (j 0; j G.vexnum; j) {if (x graph.vertices[j].data) {ArcNode* p graph.vertices[j].firstarc;while (p){if (p-adjvex y p-nextarc ! NULL){return p-nextarc-adjvex;}p p-nextarc;}return -1;//y是x的最后一个邻接点 }}
} 三、图的遍历
从图的任意指定顶点出发依照某种规则去访问图中所有顶点且每个顶点仅被访问一次这一过程叫做图的遍历。
图的遍历按照深度优先和广度优先规则去实施通常有深度优先遍历法Depth_First Search——DFS 和 广度优先遍历法 Breadth_Frist Search——BFS两种。
3.1 广度优先遍历BFS
图的广度优先遍历类似于树的层序遍历。
过程从图的某一结点出发首先依次访问该结点的所有邻接顶点 Vi1, Vi2, …, Vin 再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点搜索相邻的顶点时有可能搜到已经访问过的顶点重复此过程直至所有顶点均被访问为止。
要点
找到与一个顶点相邻的所有顶点标记哪些顶点被访问过需要一个辅助队列
对于第一个要点可以通过之前的 FirstNeighbor(ALGraph G, char x)和NextNeighbor(ALGraph G, char x, char y)两个函数实现。
对于第二个要点可以通过一个访问标记数组 bool visited[MAX_VERTEX_NUM]实现
对于第三个要点在栈和队列里面已经讲过队列的初始化和基本操作了就不多言了。
补充利用图的广度优先遍历 可以查找图上的所有顶点比如查找如下的G顶点。 当然大多数图可能是非连通图因此我们要想遍历所有顶点只能用一个for循环查询每个顶点是否已被访问如果没有访问就以它为起点进行BFS。 for (int i 0 ; i G.vexnum ; i)
{if (!visited[i]) {BFS(G,i); //对每个连通分量调用一次BFS }
} 基于上面讲的存储结构这里给出无向图顺序存储代码邻接矩阵邻接表方法同上。 int LocateVex(MGraph* G, VertexType v) {int i;//遍历一维数组找到变量vfor (i 0; i G-vexnum; i) {if (G-vexs[i] v) {break;}}//如果找不到输出提示语句返回-1if (i G-vexnum) {printf(no this vertex\n);return -1;}return i;
} int FirstAdjVex(MGraph G, int v)
{int i;//对于数组下标 v 处的顶点找到第一个和它相邻的顶点并返回该顶点的数组下标for (i 0; i G.vexnum; i) {if (G.edge[v][i]) {return i;}}return -1;
}int NextAdjVex(MGraph G, int v, int w)
{int i;//对于数组下标 v 处的顶点从 w 位置开始继续查找和它相邻的顶点并返回该顶点的数组下标for (i w 1; i G.vexnum; i) {if (G.edge[v][i]) {return i;}}return -1;
} //广度优先搜索
void BFSTraverse(MGraph G) {int v, u, w;Queue* Q NULL;InitQueue(Q); //初始化一个队列 for (v 0; v G.vexnum; v) { //将用做标记的visit数组初始化为falsevisited[v] false;}//遍历图中的各个顶点for (v 0; v G.vexnum; v) { //如果是连通图可以不加这个循环if (!visited[v]) { //若当前顶点尚未访问从此顶点出发找到并访问和它连通的所有顶点printf(%d , G.vexs[v]);//访问顶点并更新它的访问状态visited[v] true;EnQueue(Q, G.vexs[v]); //将顶点入队while (!QueueEmpty(Q)) { //遍历队列中的所有顶点DeQueue(Q, u); //从队列中的一个顶点出发u LocateVex(G, u);//找到顶点对应的数组下标//遍历紧邻 u 的所有顶点for (w FirstAdjVex(G, u); w 0; w NextAdjVex(G, u, w)) {//将紧邻 u 且尚未访问的顶点访问后入队if (!visited[w]) {printf(%d , G.vexs[w]);visited[w] true;EnQueue(Q, G.vexs[w]);}}}}}DelQueue(Q); //最后销毁队列
}复杂度分析基于连通图
空间复杂度
BFS是一种借用队列来存储的过程。无论是在邻接表还是邻接矩阵中存储都需要借助一个辅助队列v个顶点均需入队最坏的情况下空间复杂度为。
时间复杂度
邻接矩阵存储的图
查找每个顶点的邻接点所需时间为即该节点所在的该行的所有列。又因为有v个顶点 查找所有邻接点的总时间复杂度为 加上对每个结点进行入队出队的复杂度 , 所以总的时间复杂度为O(V^2 V)。省略低阶复杂度最终时间复杂度为
邻接表存储的图
查找各个顶点的邻接点共需要的时间再加上每个结点进行入队出队的复杂度
所以总的时间复杂度为
广度优先生成树
图的邻接矩阵表示是唯一的但对于邻接表来说若边的输入次序不同生成的邻接表也不同。因此对于同样一个图基于邻接表的遍历所得到的BFS序列是不唯一的比如广度优先生成树。
比如下图我们以2号顶点为起点进行BFS遍历遍历序列2 16 537 48 对应的广度优先生成树入下右图 当我将邻接表中第6号结点邻接的3 和 7改变顺序那么它的遍历序列就会发生改变那么其广度优先生成树自然也会随之改变 对非连通图的广度优先遍历可得到广度优先生成森林 ⚠️注意
上述代码和图解都是以无向图为基础的而对于有向图并非都是强连通图因此要想确保能遍历到所有的顶点还是要在BFS外套一个这个代码 for (int i 0 ; i G.vexnum ; i)
{if (!visited[i]) {BFS(G,i); }
} 比如 1、从1出发遍历顺序15 2 36 478 需要调用 4次BFS函数
2、从7出发遍历顺序73682415 需要调用 1次BFS函数
3.2 深度优先遍历DFS
图的深度优先遍历类似于树的先根遍历
过程
访问指定的起始顶点若当前访问的顶点的邻接顶点有未被访问的则任选 一个访问之反之退回到最近访问过的顶点直到与起始顶点相通的全部顶点都访问完毕若此时图中尚有顶点未被访问则再选其中一个顶点作为起始顶点并访问之转 2 反之遍历结束。 补充利用图的深度优先遍历 可以查找图上的所有顶点比如查找如下的G顶点下图中D顶点没有访问的原因是当我们找到G顶点后就让程序逐步退出递归不需要继续查找下去了完成查找到G顶点的任务就了。 要点
对于与第 v 个顶点相邻的其它顶点逐个调用深度优先搜索算法递归调用标记哪些顶点被访问过 当然大多数图可能是非连通图因此我们要想遍历所有顶点只能用一个for循环查询每个顶点是否已被访问如果没有访问就以它为起点进行DFS。 for (int v 0; v G.vexnum; v) {//如果该顶点的标记位为false就调用深度优先搜索算法if (!visited[v]) {DFS(G, v);}} 基于上面讲的存储结构这里给出无向图顺序存储代码邻接矩阵邻接表方法同上。 void DFSTraverse(MGraph G) {int v;//visit数组记录各个顶点是否已经访问过全部初始化为 falsefor (v 0; v G.vexnum; v) {visited[v] false;}for (v 0; v G.vexnum; v) {//如果该顶点的标记位为false就调用深度优先搜索算法if (!visited[v]) {DFS(G, v);}}
} void DFS(MGraph G, int v) {int w;printf(%d , G.vexs[v]); //访问第 v 个顶点visited[v] true; //将第 v 个顶点的标记设置为true//对于与第 v 个顶点相邻的其它顶点逐个调用深度优先搜索算法for (w FirstAdjVex(G, v); w 0; w NextAdjVex(G, v, w)) {//如果该顶点的标记为false证明尚未被访问就调用深度优先搜索算法if (!visited[w]) {DFS(G, w);}}
} 复杂度分析基于连通图
空间复杂度
由于是递归遍历因此空间复杂度来自递归工作栈的消耗最坏情况下递归深度为 最好情况下递归深度为 如下图其递归栈最多占用一层。
如果题目没有特别指明最好还是最坏的空间复杂度。就写
时间复杂度 邻接矩阵存储的图
访问 |V| 个顶点需要的时间查找每个顶点的邻接点都需要的时间而总共有 |V|个顶点所有总的时间复杂度为
邻接表存储的图
访问 |V| 个顶点需要的时间查找各个顶点的邻接点共需要的时间所有总的时间复杂度为 【练习】注意邻接表结点的邻接顺序 比如还是上面那个图其邻接表结点的邻接顺序可以不一样因此其深度优先遍历序列也就不一样。但一个图的邻接矩阵必须是唯一的。 深度优先生成树 深度优先生成森林
对非连通图的深度优先遍历可得到深度优先生成森林 图的遍历与图的连通性
在BFS里已经提到过了对无向图进行BFS/DFS遍历调用BFS/DFS函数的次数 连通分量数
对应连通图BFS/DFS都只需调用一次。
对有向图进行BFS/DFS遍历调用BFS/DFS函数的次数要严格根据有向图中各顶点间的邻接决定。若起始顶点到其他各顶点都有路径则只需要调用1次BFS/DFS函数。
对应强连通图BFS/DFS都只需要调用一次从任一结点出发。 四、最小生成树
在这之前我们已经介绍了生成树的基本概念 最小生成树给定一个无向网络在该网的所有生成树中使得各边权数之和最小的那棵生成树称为该网的最小生成树也叫最小代价生成树。
只有连通图才有生成树非连通图只有生成森林。
下面介绍构造最小生成树方法重要
4.1 普里姆 (Prim) 算法
书上的那一些枯燥的数学式的算法分析就不写出来了直接给出实际做法
要点从某一个顶点开始构建生成树每次将代价最小的新顶点纳入生成树保证不形成回路的前提下直到所有顶点都纳入为止。 ⚠️注意观察上面根据Prim算法的最小生成树的构建过程
每次将代价最小的新顶点纳入生成树时你的红线都必须是连通的。最小生成树可能有多个但边的权值之和总是唯一且最小的【解释】 【解释】比如当我们用Prim算法在上图中当进行到第二步时P城既可以先连接矿场也可以先连接渔村。则最后得到的最小生成树就不同。 当然你的起点也可以从任一结点开始但最后得到的最小生成树都是一样的结果。
算法代码分析选择性掌握 这里以一道Prim算法的模板题为基础进行算法代码的分析 这位佬画的图解形象生动我就不写了可能还没他写的好
Prim算法求最小生成树图解详细代码注释带上了保存路径 时间复杂度适合用于边稠密图。 4.2 克鲁斯卡尔 (Kruskal) 算法
要点每次选择一条权值最小的边使这条边的两头连通原本已经连通的就不选直到所有结点都连通保证不形成回路的前提下。 ⚠️注意观察上面根据KrusKal算法的最小生成树的构建过程
每次选择一条权值最小的边不用保证红线必须连通但必须保证不能形成回路最小生成树可能有多个但边的权值之和总是唯一且最小的 算法代码分析选择性掌握 这也是一道Kruskal算法的模板题可根据此题分析算法代码的实现
图解实在不想画为了助于大家理解还是看这位佬画的吧
注意这个代码的实现会采用到并查集判断是否会产生回路不会的可以在CSDN上搜搜。
Kruskal算法求最小生成树---海绵宝宝来喽 时间复杂度 适合用于边稀疏图 五、最短路径
最短路径问题是图论研究中的一个经典算法问题 旨在寻找图由结点和路径组成的中两结点之间的最短路径。
5.1 BFS算法
⚠️注意BFS算法虽然可以求解最短路径问题但是需要注意的是该算法只能求解非带权图的单源最短路径问题或者说带权值相同且为1的图单源最短路径问题。
说以局限性很大。
由最终的数据你可以求顶点 2 到其他顶点的最短路径。
比如2到8的最短路径为d[8] 3
而通过path[ ]数组能求得最短路径
因为path[8] 7 , path[7] 6 , path[6] 2
所以2到8的最短路径为2 - 6 - 7 - 8 //求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u){//d[i]表示从u到i结点的最短路径for(int i0; iG.vexnum; i){d[i] MAX; //初始化路径长度path[i] -1; //最短路径从哪个顶点过来}d[u] 0;visited[u] true;enQueue(Q, u);while(!isEmpty(Q)){ //BFS算法主过程deQueue(Q, u); //队头元素u出队for(wfirstNeighbor(G,v); w0; wnextNeighbor(G,v,w)){if(!visited[w]){ //w为u的尚未访问的邻接顶点d[w] d[u] 1; //路径长度加1path[w] u; //最短路径应从u到wvisited[w] true; //设已访问标志enQueue(Q, w); //顶点w入队}//if}//for}//while
}上述代码和BFS广度优先遍历差别不大。
5.2 Dijkstra 算法
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始采用贪心算法的策略每次遍历到始点距离最近且未访问过的顶点的邻接节点直到扩展到终点为止。
这里我直接以书P189那个例子为基础进行讲解附带书上的源代码 先给出算法代码然后结合着代码来讲可能会更容易理解 /* 迪杰斯特拉Dijkstra) 算法*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc path, ShortPathTable dist)
{int v, w, k, min;int final[MaxVerterNum]; // final[w] 1表示求得顶点 v0 至 vw的最短路径即已访问过顶点vwfor (v 0; v G.vexNum; v){final[v] 0; // 全部顶点初始化为未知最短路径状态dist[v] G.Edge[v0][v]; // 将与v0点有连线的顶点加上权值path[v] -1; // 初始化路劲数组p为-1}dist[v0] 0; // v0至v0路径为0final[v0] 1; // v0至v0不需要路径/* 开始主循环每次求得v0到某个顶点v的最短路径*/for (v 1; v G.vexNum; v){min INFINITY; // 当前所知离v0顶点的最近距离for (w 0; w G.vexNum; w) // 寻找离v0最近的顶点{if (!final[w] dist[w] min){k w;min dist[w]; // w顶点离v0顶点更近}}final[k] 1; // 将目前找到的最近的顶点置为1for (w 0; w G.vexNum; w) // 修正当前最短路径及距离{/* 如果经过v顶点的路径比现在这条路径的长度短的话 */if (!final[w] (min G.Edge[k][w] dist[w])){dist[w] min G.Edge[k][w]; // 修改当前路径长度path[w] k;}}}
} 【1】初始化执行上述代码前面一部分
注意这里的path[2] 、path[4]、path[5]没有初始化为0主要是没必要因为path[i] -1就表明 i 的前驱结点一定就是V0。
final[i]标记各顶点是否已找到最短路径dist[i]最短路径长度path[i]路径上的前驱 int v, w, k, min;int final[MaxVerterNum]; // final[w] 1表示求得顶点 v0 至 vw的最短路径即已访问过顶点vwfor (v 0; v G.vexNum; v){final[v] 0; // 全部顶点初始化为未知最短路径状态dist[v] G.Edge[v0][v]; // 将与v0点有连线的顶点加上权值path[v] -1; // 初始化路劲数组p为-1}dist[v0] 0; // v0至v0路径为0final[v0] 1; // v0至v0不需要路径 【2】找到距离V0最近的顶点并修改当前路径长度 /* 开始主循环每次求得v0到某个顶点v的最短路径*/for (v 1; v G.vexNum; v){min INFINITY; // 当前所知离v0顶点的最近距离for (w 0; w G.vexNum; w) // 寻找离v0最近的顶点{if (!final[w] dist[w] min){k w;min dist[w]; // w顶点离v0顶点更近}}final[k] 1; // 将目前找到的最近的顶点置为1for (w 0; w G.vexNum; w) // 修正当前最短路径及距离{/* 如果经过v顶点的路径比现在这条路径的长度短的话 */if (!final[w] (min G.Edge[k][w] dist[w])){dist[w] min G.Edge[k][w]; // 修改当前路径长度path[w] k;}}} 【3】 重复【2】 【3】重复【2】 【4】重复【2】 到这里dist[i]里面存的就是从V0到 Vi 的最短路径长度而通过path[i] 就能找到最短路径。
这里V1至始至终都没有更新的原因是V0根本走不到V1。
看完上述图解那么书上P190那个表格你肯定就明了
下图的S相当于 final[i] 这个表格建议大家要搞懂可能有些学校会考察画图哦
⚠️注意
迪杰斯特拉算法适用于求正权有向图中源点到其余各个节点的最短路径。图中可以有环但不能有负权边。
例如如下图就不能使用迪杰斯特拉算法求节点 1 到其余各个节点的最短距离。 因为根据迪杰斯特拉算法首先会更新dist[2] 1 , final[2] 1。由于final[2]被确定为1即之后将不会再更新dist[2]而根据上图显然结点1到结点2的最短路径为-1。 显然Dijkstra 算法也是基于贪心策略的。使用邻接矩阵或者带权的邻接表表示时时间复杂度都是 人们可能只希望找到从源点到某个特定顶点的最短路径但这个问题和求解源点到其他所有顶点的最短路径一样复杂时间复杂度也为 5.3 Floyd算法
Floyd算法适用于APSP(多源最短路径)是一种动态规划算法稠密图效果最佳边权可正可负但是不能解决带有“负权回路”的图。此算法简单有效由于三重循环结构紧凑对于稠密图效率要高于执行|V|次Dijkstra算法
优点容易理解可以算出任意两个节点之间的最短距离代码编写简单。缺点时间复杂度比较高不适合计算大量数据
真正的算法实现无外乎就是三个循环嵌套ij 的循环是任意两个点而 k 则是两个点之间所经过的第三个点中转点我们就是在循环之中不断比较【从i 到 j 的距离】与 【从i 到 k 距离 加上从k 到 j距离】的大小如果经过这个中转点路径变短了我们就接受这个点认为可以经过这个点否则就不经过这个点就是从 i 到 j 最短。 ⚠️注意A数组初始化时一定要将A[0][0] 0 A[1][1] 0 .... A[4][4] 0。 //......准备工作根据图的信息初始化矩阵 A 和 path (如上图)
for (int k 0 ; k G.vexNum ; k) //必须把所有顶点为中转点都试一遍
{for (int i 0 ; i G.vexNum ; i) //遍历整个矩阵i为行号j为列号 {for (int j 0 ; j G.vexNum ; j){if (A[i][j] A[i][k] A[k][j]) //已 K为中转点的路径更短 {A[i][j] A[i][k] A[k][j]; //更新最短路径长度 path[i][j] k; //记录i到 j的中转点 }}}
} 经过上述代码过程后最终的A数组和path数组就为 那么任一两个顶点 i 和 j 的最短路径长度就为A[i][j]
而要求最短路径就要通过path数组不断递归中转划分。
比如求V0 到 V4的最短路径为 因为path[0][4] 3 所以V0到V4会经过V3 而A[0][3] 2 说明V0到V3会经过V2。 而A[3][4] -1说明V3直接连接V4。 而A[0][2] -1说明V0直接连接V2。 而A[2][3] 1 说明V2到V3会经过V1。 而A[2][1] -1说明V2直接连接V1。 而A[1][3] -1说明V1直接连接V3。 所以综上V0 - V2 - V1 - V3 - V4 开头说了“但是不能解决带有“负权回路”的图”
意思就是不能解决 “有负权值的边组成回路” 。因为这样可能没有最短路径比如下图 5.4 总结 六、有向无环图及其应用
有向无环图无环的有向图 简称 DAG (Directed Acycline Graph) 图。 6.1 DAG描述表达式
当描述含有公共子式的表达式可以根据有向无环图的特点实现对相同子式的共享从而节省存储空间。
例如描述如下子式 显然上述有向无环图可以合并一部分子式不用管为什么那么存储你想怎么存储就怎么存储前提是有向无环图 咸鱼学长分析法
这个方法简单高效明了 为了说明这个方法还是以上面那道题为基础讲解
Step1:主要是为了后面合并表达式方便 Step2:这个编号顺序可以随意但为了最后的图形可观一点可以采用中缀表达式转后缀表达式的运算符的生效顺序编号 Step3 为了最后方便合并层次要分明比如4号运算符要在1、3、2的上面一层其他同理 Step4: (逐层合并) 【练习】 按那4个步骤来 由图可知需要的顶点个数至少为5个选择A 6.2 拓扑排序
AOV网用一个有向图表示一个工程的各子工程及其相互制约的关系。
其中以顶点表示活动弧 表示活动之间的优先制约关系称这种有向图为顶点表示活动的网简称AOV (Activity On Vertex network)网。
⚠️注意AOV网是有向无环。
拓扑排序定义
在 AOV 网没有回路的前提下我们将全部活动排列成一个线性序列使得若 AOV 网中有
弧 i, j 存在则在这个序列中 i 一定排在 j 的前面具有这种性质的线性序列称为拓扑有序
序列相应的拓扑有序排序的算法称为拓扑排序。
检测 AOV 网中是否存在环方法 对有向图构造其顶点的拓扑有序序列若网中所有顶点都在它的拓扑有序序列中则该 AOV 网必定不存在环。
拓扑排序的方法 在有向图中选一个没有前驱的顶点且输出之。 从图中删除该顶点和所有以它为尾的弧。 重复上述两步直至 全部顶点均已输出 或者 当图中不存在无前驱的顶点为止。
【1】如果全部顶点均已输出说明无环即拓扑有序序列
当然每个AOV网都有一个或多个拓扑有序 你可以先买菜再准备厨具即交换1和2的顺序或者3和5交换顺序等 【2】如果当图中不存在无前驱的顶点为止时即顶点没有全部输出说明原图存在回路即有环 算法代码分析 要点
存放当前顶点入度的数组 indegree[ ]记录拓扑序列的数组 print[ ]保存度为 0 的顶点的栈也可以用队列 indegree[ ]数组是你事先计算好的计算顶点度的函数在邻接表那一章已经讲了。
⚠️注意此图是采用邻接表存储的因为如果你选择邻接矩阵存储因为要遍历每个顶点及其边而邻接矩阵是 |v| * |v|所以整个算法的时间复杂度为
采用邻接表存储的算法的时间复杂度为如果是稀疏图性能上比邻接矩阵好。
下面的动图反映了程序在执行时indegree[ ]数组里存储的各顶点入度的变化 // 对图G进行拓扑排序
bool TopologicalSort(Graph G){InitStack(S); //初始化栈存储入度为0的顶点for(int i0;ig.vexnum;i){if(indegree[i]0)Push(S,i); //将所有入度为0的顶点进栈}int count0; //计数记录当前已经输出的顶点数while(!IsEmpty(S)){ //栈不空则存入Pop(S,i); //栈顶元素出栈print[count]i; //输出顶点i最后把print数组里面存的拓扑排序序列输出for(pG.vertices[i].firstarc;p;pp-nextarc){//将所有i指向的顶点的入度减1并将入度为0的顶点压入栈vp-adjvex;if(!(--indegree[v]))Push(S,v); //入度为0则入栈}}if(countG.vexnum)return false; //排序失败elsereturn true; //排序成功
}逆拓扑排序
从出度为0开始.........
基本思路不变存储结构改为逆邻接表。其他算法代码不变 逆拓扑排序的DFS算法
在顶点退栈前输出 如下图DFS遍历这个图时递归栈的变化 上述DFS遍历对应的算法代码 void DFS(Graph G , int v ) { //从顶点v出发DFS遍历 visited[v] true; // 设置已访问标志for (int w FirstNeighbor(G, v); w 0; w NextNeighbor(G, v, w)) {if (!visited[w]) {DFS(G , w); }}printf(%d , G.vex[v]); //输出顶点v
}void DFSTraverse(Graph G , int v)
{for (int v 0 ; v G.vexnum ; v){visited[v] false;}for (int v 0 ; v G.vexnum ; v){if (!visited[v]){DFS(G,v);}}
} 如果图中存在环的话就不能生成拓扑排序序列因此需要处理环的问题。
做法很简单可以格外再用一个isDescendant[ ]数组记录该结点是否被其子孙指向也就是是否有其子孙到该结点的弧。有的话必定存在环 bool visited[MAXVERTEXNUM];
bool isdescendant[MAXVERTEXNUM];void DFS(Graph G, int v) {visited[v] true;//记录全局访问情况isdescendant[v] true;//记录本轮访问情况for (int w FirstNeighbor(G, v); w 0; w NextNeighor(G, v, w)) {//依次递归访问v的邻接节点if (isdescendant[w] true) { //如果本轮存在其子孙到该结点w的弧说明存在回路直接退出程序 printf(\n出现回路) ;exit(0);}if (visited[w] false) {//没被访问就继续递归沿着该点路径继续延长DFS(G, w);}}//forprintf(%d , G.vex[v]);isdescendant[v] false;//本轮结束消去本轮对应的访问记录。(必须消去)
}void DFSTraverse(Graph G) {for (int v 0; v G.vexnum; v) {//初始化数组visited[v] false;isdescendant[v] false;}for (int v 0; v G.vexnum; v)//防止出现遗漏if (visited[v]false)DFS(G, v);
} 有些同学可能会有疑问为啥要多开一个数组isDescendant[ ] 直接在DFS的for循环里的if判断加一个visited[w] true就能判断有环
这很片面就拿上面这个图来说遍历了4 3 1 0后它们对应的visited[ ]数组都被标记成了true。
当从2开始进行第二次DFS时通过DFS的for循环遍历2的邻接点3和4发现visited[3] 为true就判定为环这显然与图不符合 6.3 关键路径
把工程计划表示为有向图用顶点表示事件弧表示活动弧的权表示活动持续时间。每个事件表示在它之前的活动已经完成在它之后的活动可以开始。称这种有向图为边表示活动的网简称为 AOE (Activity On Edge) 网。
边上的权值表示完成该活动的开销如完成活动所需要的时间。
对AOE网我们关心两个问题 完成整项工程至少需要多少时间 哪些活动是影响工程进度的关键
在AOE网中仅有一个入度为0的顶点称为开始顶点(源点)它表示整个工程的开始网中也仅存在一个出度为0的顶点称为结束顶点(汇点)它表示整个工程的结束。
我们把路径上各个活动所持续的时间之和称为路径长度从源点到汇点具有最大长度的路径叫关键路径在关键路径上的活动叫关键活动。
完成整个工程的最短时间就是关键路径的长度即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间即若关键活动不能按时完成则整个工程的完成时间就会延长。因此只要找到了关键活动就找到了关键路径也就可以得出最短完成时间。 要求得一个AOE网的关键活动必须熟悉如下几个重要参数 ve(k) — 表示事件 Vk 的最早发生时间。 e(i) — 表示活动 ai 的最早开始时间。
如下图黄色标注的数据就是事件Vk 的最早发生时间。而通过ve(k)就能间接得到活动ai的最早开始时间e(i)如红色标注的数据。 vl(k) — 表示事件 Vk 的最迟发生时间。
l(i) — 表示活动 ai 的最迟开始时间。
如下图紫色标注的数据就是事件Vl 的最迟发生时间。而通过vl(k)就能间接得到活动ai的最迟开始时间l(i)如绿色标注的数据。 而通过这四个参数的数据就能求得关键活动
l(i) - e(i) — 表示完成活动 ai 的时间余量。
关键活动 — 关键路径上的活动即 l(i) e(i) 的活动。
如下图关键活动为a2 、a3、a4。关键路径为V1 - V2 - V3 - V4 【例子】详细解题步骤5步骤 在开始前先确定该AOE网的拓扑排序序列按照这个顺序有条理的列出ve()、vl()、e()、l()。
上图的一个拓扑排序序列为V1、V3、V2、V5、V4、V6
【1】基本没啥难点但要注意如果有像事件V4和V6这种存在多条入度的活动需要求最大值因为要保证之前的所有活动都能完成
【2】需要按照逆拓扑序列从结束顶点开始求vl()。这里注意存在多条出度的活动需要求最小值因为只有保证了多个活动中最小的值开始才能保证那些较大值的开始
【3】通过【1】求得的ve(i)间接得到e(i)按照拓扑排序序列对于每个活动的最早发生时间就是弧尾连接的那个事件ve()比如下图e(a3) ve(v2) 3 ;e(a5) ve(v3) 2
【4】通过【2】求得的vl(i)间接得到l(i)按照逆拓扑排序序列对于每个活动的最迟发生时间就是弧头连接的那个事件vl()减去这个活动 ai的权值就为 l(i)比如下图l(a3) vl(v4) - a3 4
【5】将求得的e(i) 和 l(i)相减求得时间余量d(i)d(i)等于0的活动 ai就为关键活动。那么关键路径即为经过这些关键活动的路径。如下图标注红线的路线 关键活动和关键路径的注意点 对于关键活动需要注意以下几点: 若关键活动耗时增加则整个工程的工期将增长缩短关键活动的时间可以缩短整个工程的工期当缩短到一定程度时关键活动可能变成非关键活动 对于关键路径需要注意以下几点 网中的关键路径并不唯一且对于有几条关键路径的网只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。 结尾
最后非常感谢大家的阅读。我接下来还会更新 查找 如果本文有错误或者不足的地方请在评论区(或者私信)留言一定尽量满足大家如果对大家有帮助还望三连一下啦
我的个人博客欢迎访问 !
