数据结构-图习题.doc

在数据结构中，图是一种重要的抽象数据类型，用于表示对象之间的关系。图由顶点（Vertex）和边（Edge）组成，边连接了两个顶点。本题涉及了无向完全图、有向图、强连通图、图的表示方法以及图的一些基本性质。 1. **无向完全图**：在一个无向图中，如果任意两个不同的顶点之间都存在一条边，则称此图是无向完全图。例如，1个顶点的无向完全图无边，2个顶点的无向完全图有1条边，3个顶点的无向完全图有3条边（AB, AC, BC），以此类推。公式表示为n个顶点的无向完全图有n(n-1)/2条边，这是由于每条边被计算了两次，一次作为起点，一次作为终点。 2. **强连通图**：在有向图中，如果从每个顶点都能通过一系列有向边到达图中的任何其他顶点，则该图称为强连通图。在问题中，给出的有向图不是强连通图，因为无法从某些顶点回到自身。强连通图的判断可以通过拓扑排序或者深度优先搜索来完成。 3. **图的表示**：图可以使用邻接矩阵、邻接表和邻接多重表来表示。 - **邻接矩阵**：用一个二维数组表示，矩阵的大小是顶点数的平方，矩阵中的元素表示对应顶点间是否存在边。如果图是无向的，矩阵是对称的；如果是有向的，矩阵可能不对称。邻接矩阵适合表示稠密图（边数接近顶点数的平方）。 - **邻接表**：为每个顶点维护一个列表，列表中存储了所有与该顶点相邻的顶点。邻接表节省空间，适合表示稀疏图（边数远小于顶点数的平方）。 - **邻接多重表**（十字链表）：结合了邻接矩阵和邻接表的优点，对于无向图，每个顶点有两个列表，分别表示其出边和入边。 4. **稀疏矩阵**：如果一个图的边数远小于顶点数的平方，那么它的邻接矩阵是稀疏的，反之则为稠密的。对于1000个顶点的图，如果有1000条边，那么邻接矩阵是稀疏的，因为非零元素个数远少于矩阵元素总数。 5. **图的性质**： - **无向连通图的最小边数**：n个顶点的无向连通图至少需要n-1条边，形成一棵树形结构。 - **有向强连通图的最小边数**：n个顶点的有向强连通图至少需要n条边，使得每个顶点都能到达其他所有顶点。 6. **图的查询**：使用邻接矩阵可以方便地查询图的边数、两个顶点之间是否存在边以及顶点的度（与之相连的边数）。例如，检查顶点i和j之间是否有边，只需查看邻接矩阵中的A[i][j]是否非零；顶点i的度等于邻接矩阵中第i行或第i列的非零元素个数。 以上就是关于“数据结构-图习题.doc”中涉及的图论知识的详细解析，包括无向完全图的性质、强连通图的判断、图的表示方法以及图的基本查询操作。这些知识是理解图算法和设计图数据结构的基础。