图论概论

图的种类

  • 无向图：边没方向
    • 权值：每一条边对应的数值上升
  • 有向图：边有方向

度

  • 度：无向图里面每一个点连着几条边
  • 出度：有向图里面一个点伸出去几条边
  • 入度：有向图里面一个点伸进来几条边

连通性

  • 对于无向图
    • 图里没有断开的，每个点都可以到另外的点，我们称之为连通图
    • 连通分量：极大连通子图（是连通的且包括连通的所有节点，可以有多个）
  • 对于有向图
    • 强连通图：每个点都可以到另外的点（注意方向，任何两个节点是可以相互到达）
    • 强连通分量：是强连通的且包括连通的所有节点，可以有多个

图的构造

  • （朴素存储）：用nnx22数组（n是边数）或者用map（泛化的映射关系）或者用class来存储每条边，也就是存储图
    • 缺点：要确定某个关系必须遍历，慢
  • 邻接矩阵：用一个nxn的数组（n是节点数）
    • 表示有向图：grid[1][2]=6（从节点1指向结点2，权重是6）
    • 表示无向图：grid[1][2]=6且grid[2][1]=6且（从节点1指向结点2，且从结点2指向节点1，所以无向，权重是6）
    • 优点：要确定某两个节点是否相连只需要看对应的grid[ ][ ]是否为0
    • 缺点：要开一个很大的二维矩阵，很浪费内存空间
    • 适用于：边多，节点不太多（稠密图）
  • 邻接表：有一个nx1的数组和一个链表，数组代表了每一个节点，链表表示与每一个节点的连接情况
    • 适用于：节点多，边不太多（稀疏图）

图的遍历

  • BFS
  • DFS