图论与图算法概览

"第四章：图-2021-11" 在计算机科学中，图是数据结构的一种重要形式，它用于表示对象之间的关系。本章主要涵盖了图论的基本术语，图的表示方法，图的搜索算法，以及图与树的联系，特别强调了强联通图和最短路径的计算。以下是关于这些知识点的详细说明： 1. **基本术语（图论）**： - **顶点（Vertex）**：图中的基本元素，代表一个实体或概念。 - **边（Edge）**：连接两个顶点的关系，表示它们之间的联系。 - **邻接（Adjacency）**：如果一条边连接两个顶点，那么这两个顶点互为邻接。 - **无向图（Undirected Graph）**：边没有方向，表示相互关系。 - **有向图（Directed Graph）**：边有方向，表示从一个顶点到另一个顶点的单向关系。 - **权重（Weight）**：边可能附带的数值，表示两个顶点之间关系的强度或距离。 2. **强联通图**： - 在有向图中，如果图中任意两个顶点都互相可达，即存在从每个顶点到其他所有顶点的路径，那么这个图称为强联通图。 3. **图的表示**： - **邻接矩阵（Adjacency Matrix）**：使用二维数组存储图，矩阵的每个元素表示对应顶点之间是否存在边，如果存在，根据边是否有权重而设置为1或相应的权重值。 - **邻接表（Adjacency List）**：为每个顶点存储一个列表，列表包含与其邻接的所有顶点，节省空间，适用于稀疏图。 - **邻接多重表（Adjacency Multilist）**和**十字链表（Cross-Linked List）**：是邻接表的变体，更灵活地处理多条边的情况。 4. **图的搜索算法**： - **深度优先搜索（Depth First Search, DFS）**：从一个顶点开始，尽可能深地探索图的分支，直到到达叶子节点，然后回溯。 - **广度优先搜索（Breadth First Search, BFS）**：从一个顶点开始，逐层地访问所有相邻的顶点，直到访问完所有顶点。 5. **图与树的联系**： - 树是一种特殊的图，其中任何两个顶点间有且仅有一条路径。树的根节点没有前驱，叶节点没有后继，非叶节点的子树个数不小于1。 6. **最短路径**： - **Dijkstra算法**：用于计算有向图中单源最短路径，假设所有边的权重都是非负的。 - **Floyd-Warshall算法**：用于计算所有顶点对间的最短路径，适用于所有边可能有负权重的图。 - **Bellman-Ford算法**：可以处理边权重为负的情况，但不能处理负权环。 7. **拓扑排序**： - 对于有向无环图（DAG），拓扑排序是将所有顶点排成线性的序列，使得对于每条有向边 (u, v)，顶点 u 都在顶点 v 之前。 8. **关键路径**： - 在有向无环图中，关键路径是一条具有最长路径长度的路径，它表示项目中最长的不受延误的部分，对项目的完成时间至关重要。 教学要求强调了理解图的逻辑结构，掌握图的存储结构（如邻接矩阵和邻接表），以及实现图的遍历算法。此外，还需要掌握最小生成树（如Prim算法或Kruskal算法）、最短路径（如Dijkstra算法）、拓扑排序和关键路径算法的基本思想、原理和实现过程。 考试大纲中列出的图的基本概念包括邻接矩阵、邻接表等存储结构，以及深度优先搜索和广度优先搜索等遍历方法。同时，图的应用包括寻找最小生成树、最短路径、拓扑排序和关键路径等实际问题的解决。