数据结构 第6章 图（一轮习题总结）

6.1 图的基本概念（2 4 11）
6.2 图的存储及基本操作（1 12 13 15 16）
6.3 图的遍历（2 3 5 16）
6.4 图的应用

6.1 图的基本概念

• T2
  一个有个顶点和n条边的图，一定是有环的。
• T4
  无向图的连通分量 = 极大连通子图
  图的遍历：每个结点只访问一次；若为非连通图，可能某顶点出不能完全访问。
• T6
  完全无向图中，n个顶点，边=n(n-1)/2
• T11
  极大连通子图：连通分量
  极小连通分量：图的生成树

6.2 图的存储及基本操作

• T1
  图的拓扑序列 / DAG图：一个有向图中不存在环
  （对应的领接矩阵对角线以下元素全为0，图一定没有环，即图的拓扑序列一定存在，但拓扑序列不唯一）
  拓扑排序的算法：
  （1）从有向图中选择一个没有前驱（即入度为0）的顶点并输出。
  （2）从网中删除该顶点，并删除从该顶点出发的全部的有向边。
  （3）重复上述步骤，直到剩余网中不再存在没有前驱的顶点为止。
• T12
  无向图没有自己指向自己的边
  无向图的邻接表最多有n(n-1)个边表结点，每条边存储两边
• T15 T16
  领接多重表——无向图（顶点结点：data firstedge；弧结点…）
  十字链表——有向图：（顶点结点：data firstin firstout；弧结点…）
  领接矩阵、领接表——无向图、有向图

6.3 图的遍历

• T1
  广度优先可以解决各边权值相等的单源最短路径问题
• T2
  在DFSTraverse函数中调用DFS函数的次数 = 连通分量数
• T3
  DFS和BFS的时间复杂度以及空间复杂度都相等
  （1）空间复杂度：O(n)；深度优先DFS—栈；广度优先BFS—队列
  （2）时间复杂度：领接表O(n+e)；领接矩阵O(n²)
• T5
  深度优先遍历的注意点：若出现环，退回求下一个顶点（栈）

6.4 图的应用