深圳市手机网站建设,新东方研学网站那家公司做的,wordpress交流插件,网络运营商无服务六、图 目录 六、图定义及基本术语图的定义有向图以及无向图简单图以及多重图度顶点-顶点间关系连通图、强连通图子图连通分量强连通分量生成树生成森林边的权、带权网/图特殊形态的图 图的存储及基本操作邻接矩阵邻接表法十字链表邻接多重表分析对比图的基本操作 图的遍历广度…六、图 目录 六、图定义及基本术语图的定义有向图以及无向图简单图以及多重图度顶点-顶点间关系连通图、强连通图子图连通分量强连通分量生成树生成森林边的权、带权网/图特殊形态的图 图的存储及基本操作邻接矩阵邻接表法十字链表邻接多重表分析对比图的基本操作 图的遍历广度优先遍历(BFS)深度优先遍历(DFS) 图的应用最小生成树最短路径BFS最短路径Dijkstra最短路径Floyd算法有向无环图拓扑排序关键路径 定义及基本术语
图的定义 有向图以及无向图 简单图以及多重图 度 顶点-顶点间关系 连通图、强连通图 子图 有向图也一样
连通分量 强连通分量 生成树 生成森林 边的权、带权网/图 特殊形态的图 总结 图的存储及基本操作
邻接矩阵
#define MaxVertexNum 100//顶点数目的最大值
typedef struct
{char Vex[MaxVertexNum];//顶点表 可存更复杂的信息int Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵边表可以用bool型或枚举型变量表示边int vexnum, arcnum;//图的当前顶点数和边数/弧数
}MGraph;存储带权图网 对角线处可以填0或∞
空间复杂度为O|V|2只和顶点数相关和实际的边数无关适合用于存储稠密图
对于无向图邻接矩阵是对称矩阵可以进行对称矩阵的存储压缩存入一维数组中只存储上三角区/下三角区
性质 邻接表法
邻接矩阵是用数组实现的顺序存储空间复杂度高不适合存储稀疏图
而邻接表法使用顺序链式存储的方式表示方式并不唯一与树的孩子表示法相似
//邻接表
typedef char VertexType;//顶点的数据类型
//“边/弧”
typedef struct ArcNode
{int adjvex;//边/弧指向哪个节点struct ArcNode* next;//指向下一条弧的指针//InfoType info;//权值
}ArcNode;
//“顶点”
typedef struct VNode
{VertexType data;//顶点信息ArcNode* first;//第一条边/弧
}VNode,AdjList[MaxVertexNum];
//用邻接表存储的图
typedef struct
{AdjList vertices;int vexnum, arcnum;
}ALGraph;与邻接矩阵对比 十字链表
用邻接矩阵以及邻接表存储有向图时都有所缺陷 使用十字链表存储有向图不能用于无向图 空间复杂度为:O(|V||E|)
顺着绿色路线能找到顶点所有的出边
顺着橙色路线能找到顶点所有的入边
邻接多重表
用邻接矩阵以及邻接表存储无向图时都有所缺陷 用邻接多重表存储无向图不能用于有向图 空间复杂度O(|V||E|)
删除边、删除节点等操作很方便
分析对比 图的基本操作
主要基于图的邻接矩阵以及邻接表 **Adjacent(G,x,y)**判断图G是否存在边x, y或(x, y)。
邻接矩阵O(1) 邻接表O(1)~O(|V|)
**Neighbors(G,x)**列出图G中与结点x邻接的边。
邻接矩阵O(|V|) 邻接表出边O(1)~O(|V|) 入边O(|E|)
**InsertVertex(G,x)**在图G中插入顶点x
邻接矩阵O(1) 邻接表O(1)
**DeleteVertex(G,x)**从图G中删除节点x
邻接矩阵O(|V|) 邻接表出边O(1)~O(|V|) 入边O(|E|)
**AddEdge(G,x,y)**若无向边(x, y)或有向边x, y不存在则向图G中添加该边。
邻接矩阵O(1) 邻接表O(1)
**RemoveEdge(G,x,y)**若无向边(x, y)或有向边x, y存在则从图G中删除该边。
邻接矩阵O(1) 邻接表O(1)~O(|V|)
**FirstNeighbor(G,x)**求图G中顶点x的第一个邻接点若有则返回顶点号。若x没有邻接点或图中不存在x则返回-1。
邻接矩阵O(1)~O(|V|) 邻接表出边O(1) 入边O(1)~O(|E|)
**NextNeighbor(G,x,y)**假设图G中顶点y是顶点x的一个邻接点返回除y之外顶点x的下一个邻接点的顶点号若y是x的最后一个邻接点则返回-1。
邻接矩阵O(1)~O(|V|) 邻接表O(1)
图的遍历
广度优先遍历(BFS)
实现思路 #define MAX_VERTEX_NUM 100//顶点数目的最大值bool visited[MAX_VERTEX_NUM];//访问标记数组
void BFSTraverse(Graph G) //对图G进行广度优先遍历
{for (int i 0; i G.vexnum; i)visited[i] false;//访问标记数组初始化InitQueue(Q);//初始化辅助队列Qfor (int i 0; i G.vexnum; i)//从0号顶点开始遍历{if (!visited[i])//对每个连通分量调用一次BFSBFS(G, i);//vi未访问过从vi开始BFS}
}//广度优先遍历
void BFS(Graph G, int v) //从顶点v出发广度优先遍历图G
{visit(v);//访问初始顶点vvisited[v] true;//对v做已访问标记Enqueue(Q, v);//顶点v入队列Qwhile (!isEmpty(Q)){DeQueue(Q, v);//顶点v处队列for (w FirstNeighbor(G, v); w 0; w NextNeighbor(G, v, w)){//检测v所有邻接点if (!visited[w])//w为v的尚未访问的邻接顶点{visit(w);//访问顶点wvisited[w] true;//对w做已访问标记EnQueue(Q, w);//顶点w入队列}}}
}遍历序列是具有可变性的 对于无向图调用BFS函数的次数连通分量数
复杂度分析 广度优先生成树若是非连通图则得到广度优先生成森林 利用广度优先生成的树高度是最小的因为按最短路径
应用解决非带权图的单源最短路径问题
//解决非带权图的单源最短路径问题
void BFS_MIN_Distance(Graph G, int u)
{//d[i]表示从u到i结点的最短路径for (int i 0; i G.vexnum; i){d[i] 0x3f3f3f3f;//无穷大初始化路径长度}visited[u] true;d[u] 0;EnQueue(Q, u);while (!isEmpty(Q))//BFS算法主过程{DeQueue(Q, u);//队头元素u出队for (w FirstNeighbor(G, u); w 0; w NextNeighbor(G, u, w)){if (!visited[w])//w为u的尚未访问的邻接顶点{visited[w] true;//设已访问标记d[w] d[u] 1;//路径长度加1EnQueue(Q, w);//顶点w入队}}}
}深度优先遍历(DFS)
类似于树的先根遍历使用函数调用栈递归实现
#define MAX_VERTEX_NUM 100//顶点数目的最大值bool visited[MAX_VERTEX_NUM];//访问标记数组void DFSTraverse(Graph G)//深度优先遍历图G
{for (v 0; v G.vexnum; v)visited[v] false;//初始化已访问标记数据for (v 0; v G.vexnum; v)//从v0开始遍历if (!visited[v])DFS(G, v);
}void DFS(Graph G, int v)//从顶点v触发深度优先遍历图G
{visit(v);//访问顶点vvisited[v] true;//设已访问标记for (w FirstNeighbor(G, v); w 0; w NextNeighbor(G, v, w)){if (!visited[w]){DFS(G, w); // w为v的尚未访问的邻接顶点}}
}复杂度分析 遍历序列不唯一性 深度优先生成树非连通生成森林 对于无向图进行BFS/DFS遍历调用BFS/DFS次数连通分量数对于连通图只调用一次
对于有向图进行BFS/DFS遍历调用BFS/DFS次数要具体问题具体分析若起始顶点到其他各顶点都有路径只调用一次对于强连通图从任一结点出发都只需调用一次BFS/DFS
图的应用
最小生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n则它的生成树含有n-1条边对生成树而言若砍去它的一条边则会变成非连通图若加上一条边则会形成一个回路。
广度优先生成树的高度是小于等于深度优先生成树的高度的。
最小生成树定义 两种求最小生成树的方法
Kruskal: Prim: 最短路径BFS
最短路径问题描述 利用BFS算法可以求无权图的单源最短路径无权图可以视作一种特殊的带权图只是每条边的权值都为1故各边权值相等时可以使用BFS算法求解
代码实现
//解决非带权图的单源最短路径问题
void BFS_MIN_Distance(Graph G, int u)
{//d[i]表示从u到i结点的最短路径for (int i 0; i G.vexnum; i){d[i] 0x3f3f3f3f;//无穷大初始化路径长度path[i]-1;//记录最短路径从哪个顶点过来}visited[u] true;d[u] 0;EnQueue(Q, u);while (!isEmpty(Q))//BFS算法主过程{DeQueue(Q, u);//队头元素u出队for (w FirstNeighbor(G, u); w 0; w NextNeighbor(G, u, w)){if (!visited[w])//w为u的尚未访问的邻接顶点{visited[w] true;//设已访问标记d[w] d[u] 1;//路径长度加1path[w]u;//最短路径应从u到wEnQueue(Q, w);//顶点w入队}}}
}时间复杂度邻接矩阵O(|V|2) 邻接表O(|V||E|)
最短路径Dijkstra
dist[ ]记录从源点v0到其他各顶点当前的最短路径长度它的初态为若从v0到vi有弧则dist[i]为弧上的权值否则置于∞
path[ ]表示从源点到顶点i之间的最短路径的前驱结点。在算法结束时可根据其值追溯得到源点v0到顶点vi的最短路径。 不适用于有负权值的带权图
用邻接矩阵以及邻接表时间复杂度都为O(|V|2)
最短路径Floyd算法
算法思路 最终实现 对于更多结点若要找到完整路径需要通过path矩阵递归寻找 Floyd算法可以用于负权图但不能解决带有“负权回路”的图有负权值的边组成回路这种图有可能没有最短路径
不同算法对比 有向无环图
若一个有向图中不存在环则称为有向无环图简称DAG图
有向无环图是描述含有公共子式的表达式的有效工具
其表示表达式中顶点中不可能出现重复的操作数
步骤 表示出来的结果可能不唯一
拓扑排序
AOV网用DAG图表示一个工程顶点表示活动有向边Vi,Vj表示活动Vi必须先于活动Vj进行不能存在环路
拓扑排序 实现代码
#define MaxVertexNum 100//图中顶点数目的最大值//定义邻接表
typedef char VertexType;//顶点的数据类型
//“边/弧”
typedef struct ArcNode
{int adjvex;//边/弧指向哪个节点struct ArcNode* nextarc;//指向下一条弧的指针//InfoType info;//权值
}ArcNode;
//“顶点”
typedef struct VNode
{VertexType data;//顶点信息ArcNode* firstarc;//第一条边/弧
}VNode, AdjList[MaxVertexNum];
//用邻接表存储的图
typedef struct
{AdjList vertices;int vexnum, arcnum;
}ALGraph;//拓扑排序
bool TopologicalSort(Graph G)
{InitStack(S);//初始化栈存储入度为0的结点for (int i 0; i G.vexnum; i){if (indegree[i] 0){Push(S, i);//将所有入度为0的顶点进栈}}int count 0;//计数记录当前已经输出的顶点数while (!IsEmpty(S))//栈不空则存在入度为0的顶点{Pop(S, i);//栈顶元素出栈print(count) i;//输出顶点ifor (p G.vertices[i].firstarc; p; p p-nextarc){//将所有i指向的顶点的入度减1并且将入度为0的顶点压入栈Sv p-adjvex;if (!(--indegree[v]))//若为0{Push(S, v);//入栈}}}if (count G.vexnum){return false;//排序失败有向图中有回路}elsereturn true;//拓扑排序成功
}时间复杂度邻接表O(|V||E|) 若采用邻接矩阵 O(|V|2)
逆拓扑排序 也可以用DFS算法实现
//逆拓扑排序
void DFSTraverse(Graph G)//深度优先遍历图G
{for (v 0; v G.vexnum; v)visited[v] false;//初始化已访问标记数据for (v 0; v G.vexnum; v)//从v0开始遍历if (!visited[v])DFS(G, v);
}void DFS(Graph G, int v)//从顶点v触发深度优先遍历图G
{visit(v);//访问顶点vvisited[v] true;//设已访问标记for (w FirstNeighbor(G, v); w 0; w NextNeighbor(G, v, w)){if (!visited[w]){DFS(G, w); // w为v的尚未访问的邻接顶点}}print(v);//输出顶点
}关键路径
在带权有向图中以顶点表示事件以有向边表示活动以边上的权值表示完成该活动的开销(如完成活动所需的时间)称之为用边表示活动的网络简称AOE网。
性质 AOE网中仅有一个入度为0的顶点称为开始顶点源点也仅有一个出度为0的顶点称为结束顶点汇点
从源点到汇点的有向路径可能有多条所有路径中具有最大路径长度的路径称为关键路径而把关键路径上的活动称为关键活动
完成整个工作的最短时间就是关键路径的长度若关键活动 不能按时安成为则整个工程的完成时间就会延长。
几个概念 求关键路径的步骤 求事件的最早发生时间 求事件的最迟发生时间 求活动的最早发生时间 求活动的最迟发生时间 求活动的时间余量 最终得出关键路径 特性
若关键活动耗时增加则整个工程的工期将增长缩短关键活动的时间可以缩短整个工程的工期当缩短到一定程度时关键活动可能会变成非关键活动。
可能有多条关键路径只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
思路总结 主要参考王道考研课程 后续会持续更新考研408部分的学习笔记欢迎关注。 github仓库含所有相关源码408数据结构笔记
