无向图与有向图邻接表分析：顶点度、边数与存储空间

本资源主要讨论了图在数据结构中的表示方法，特别是通过邻接表来分析无向图和有向图的特性。以下是一些关键知识点： 1. **无向图邻接表**： - **顶点度**：无向图的邻接表中，第i个链表的节点数等于顶点i的度（即与它相连的其他顶点的数量）。每个顶点的度反映了其与其他顶点的连接关系。 - **边数**：所有链表中节点总数的一半代表图中的边数，因为每条边会在两个顶点的邻接链表中各出现一次。 - **存储空间**：无向图的邻接表占用的存储单元数为n（顶点数）加上2e（边数），其中n是顶点的数量，e是边的数量。 2. **有向图邻接表**： - **出度**：在有向图的邻接表中，第i个链表的节点数等于顶点i的出度，即从顶点i出发的边的数量。 - **弧数**：所有链表中节点的总数等于图中的弧数，即有向边的数量。 - **存储空间**：有向图的邻接表占用的存储单元数为n（顶点数）加上e（弧数），相比于无向图，少了一半的边数。 3. **图的定义和术语**： - **图**：由顶点集合V和边（无向或有向）集合E组成，如无向图的边是无序对，而有向图的边是有序对。 - **有向图和无向图**：区别在于无向图的边是无序对，表示两点之间的双向连接，而有向图的边是有序对，表示方向性。 - **完全图**：有向完全图中任意两顶点之间有两条相反方向的弧，无向完全图中任意两顶点之间有一条直接边。 - **权值**：与图的边或弧关联的数值，可以代表诸如长度、时间等特定意义。 - **网**：指带权的图，权值赋予图更丰富的信息。 4. **实际应用**： - 权值在实际问题中具有重要作用，例如在交通网络图中，权值可能表示路线长度或等级；工程进度图中，权值可能代表工序间的依赖时间。 总结来说，这个资源主要讲述了如何通过邻接表形式来表示和理解无向图和有向图，以及它们在度量、存储需求和实际问题中的应用。掌握这些概念对于理解和处理图算法、网络分析和优化等问题至关重要。