图

逻辑结构

遍历

dfs

栈/递归
①从图中某个顶点V0出发②找出刚访问的顶点的第一个邻接点，访问它并将他置位当前节点③重复步骤2直至当前节点不再有邻接点④返回上一个仍有邻接点并未被访问过的节点，重复步骤

bfs

队列
依次访问当前节点的每一个邻接点

存储结构

邻接矩阵

定义

设矩阵A，对于任意的Vi与Vj，若∈VR，则Aij＝1，反之为0

实现

有权图的邻接矩阵初值赋为∞，无权图初值为0.

再通过循环存入每一条弧。

复杂度

时间复杂度
存弧的时间复杂度为O(e)，赋初值的时间复杂度为O(n²)
空间复杂度
空间复杂度为O(n²)

特性

便于运算
因为使用矩阵存储，所以可以便捷地访问每一条弧。显然，判断弧存在、求顶点的度都可以在短时间内较优地完成
无向图的对角矩阵优化
对于稀疏图存在大量空间浪费

邻接表

定义

对图中所有的顶点建立一个带头节点的边链表，第i个边链表表示依附于Vi的边(弧)，而每个边链表的头又构成一个表头节点表。
表头节点表
  • 由数据域与链域构成。
    • 数据域存储节点名及其他相关信息。
    • 链域指向第一个节点边表
  • 由n个表示邻接关系的边链表组成。这些边链表中的每个节点由邻接点域、链域及数据域组成。
    • 邻接点域存放与当前顶点Vi相邻接的顶点在图中的位置
    • 链域用于指向下一个相关联的节点
    • 数据域用于存储节点相关信息实现定义ArcNode类，其成员为指向下一条边(弧)的指针*nextarc、存储信息的变量info和存储位置的变量adj定义VertexNode类，其成员为存储信息的变量data与指向第一个节点的指针*firstarc定义AdjList类，其成员为记录图顶点数的变量vexnum、记录图边(弧)数的变量arcnum与VertexNode数组vertex复杂度空间复杂度为O (n+2e)特性空间优化采用动态存储，故对于稀疏图与稠密图，都能在较优的情况下完成存储任务并且可以使用十字链表等方式进一步优化空间计算复杂链表无法直接对某个元素进行访问。故邻接表无法在常数时间内判断某两点间是否存在边(弧)。同样地，求入度则需要遍历整个邻接表，求出度更是需要借助逆邻接表应用最小生成树生成树定义简而言之，能联通所有顶点且不产生回路的所有子图都是母图的生成树最小生成树定义显然，每个有权连通图的所有生成树其权都不尽相同。我们定义权值最小的那些生成树为最小生成树求解Prim算法存储结构
  • 通常为邻接矩阵算法思想
  • Prim是一种采用贪心思想的算法。构造一个节点集合U，它是节点全集V的子集。初始状态下U中仅有起始节点V0。每次操作时从U和V－U中找到能组成当前最短边的(V, U)，将V加入到集合U中。重复上述操作直到所有节点都在U中，此时U中所有元素和即是最小生成树权。复杂度
  • 时间复杂度为O(nm＋m)
    • 可以使用堆优化至O(mlogn)，但空间复杂度与代码复杂度较高
  • 空间复杂度为O(n)kruskal算法算法思想
  • 类似于哈夫曼树的求解。初始状态下构造一个n个节点但边集为空的子图，将此状态下每个节点视为一个根，这这n棵树构成一个森林。每一步从原图边集中找出最小边，若构成边的两个顶点分属不同树则合并这两棵树，反之不做操作。重复操作至森林中仅剩一棵树，这棵树就是最小生成树算法实现
  • ①新建边集为空的子图G0②将原图中所有边以权为关键字升序排序③从边集中第一条边开始，若构成这条边的两个接节点不在一个联通分量中则将这条边置入G0④重复步骤3至所有节点都在一个联通分量中。复杂度分析
  • 时间复杂度为O(n²)
    • 可用并查集优化至O(mlogm)
  • 空间复杂度为O(n)适用范围稠密图
  • Prim稀疏图
  • Kruskal堆优化的prim在上树情况中都有不错的性能，但他存在较高的空间及代码复杂度。最短路问题Dijkstra算法算法思想贪心策略。每一步去找vi到起始点的最短路径，若找到则将vi加入U中。算法实现dis[i]记录起始点到每个点的最短路径，s存储已经遍历过的节点。复杂度时间复杂度为O(n²)
  • 可用堆优化至O(nlogn)空间复杂度为O(n)适用范围非负权图Floyd算法算法思想枚举算法实现a[i][j]表示从i到j的最短路径，利用媒介节点k来枚举所有可能的情况。三重循环分别去枚举ijk。复杂度时间复杂度为O(n³)空间复杂度为O(n²)适用范围任意图topo排序定义一个有向无环图所有顶点的线性序列，该序列满足：①每个顶点出现且仅出现一次②若存在一条从A到B的坎路径，则A一定在B前面通常，一个DAG图存在一个或多个拓扑排序实现①从DAG 图中找到一个入度为0的节点并输出②从图中删除该点以及所有以它为起点的边③重复步骤1与步骤2至DAG图为空或不存在入度为0的点。而后者说明该图存在环。时间复杂度为O(v＋e)应用若完成任务A的先决条件是完成任务B，则这个任务中存在前置关系。拓扑排序可以确定存在前置关系的条件下整个任务的完成流程