图状结构思维导图

基本概念

结构体定义

基本概念

创建无向网

空间效率：无向图的邻接矩阵对称，可以压缩存储空间；有n个顶点的无向图需要n(n-1)/2。有n个顶点的有向图所需要的存储空间为n^2；用于稀疏图空间浪费较多

容易实现图的操作（如：求某顶点的度、判断顶点之间是都右边、找顶点的邻接点）

图示表示

邻接表不唯一，因为各个表结点的链入顺序是任意的 空间效率为O(n+2e)，适合存储稀疏图 TD(Vi)=单链表中链接的结点数

图示表示

空间效率：O(n+e) 出度：OD(Vi)=表中Vi链接单链表中的结点数 入度：ID(Vi)=表中节点邻接点域为Vi的弧的个数 度：TD(Vi)=OD(Vi)+ID(Vi)

若<v,w>∈VR，则<v,w>表示从v到w的一条弧，且称弧v为弧尾，称w为弧头，此时的图为有向图

若<v,w>∈VR必有<w,v>∈VR，则以无序对（v，w）代表这两个有序对，表示v，w之间有一条边，此时的图为无向图

含有很少条边或者弧的图

含有很多条边或弧的接近完全图的图

与图的边或弧相关的数，这些数可以表示从一个顶点到另一个顶点的距离或耗费

带权的图

如果图G=(V,E)和G’=(V’, E’)，满足：V’ ⊆ V且E’ ⊆ E，则称G’是G的子图

无向图：若（v，v’）是一条边则称顶点v和v’互为邻接点，称边（v，v’）与v和v’相关联

有向图：若<v，v’>是一条弧，则称顶点v邻接到v’，顶点v’邻接自顶点v，弧<v，v’>与顶点v和v’相关联

无向图中顶点v的度是和v相关联的边的数目，记作TD（v）

入度：有向图以顶点v为头的弧的数目称为v的入度，记作ID（v）

出度：有向图以顶点v为尾的弧的数目称为v的出度，记作OD（v）

定义

路径长度

回路

简单路径

简单回路

无向图中，从顶点v到v'之间有路径则称从v到v'是连通的

连通图：无向图中任意两个顶点都是连通的

连通分量：无向图的极大连通子图

包含无向图G中的所有顶点的极小连通子图

生成树的特点

如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树

有向图的生成森林：由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧

沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

为了求得问题的解，先选择某一种可能情况向前探索；

在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索；

如此反复进行，直至得到解或证明无解

仿照树的层序遍历，查找遍历完整张图

在访问起止点之后，依次访问v的邻接点

然后再依次访问这些顶点中未被访问的

直到所有顶点都被访问过为止

采用队列的方式 1. 把根结点放到队列的末尾 2. 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素标记为它下一级元素的前驱 3. 找到所要找的元素时结束程序 4. 如果遍历整个树都还没有找到，则结束程序

Prim算法通过一系列不断扩张的子树来构造一棵最小生成树。

从图的顶点集合中任意选择的一个单项点，作为序列中的初始子树。

每一次迭代时，以一种贪心的思想来扩张当前的生成树，即把不在树的最近顶点添加到树中

当图的所有顶点都包含在所构造的树中以后，该算法就停止了。

算法优化：我们可以定义一个优先队列，队列中元素记录了节点的编号和节点和树中的顶点相连的边权，将源点压入队列。当队列非空，执行以下操作： 1.u等于队顶的节点，w等于队顶节点的最短边权。 2.遍历u的所有边，如果能找到节点v小于v的当前值，更新v，将v压入队列。

Kruskal算法按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路

使用并查集，并将加权图每个顶点都看做森林，然后将图中每条邻接边的边权按照升序的方式进行排列

从排列好的邻接边表中抽取边权最小的边，写入该边的起始顶点和结束顶点，连接顶点将森林构成树

然后读取起始结束顶点的邻接边，优先抽取边权小的邻接边，继续连接顶点将森林构成树。

添加邻接边的要求是加入到图中的邻接边不构成回路（环）。如此反复进行，直到已经添加n-1条边为止。

归并顶点，算法的时间复杂度为O（n^2），与e无关

适用于稠密网

归并边，算法的时间复杂度为O（eloge），与e有关

适用于稀疏网

若从i到j有一条有向路径，则i是j的前驱；j是i的后继。

AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谡的。

在AOV网络中选一个没有直接前驱的顶点，并输出之；

从图中删去该顶点，同时删去所有它发出的有向边;

重复以上2、3步，直到： 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；若图中还有未输出的顶点，但已跳出处理福环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。

在有向图中选一个无前趋的顶点v，输出之；

从有向图中删除v及以v为尾的弧；

重复1、2，直接全部输出全部頂点或有向圏中不存在无前超的結点吋力止

AOV网侧重于表示活动的前后次序。

AOE网除了 表示活动的先后次序外，还表示了活动的持续时间，因此可利用AOE网解决工程所需最短时间及哪些子工程拖延会影响整个工程按时完成等问题。

实际应用中采用那一种图，取決于要求解的问题。

图中的最长路径

因此可以设置数组e(earliest)和数组l(latest)，其中e[r]和l[r]分别表示活动ar的最早开始时间和最迟开始时间。于是，当求出这两个数组之后，就可以通过判断e[r] == l[r]是否成立来确定活动r是否是关键活动。

设置两点顶点的集合 U和 T ，集合 U中存放已找到最短路径的顶点，集合 T中存放当前还未找到的最短路径的顶点。

初始状态时，集合 U中只包含源点，设为 v0

然后从集合工中选择到源点v0路径长度最短的顶点u加入到集合U中。

集合U 中每加入一个新的顶点u都要修改源点vo带集合工 中剩余顶点的当前最短路径值，集合工中各顶点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过顶点山到达该顶点的带权路径长度中的较小者。

回到3，此过程不断重复，直到集合工中的顶点全部加入到集合U中为止。

初始化矩阵，将所有相邻的节点对应的权值写入矩阵，不相邻的节点对应的权值初始化为inf

初始化结束后，开始进行三重循环，每层循环从第一个节点开始遍历，直至遍历到第n个节点，设最外层循环当前节点为i，中间层循环的当前节点为j，内层循环的当前节点为k，且i≠j≠k。则以节点i为中介点，以节点j为起点，节点k为目标点，判断由起点j经由中介点i到达目标点k的代价值是否小于由起点j直接到目标点k的代价值，若小于，则将从起点j到目标点k的代价值d[j][k]更新为d[j][i]+d[i][k]。三重循环结束后，路径规划结束。

路径规划结束后，图的邻接矩阵D也就更新完成了，如果从Vi到Vj有路可达，则D[i][j]=d，d表示该路的长度；否则D[i][j]=无穷大。定义一个矩阵P用来记录所插入点的信息，P[i][j]表示从Vi到Vj需要经过的点，初始化P[i][j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，D[i][j] = min( D[i][j], D[i][k]+D[k][j] )，如果D[i][j]的值变小，则P[i][j]=k。在D中包含有两点之间最短道路的信息，而在P中则包含了最短通路径的信息。