Skip to content

Latest commit

 

History

History

graph

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
demo_adjacency_list_1.c
demo_adjacency_list_1.c
 
 
demo_adjacency_list_2.cpp
demo_adjacency_list_2.cpp
 
 
demo_adjacency_matrices_1.cpp
demo_adjacency_matrices_1.cpp
 
 
demo_adjacency_matrices_2.c
demo_adjacency_matrices_2.c
 
 
demo_astar_1.cpp
demo_astar_1.cpp
 
 
demo_astar_2.cpp
demo_astar_2.cpp
 
 
demo_breadth_fist_search_1.cpp
demo_breadth_fist_search_1.cpp
 
 
demo_breadth_fist_search_2.cpp
demo_breadth_fist_search_2.cpp
 
 
demo_connected_components_1.cpp
demo_connected_components_1.cpp
 
 
demo_depth_first_search_1.c
demo_depth_first_search_1.c
 
 
demo_depth_first_search_2.cpp
demo_depth_first_search_2.cpp
 
 
demo_depth_first_search_3.cpp
demo_depth_first_search_3.cpp
 
 
demo_depth_first_search_4.cpp
demo_depth_first_search_4.cpp
 
 
demo_dijkstra_1.cpp
demo_dijkstra_1.cpp
 
 
demo_graph_color_1.cpp
demo_graph_color_1.cpp
 
 
demo_graph_or_tree_1.c
demo_graph_or_tree_1.c
 
 
demo_hungarian_algorithm_1.cpp
demo_hungarian_algorithm_1.cpp
 
 
demo_topo_sort_1.cpp
demo_topo_sort_1.cpp
 
 
demo_topo_sort_2.c
demo_topo_sort_2.c
 
 
demo_topo_sort_3.c
demo_topo_sort_3.c
 
 
demo_translation_system_1.cpp
demo_translation_system_1.cpp
 
 
readme.md
readme.md
 
 

readme.md

图的类别

  • 无向图
    • avatar
    • 顶点(vertex)
      • 图中的元素就叫做顶点
    • 边(edge)
      • 图中的一个顶点可以与任意其他顶点建立连接关系，我们把这种建立的关系叫做边
    • 度(degree)
      • 以微信举例，可以把每个用户看作一个顶点。如果两个用户之间互为好友，那么就在两者之间建立一条边
      • 其中，每个用户有多少好友，对应图中，就叫做顶点的度。就是跟顶点相连接的边的条数
  • 有向图
    • avatar
    • 入度(In-degree)
      • 顶点的入度，表示有多少边指向这个顶点
      • 对应到微博的例子，入度就表示有多少粉丝
    • 出度(Out-degree)
      • 顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点
      • 对应到微博的例子，出度就表示关注来多少人
  • 带权图
    • avatar
    • 在带权图中，每条边都有一个权重(weigth), 我们可以通过这个权重来表示QQ好友间的亲密度

邻接矩阵存储方法

  • 邻接矩阵(Adjacency Matrix)
    • avatar
    • 优点
      • 邻接矩阵的存储方式简单，直接
      • 因为基于数组，所以在获取两个顶点的关系时，就非常高效
      • 邻接矩阵存储图的另外一个好处是方便计算。比如求解最短路径时候，会提到一个Floyd-Warshall 算法，就是利用矩阵循环相乘若干次得到结果
    • 缺点
      • 如果我们存储的是稀疏图(Sparse Matrix), 也就是说，顶点很多，但每个顶点的边并不多，那么邻接矩阵的存储方法就更加浪费空间来
      • 比如，微信有好几亿的用户，对应到图上就是好几亿的顶点
      • 但是每个用户的好友并不会喝多，一般也就是三五百个而已。如果用邻接矩阵来存储，那绝大部分的存储空间都被浪费了
  • 邻接表(Adjacency List)
    • avatar
    • 邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间。相反，邻接表存储起来比较节省空间，但是用起来比较耗时间
    • 缺点
      • 以图中的例子，如果要确定，是否存在一条从顶点2到顶点4的边，那就要遍历顶点2对应的那条链表，看链表中是否存在顶点4.
      • 但链表的存储方式对缓存不友好
      • 而且邻接表的的链表过长，对查询也很不友好
        • 为了提高查找效率，把链表替换成红黑树，跳表，散列表等

广度优先搜索(BFS)

  • 广度优先搜索（Breadth-First-Search），我们平常都把简称为 BFS
  • 直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索
  • avatar
  • V 表示顶点，E表示边的个数
  • 时间复杂度
    • 最坏情况,终止顶点t离起始顶点s很远，需要遍历完整整个图才能找到
    • 这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次
    • 所以，BFS的时间复杂度是O(V + E)
    • 当然，对于一个连通图来说，也就是说一个图中的所有顶点是连通的，E肯定是要大于等于V - 1，所以BFS的时间复杂度可以简单写为 O(E)
  • 空间复杂度
    • BFS空间消耗主要是几个辅助变量 visited数组，queue队列, prev数组
    • 这三个存储空间大小不会超过顶点的个数，所以是O(V)

深度优先搜索(DFS)

  • 深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是“走迷宫”
  • 假设你站在迷宫的某个岔路口，然后想找到出口.你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。
  • avatar
  • 搜索的起始顶点是 s，终止顶点是 t，我们希望在图中寻找一条从顶点 s 到顶点 t 的路径。如果映射到迷宫那个例子，s 就是你起始所在的位置，t 就是出口。
  • 这里面实线箭头表示遍历，虚线箭头表示回退。从图中我们可以看出，深度优先搜索找出来的路径，并不是顶点 s 到顶点 t 的最短路径。
  • 实际上，深度优先搜索用的是一种比较著名的算法思想，回溯思想
  • 时间复杂度
    • 每条边最多会被访问两次，一次是遍历，一次是回退。所以，图上的DFS的时间复杂度是O(E), E表示个数
  • 空间复杂度
    • DFS 的消耗内存主要是 visited, stack数组。visited, stack数组的大小跟顶点的个数V成正比，所以总的空间复杂度O(V)

拓扑排序

偏序
  • avatar
  • 理解偏序，以选课为例子
    • 假设我们学习完V1这门课后，可以选修 V2 或者 V3
    • 这个或者表示，学习V2和V3这两门课没有特定的先后顺序
    • 因此,在我们所有可以选择的课程中，任意两门课程的关系要么是确定的（即拥有先后关系），要么是不确定的（即没有先后关系），绝对不存在互相矛盾的关系(即环路)
    • 抽象而言，有向图中两个顶点之间不存在环路，至于连通与否，是无所谓的。所以，有向无环图必然是满足偏序关系的
全序
  • avatar
  • 全序是偏序的一种特殊情况。它是基于偏序基础上的,有向无环图中的任意一对顶点都需要有明确的关系
  • 反应图中就是单向连通关系，注意不能双向连通，那就成了环
如何用偏序/全序来解释排序结果的唯一性？
  • 我们知道不同整数之间的大小关系是确定的，即1总是小于4的，不会有人说1大于等于4吧，这就是说，这个序列是满足全序关系的
  • 而对于拥有全序关系的结构（如拥有不同整数的数组），在其线性化(排序)之后的结果必然是唯一的
  • 对于排序算法，评价指标之一是看该排序算法是否稳定，即值相同的元素的排序结果是否和出现的顺序一致
    • 比如，我们说快排是不稳定的，这是因为最后的快排结果中相同元素的出现顺序和排序前不一致了
    • 如果用偏序的概念可以这样解释这一想象:相同值的元素之间的关系是无法确定的，因此它们在最终的结果中的出现顺序可以是任意的
    • 而对于插入排序这种稳定性排序，它们对于值相同的元素，还有一个潜在的比较方式，即比较它们的出现顺序，出现靠前的元素大于出现后出现的元素
    • 因此，通过这一潜在的比较，将偏序关系转换为了全序关系，从而保证了结果的唯一性
偏序排序图例
  • avatar
  • 进行拓扑排序，首先找到没有前驱的顶点V1
  • 在删除顶点V1以及作为起点的弧后，继续查找没有前驱的顶点，此时，V2 和 V3都符合条件，可以随机选择一个，最终选择了V2
  • 然后继续重复以上的操作，直至最后找不到没有前驱的节点
  • 最后得到的排序结果有两种 
    V1 -> V2 -> V3 -> V4
V1 -> V3 -> V2 -> V4
拓扑排序案例
  • avatar

Dijkstra 算法

  • 迪杰斯特拉(Dijkstra) 算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径
  • 它的主要特点是以起始点为中心向外层扩展(广度优化搜索思想)，直到扩展为止
  • 其中的最小堆优先级队列，采用了贪心的思想。从小到大排列
  • 图例
    • 以demo_dijkstra_1.cpp为例子
    • avatar

A*算法

  • 以demo_astar_2.cpp为例子
    • avatar
  • 如何快速找出一条接近最短路径
    • 每次找到跟起点最近的顶点，往外扩展
      • 但是，这样会遇到一个问题，离起点近的顶点，可能离终点会越来越远，会存在跑偏的情况
    • 当我们遍历到某个顶点的时候，从起点走到这个顶点的路径长度是确定的，记作g(i)(i表示顶点)。但是，从这个顶点到终点的路径长度是未知的。确切的值无法直到，可以用估算值来替代
      • 我们可以通过这个顶点跟终点之间的直线距离，也就是欧几里得距离，来近似地估计这个顶点跟终点的路径长度，
      • 可以把这个距离记作h(i)(i表示这个顶点的编号)，专业的叫法是启发函数(heuristic function)
      • 整体公式： f(i) = g(i) + h(i). f(i)的专业叫法是估计函数(evaluation function).这样避免“跑偏”的问题
  • 为什么 A* 不像 Dijkstra能找到最短距离
    • Dijkstra 算法算法在回溯的基础上，利用了动态规划的思想，对回溯进行剪枝.同时它也考察了所有从起点到终点的路线，所以可以得到最优解
      • avatar
      • avatar
    • A* 算法利用的是贪心算法的思路，每次找到f的最小值，一旦搜索到终点就不再继续考察其他顶点和路线了

参考资料