数据结构第6章小结

  第六章我们学习了图，首先我掌握了一些图的基本术语。例如：对与具有n个顶点的图，无向完全图是指具有n（n-1）/2条边的无向图；有向完全图是指具有n（n-1）条弧的有向图；对于边或者弧比较少的称为稀疏图，反之称为稠密图；顶点的度是指和该顶点相关联的边的数目，对于有向图，顶点的度分为入度和出度，入度是以该顶点为头的弧的数目，出度是以该顶点为尾的弧的数目；连通图是指对于图中任意两个顶点都是连通的图，连通分量是指无向图中的极大连通子图；强连通图是指有向图中每一对顶点互相存在路径的图，强连通分量是指有向图中的极大强连通子图。然后我还学会了图的两种表示方法，一是邻接矩阵表示法，二是邻接表表示法；对于稀疏图，用邻接表表示比较好，空间复杂度较低，对于稠密图，则邻接矩阵表示较好。接着还学会了两种图的遍历方法，深度优先搜索遍历和广度优先搜索遍历。然后学习了生成最小生成树的两种算法：普利姆算法和克鲁斯卡尔算法，若有两条边权值相同，则最小生成树不唯一。接着还学会了解决最短路径问题的迪杰斯特拉算法。