首页 书籍 深入浅出程序设计竞赛

# 图的概念与建立

图是数学和计算机科学中的一个基本概念，用于表示物件（顶点或节点）之间的关系（边）。图可以用来模拟现实世界中的许多类型的关系，比如社交网络中的人际关系、城市间的道路网络、网页之间的链接等。

# 图的基本概念

  1. 顶点（Vertex）：图中的一个节点，可以表示一个实体。
  2. 边（Edge）：连接两个顶点的线，可以是有向的（箭头指向某一方向，表示关系的方向）或无向的（没有箭头，表示双向关系）。
  3. 路径（Path）：顶点的一个序列，其中任意两个连续的顶点之间都通过边相连。
  4. 循环（Cycle）：起点和终点相同的路径。
  5. 连通图（Connected Graph）：在无向图中，如果任意两个顶点之间都存在路径，则称该图为连通图。
  6. 强连通图（Strongly Connected Graph）：在有向图中，如果任意两个顶点之间都存在双向路径，则称该图为强连通图。
  7. 加权图（Weighted Graph）：图的边被赋予了权重（代表成本、距离等）。

# 图的表示方法

图主要有两种表示方法：邻接矩阵和邻接表。

  1. 邻接矩阵（Adjacency Matrix）：使用二维数组 adjMatrix[u][v] 表示顶点 u 和顶点 v 之间的关系。对于无权图，如果 u 和 v 之间有边，则 adjMatrix[u][v] = 1 ；否则为 0。对于加权图， adjMatrix[u][v] 存储的是边的权重。邻接矩阵的空间复杂度为 O (V^2)，其中 V 是顶点数。
int adjMatrix[V][V];
  1. 邻接表（Adjacency List）：对每个顶点，存储一个列表，其中包含与该顶点直接相连的所有顶点。这是图表示的更为紧凑方式，特别是对于稀疏图（边数远小于顶点数的平方）。邻接表的空间复杂度为 O (V+E)，其中 V 是顶点数，E 是边数。
#include <vector>
using namespace std;
vector<int> adjList[V];  // 对于无权图
vector<pair<int, int>> adjList[V];  // 对于加权图，pair 中存储相邻顶点和边的权重
# 图的建立


建立图的过程取决于图的类型（有向图 / 无向图，加权图 / 非加权图）以及选择的表示方法（邻接矩阵 / 邻接表）。以下是一个使用邻接表表示无向非加权图的简单例子：


int V;  // 顶点数
vector<int> adjList[V];  // 邻接表
// 添加边
void addEdge(int u, int v) {
    adjList[u].push_back(v);
    adjList[v].push_back(u);  // 因为是无向图，所以也需要添加 v 到 u 的边
}
对于其他类型的图，建立过程类似，只是在处理边的添加时需要考虑方向（对于有向图）和权重（对于加权图）。


# 图的遍历


图的遍历是指按照一定的规则访问图中所有顶点，且每个顶点仅被访问一次。图的遍历有两种基本方式：深度优先搜索（DFS）和广度优先搜索（BFS）。这两种遍历方式在解决如路径查找、图的连通性分析等问题时非常有用。


# 深度优先搜索（DFS）


深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。该算法沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点 v 的所在边都已被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。


DFS 算法步骤：


    

  1. 选择一个起点。
    2. 

  2. 访问该起点，并将其标记为已访问。
    3. 

  3. 选择一个与当前顶点相邻的未访问顶点，从该顶点再次执行 DFS。
    4. 

  4. 重复步骤 2 和 3，直到没有未访问的相邻顶点为止。然后回溯，继续探索未被访问的顶点。
    5. 

  5. 重复以上步骤，直到所有顶点都被访问过。
    6. 



# 广度优先搜索（BFS）


广度优先搜索（Breadth-First Search, BFS）是一种用于图的查找算法，它从一个节点开始，逐层遍历图中的节点，先访问离起始点最近的节点。


BFS 算法步骤：


    

  1. 选择一个起点，并将其加入队列中。
    2. 

  2. 从队列中移除一个顶点并访问它。
    3. 

  3. 将所有未访问的、与刚访问的顶点相邻的顶点加入队列。
    4. 

  4. 重复步骤 2 和 3，直到队列为空。
    5. 



# 示例代码


以下是使用 C++ 实现的 DFS 和 BFS 的简单示例，假设图以邻接表形式给出。


#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 邻接表表示图
vector<int> adj[10]; // 假设图最多有 10 个顶点
bool visited[10]; // 访问标记数组
// DFS 实现
void dfs(int v) {
    visited[v] = true;
    cout << v << " ";
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
        }
    }
}
// BFS 实现
void bfs(int s) {
    queue<int> q;
    q.push(s);
    visited[s] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        cout << v << " ";
        for (int u : adj[v]) {
            if (!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }
}
int main() {
    // 假设有一些添加边的操作填充 adj
    // 初始化 visited 数组
    fill_n(visited, 10, false);
    cout << "DFS: ";
    dfs(0); // 假设从顶点 0 开始 DFS
    cout << endl;
    // 再次初始化 visited 数组
    fill_n(visited, 10, false);
    cout << "BFS: ";
    bfs(0); // 假设从顶点 0 开始 BFS
    cout << endl;
    return 0;
}
在实际应用中，图可能包含循环或者是不连通的，因此在实现 DFS 和 BFS 时需要注意处理这些情况，确保每个节点只被访问一次。


# DAG 与拓扑排序


有向无环图（Directed Acyclic Graph，简称 DAG）是一种特殊类型的有向图，它不包含任何环。这意味着在 DAG 中，不可能从某个顶点 v 出发通过一系列的有向边回到 v 本身。DAG 在计算机科学中有着广泛的应用，如表示工程项目中的任务安排、编译原理中的指令调度、数据分析中的依赖解析等。


# 拓扑排序


拓扑排序是 DAG 的一个重要概念，它是将 DAG 中的所有顶点排成一个线性序列，使得对于任何从顶点 u 到顶点 v 的有向边 uv，在这个序列中 u 都出现在 v 之前。拓扑排序不是唯一的，一个 DAG 可能有多个合法的拓扑排序结果。


拓扑排序的一个常见应用场景是任务调度问题，在这个问题中，每个任务可能依赖于其他任务的完成，而拓扑排序可以提供一个合理的任务执行顺序。


# 如何进行拓扑排序


拓扑排序的一个经典算法是基于深度优先搜索（DFS）的方法。该方法从 DAG 的任一未被访问的顶点出发，递归地探索该顶点的每一个邻接点，然后将顶点加入到一个栈中。当探索完所有顶点后，从栈顶到栈底的顺序就构成了一个拓扑排序。


另一个常用的算法是基于入度（即指向顶点的边的数量）的 Kahn 算法。该算法的步骤如下：


    

  1. 计算图中所有顶点的入度。
    2. 

  2. 将所有入度为 0 的顶点加入到一个队列中。
    3. 

  3. 从队列中取出一个顶点，将其加入到拓扑排序的结果中，并将该顶点的所有邻接点的入度减 1。如果某个邻接点的入度减为 0，则将其加入队列。
    4. 

  4. 重复步骤 3，直到队列为空。
    5. 



如果图中存在环，则无法完成拓扑排序，这可以通过检查排序结果中的顶点数是否与图中的顶点总数相等来判断。


# 示例代码


以下是使用 Kahn 算法实现拓扑排序的简单示例：


#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 函数进行拓扑排序，返回排序后的结果
vector<int> topologicalSort(int V, vector<vector<int>>& adj) {
    vector<int> in_degree(V, 0);
    vector<int> topo; // 存储拓扑排序的结果
    queue<int> q;
    // 计算所有顶点的入度
    for (int u = 0; u < V; ++u) {
        for (int v : adj[u]) {
            in_degree[v]++;
        }
    }
    // 将所有入度为 0 的顶点加入队列
    for (int i = 0; i < V; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);
        // 减少所有邻接顶点的入度
        for (int v : adj[u]) {
            if (--in_degree[v] == 0) {
                q.push(v);
            }
        }
    }
    // 如果 topo 的大小小于 V，则图中存在环，不能进行拓扑排序
    if (topo.size() != V) {
        cout << "The graph has a cycle and cannot be topologically sorted." << endl;
        return {};
    }
    return topo;
}
int main() {
    int V = 6; // 顶点数
    vector<vector<int>> adj(V); // 邻接表表示图
    // 添加边示例
    adj[5].push_back(2);
    adj[5].push_back(0);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);
    vector<int> topo = topologicalSort(V, adj);
    cout << "Topological Sorting: ";
    for (int v : topo) {
        cout << v << " ";
    }
    cout << endl;
    return 0;
}
这段代码首先计算了每个顶点的入度，然后使用 Kahn 算法进行拓扑排序，并打印出排序的结果。如果图中存在环，则会提示无法进行拓扑排序。


      

          
          
      

  


   


    

  
    
      
    
    更新于