用途：

  • 社交网络的好友关系

    定义：

  • 非线性数据结构

  • 顶点、边
  • 度：跟顶点相连的边的条数，分为入度和出度
  • 有向图：右边有方向
  • 无向图：有边无方向

  • 带权图：每条边都有权重

    如何存储：

  • 邻边矩阵

    • ->底层依赖二维数组
    • 如果顶点i j之间有边，则a[i][j]标记为1；如果是带权图则存储权重
    • 比较浪费空间，但是数组运算效率比较高

  • 邻接表

    • 每个顶点对应一条链表，链表中存储和这个顶点相连接的顶点
    • 比较节省空间，但是用起来比较耗时间
    • 可以将链表改成红黑树来提高效率

      稀疏图：

  • 顶点很多，但是边不多

    深度优先搜索

  • 回溯思想

    广度优先搜索