第6章 图.ppt

【图的定义与基本术语】 图是数据结构中一种重要的概念，它由顶点集合（Vertex）和顶点之间的关系集合（边或弧）组成，记作G=(V,E)。这里的V代表顶点集合，E代表边或弧的集合。 1. **无向边与有向边**： - 无向边是不具有方向性的，表示两个顶点之间的双向连接，用无序偶对(vi，vj)表示。 - 有向边是有方向性的，也称为弧，用有序偶对(<vi，vj>)表示，意味着从vi指向vj。 2. **无向图与有向图**： - 无向图中任意两个顶点间的边没有方向，例如图6.1(a)所示的无向图G1。 - 有向图中所有边都有方向，如图6.1(b)所示的有向图G2。 3. **弧头与弧尾**： - 在有向图中，弧头是指弧的方向终点，而弧尾是起点。 4. **权与网**： - 权是边或弧上附加的数据，可以表示距离、时间、成本等。带有权值的图称为网，如图6.2(a)和6.2(b)所示的无向网G3和有向网G4。 5. **完全图**： - 无向完全图是任何两个顶点间都有边相连的图，边数为n(n-1)/2。 - 有向完全图则是任何两个顶点间都有方向相反的两条弧，边数为n(n-1)。 6. **稠密图与稀疏图**： - 稠密图接近完全图，边数较多。 - 稀疏图边数相对较少，相对于其顶点数来说。 7. **子图**： - 如果一个图G2的顶点集合V2和边集合E2都是另一个图G1的顶点集合V1和边集合E1的子集，那么G2是G1的子图。 8. **邻接点与度**： - 两个顶点如果有一条边相连，它们就是邻接点。 - 无向图中，一个顶点的度是与其相邻的边数。 - 有向图中，顶点的出度是作为弧尾的弧的数量，入度是作为弧头的弧的数量。 【图的存储表示】 图的存储方式主要有两种：邻接矩阵和邻接表。 1. **邻接矩阵**： - 邻接矩阵是一个二维数组，用于表示图中顶点之间的邻接关系。对于无向图，矩阵是对称的；对于有向图，矩阵可能不对称。 2. **邻接表**： - 邻接表是每个顶点都有一个链表，链表中包含所有与该顶点邻接的其他顶点。这种方式节省空间，尤其适用于稀疏图。 【图的遍历】 图的遍历包括深度优先遍历（DFS）和广度优先遍历（BFS）。 1. **深度优先遍历**： - 从一个顶点出发，尽可能深地探索图的分支，直到达到叶子节点，然后回溯。 2. **广度优先遍历**： - 从一个顶点开始，先访问所有与其相邻的顶点，然后逐层向外扩展。 【图的操作与算法】 1. **最小生成树**： - 如Prim或Kruskal算法，用于找到一个连接所有顶点的最小权值总和的子图。 2. **拓扑排序**： - 对有向无环图（DAG）进行排序，使得对于每条有向边<u, v>，u总是在v之前。 3. **关键路径**： - 在有向加权图（AOE网）中找到最长路径，用于项目管理。 4. **最短路径**： - Dijkstra算法或Floyd-Warshall算法，用于找到图中两个顶点间的最短路径。 通过学习这些图的理论和算法，我们可以解决许多实际问题，如网络路由、任务调度、社交网络分析等。理解并掌握图的概念和操作是计算机科学中的重要基础。