数据结构 图
时间：2019-05-15 11:57:18
参考：
图¶
图由顶点和边组成。图可以通过邻接矩阵（稀疏图）、邻接表（稠密图）或其它方式表示。
图算法¶
图遍历算法¶
深度优先搜索¶
对于给定顶点，依次递归访问第一个邻接节点，第二个邻接节点...
伪代码如下：
void deepFirstSearch(Vertex v) {
print(v)
//对于邻接节点,如果有邻接节点
if has adj_vertex
for v_a in adjs:
deepSearch(v_a);
else:
return;
}
广度优先搜索¶
对于给定节点，先访问该节点的所有邻接节点，再访问邻接节点的邻接节点。类似于有层次的访问。通常使用队列作为层次访问的数据结构。
假设洋葱的中心是要访问的初始顶点，中心之外一层的洋葱上的点到中心点的距离为 1，再外面一层上的点到中心的距离为2，依次类推。广度优先搜索要做的就是先把中心外第一层上的点都访问一遍，再把第二层的上的点访问一遍，依次类推。
伪代码：
//初始化队列
queue.enQueue(v)
breadthFirstSearch(queue)
//广度优先搜索
void breadthFirstSearch(Queue queue){
v = queue.deQueue();
//队列为空搜索结束
if(v == null || 节点满足指定条件)
return
print(v)
//有邻接节点则邻接节点入队
if v has v_adj_vertex
for v_j in v_adjs:
queue.enQueue(v_j)
else:
return;
}
Dijkstra 算法¶
计算起始点到其它点的最短路径。对于有权图，无权图可以看作点与点之间的路径长度都为1。
初始化工作：
dist[int]: 表示指定点，到另一个点的最短距离。初始化dist：起始点为0，其余为正无穷。path[int]: 表示经过哪一个点到当前点的路径最短。初始化path：所有都为-1，算法完成之后起始点的 path 仍为-1。visited[boolean]：记录顶点是否已经访问。
算法描述:
- 访问起始点，标记起始点为已经访问。
- 把起始点的邻接点的
dist[]赋值为dist[起始点] + 起始点邻到接点的距离。 - 从没有访问的节点中找一个
dist值最小的顶点做下一个顶点，记录顶点已访问。如果找不到则算法结束，如果找到继续下一步。 - 比较每一个没有访问的邻接点的
dist[邻接点]和dist[当前点] + 当前点邻接点的距离的大小，如果大于则找到了另一条最短的路径，更新dist的值，并更新path的值为当前节点。 - 回到第三步。
伪代码：
void dijkstra(Vertex v) {
while true:
//
v = 没有被访问的点中 dist 最小的点
if v == null:
return
//变更邻接节点的最短路径
for v_a in adjs:
if dist[v_a] > dist[v] + v 到 v_a 的距离
dist[v_a] = dist[v] + v 到 v_a 的距离
path[v_a] = v
}
Floyd 算法¶
计算图中所有点之间的最短距离。
准备工作：
以邻接矩阵 Graph[][] 表示的图为例。以二维数组 Dist[][] 记录点到点的最短距离，以二维数组 Path[][] 记录点到点之间的最短路径需要经过的点。
算法描述：
- 初始化
Dist[][]对角线的值为正无穷。初始化Path[][]的值为 -1。 - 初始化
Dist[i][j]的距离为Graph[i][j]。 - 以矩阵中的第一个点
k为中间点，比较Dist[i][j]和Dist[i][k]+Dist[k][j]的大小，如果大于则设置Dist[i][j] = Dist[i][k] + dist[k][j]Path[i][j] = k。 - 以矩阵中的第二个点为中间点...依次类推直到最后一个点，结束算法。
伪代码：
//N 代表点的个数
for (int i = 0; i < N; i++) {
for(int j = 0; j < N; j ++) {
Dist[i][j] = Graph[i][j] > 0 ? Graph[i][j]: 正无穷
}
}
for (int k = 0 ; k < N; k ++) {
for (int i = 0; i < N; i++) {
for(int j = 0; j < N; j ++) {
if(Dist[i][j] > Dist[i][k] + Dist[k][j]) {
Dist[i][j] = Dist[i][k] + Dist[k][j]
Path[i][j] = k
}
}
}
}
最小生成树算法¶
Prim 算法¶
从当前已经选择的顶点中选择一条出边最短的路径（出边的下一个顶点不能是已经选择的顶点）。直到已经选择的边的数量为 顶点数 - 1。
Kruskal 算法¶
从所有没有被选择的边中选择一条权值最小的边，把边连接的顶点标记为已经选择。
从所有未选择的边中选择一条权值最小的边，把边连接的顶点加入已选择顶点集合。选择的边不能然已选择的边和组成的图中包含循环。直到选择的边数为 顶点数 - 1。