图是比树更一般的结构，由节点和边组成。根据边是否有方向分为有向图和无向图。同时在每个边上可以加入权重，代表从一个顶点到另一个顶点的代价。
圈(Cycle):首尾顶点相同的路径。
图的抽象数据类型
图的抽象数据类型主要通过邻接矩阵或邻接表来实现。
- 邻接矩阵：每行每列代表图中的顶点，行列值表示节点是否相连;简单，但大多为稀疏矩阵效率低下。
- 邻接列表：一个列表中包含所有顶点，其中每个顶点关联一个与自身有连接的顶点的列表；存储空间紧凑高效。
词梯问题
- 目标:找到从一个单词到另一个单词之间最短的变换序列。
步骤一：将所有单词的关系表达为图
-
方法一：将所有单词之间互相比较；思路简单，但计算量大。
-
方法二：创建桶，将去掉一个字母后相同的单词放入统一桶中，最后对统一桶中的单词构建边。
def buildGraph(wordfile): d = {} #桶 # 构建桶，并将相同的单词放入桶中 for line in wfile: word = line[:-1] for i in range(len(word)): bucket = word[:i] + '_' + word[i+1:] if bucket in d: d[bucket].append(word) else: d[bucket]=word ......
步骤二：采用广度优先搜索(Breadth First Search)寻找所有有效路径
BFS搜索时，在达到更远距离K+1前会找到全部距离为K的顶点。
搜索时需要添加距离，前驱节点，颜色三个属性，并使用队列对已发现顶点进行排列。其中颜色中白色代表尚未发现，灰色代表以及发现，黑色代表已经完成探索。
步骤三：选择最优路径
最后通过追溯函数即可确定最短词梯。
骑士周游问题
目标：从棋盘上一个点走遍所有棋盘上的点；建建立一个没有分支的最深的深度优先树，表现为一条线性的包含所有节点的退化树。
步骤一：构建图
根据马走’日’的特性设置相对位置并保证不会超过棋盘边界。之后通过遍历构建出图。
步骤二：寻找一个路径恰好将所有节点包含所有节点且只经过一次
通过深度优先搜索算法(Depth First Search)实现。**DFS:沿着树的单枝尽量深入向下搜索，如果无法找到解就回溯到上一层搜索下一枝。**在骑士周游问题中每个顶点仅访问一次。
如果沿单枝搜索至无法继续路径仍没有达到预定值（棋盘格数），就清除颜色标记递归调用函数切换至下一枝（灰色代表以及探索，白色代表未探索）。在搜索过程中使用一个栈还记录路径便于回溯。
搜索算法的改进
修改遍历下一格的次序。改为具有最少合法移动目标的格子优先搜索。（启发式规则）
通用深度优先搜索
有时候深度优先搜索会创建多棵树，称为"深度优先森林"。
通用DFS算法中加入发现时间和结束时间两个属性。
在访问一个节点时将节点设置为灰色（搜索中），并记录开始时间。对该节点连接的白色（未搜索）节点递归调用函数（深度优先向下搜索）。最后搜索完成后将节点改为黑色（搜索完成），并记录结束时间。
图的应用
-
拓扑排序：从工作流程图（DAG图：有向无环）得到工作次序排列的算法。利用DFS实现。
-
强连通分支：图G的子集C中任意两个顶点间都有路径来回，且C是具有这样性质的最大子集。图和专职图在强连通分支的数量和划分上是相同的。
1.对图G使用DFS算法，计算每个顶点的结束时间。
2.将图G转置使用DFS算法，以顶点结束时间倒序顺序搜索。
3. 深度优先森林中的每一颗树就是一个强连通分支。 -
最短路径：当图已知时，带权图的最短路径问题可以看作词梯问题的改进。使用Dijkstra算法实现。
Dijkstra算法:在顶点vertex类中的成员dist用于记录开始顶点到到本顶点的最短带权路径长度（权重之和），算法对图中的每个顶点迭代一次，得出从一个顶点到其余所有顶点的最短路径。【只能处理权重大于0的图】
-
最小生成树
信息广播问题：
1.最简单解法时由广播源维护一个收听者列表，将每个消息向每个收听者发送一次。
2.洪水解法：将每条消息在路由器间散布出去。每个路由器将消息分别转发到相邻的路由器和收听者，并加入TTL（消息源到收听者的最远距离）。
3.最小权重生成树。生成树：拥有图中所有顶点和最小数量的边，以保持连通的子图。使用Prim算法，每部都沿着最小权重的边向前搜索实现。