算法（六）--图

经典图算法

一、图的搜索

深度优先遍历

图示意：

void bfs(vector<vector<int>>& G, vector<bool>& seen, int u) {
	if (减枝条件) {
		return;
	}
	if (满足答案) {
		// 记录结果
		return;
	}
	
	// 访问节点u
	seen[u] = true;
	for (int v: G[u]) {
		// 访问边 u->v
		dfs(G, seen, v);
		// 回溯边 u->v
	}
	// 回溯节点u
	seen[u] = false;
}

G为邻接表

void dfs(vector<vector<int>>& G, vector<bool>& seen, int u) {
    // 如果满足减枝条件，则返回
    if (减枝条件) {
        return;
    }
    // 如果满足答案条件，则记录结果并返回
    if (满足答案) {
        // 记录结果
        return;
    }
    
    // 访问节点 u
    seen[u] = true;
    // 遍历节点 u 的所有邻接节点 v
    for (int v = 0; v < G[u].size(); ++v) {
        // 如果节点 v 与节点 u 相连且 v 未被访问，则递归调用 dfs
        if (G[u][v] == 1 && !seen[v]) {
            // 访问边 u->v
            dfs(G, seen, v);
            // 回溯边 u->v
        }
    }
    // 回溯节点 u
    seen[u] = false;
}

广度优先遍历

void bfs(vector<vector<int>>& graph, int start, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";
        
        for(int i = 0; i < graph[node].size(); i++) {
            if(graph[node][i] == 1 && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

最短路径

单源最短路径Dijkstra

输出起始节点到所有节点的最短距离

未记录路径版

void dijkstra(vector<vector<int>>& graph, int start, vector<int>& dist) {
    int n = graph.size();
    dist.assign(n, INT_MAX);
    dist[start] = 0;
    // 小端优先级队列
    // （节点到指定节点的距离，节点）
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        //如果 d 大于 dist[u]，说明当前节点 u 已经通过其他路径找到了更短的距离，因此我们可以跳过这个节点，继续处理队列中的下一个节点。
        if (d > dist[u]) continue;

        for (int v = 0; v < n; ++v) {
            if (graph[u][v] != 0) {
                int newDist = dist[u] + graph[u][v];
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    pq.push({newDist, v});
                }
            }
        }
    }
}

计算连通性 并查集

class UnionFind {
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    // 查找操作，带路径压缩
    int find(int u) {
        if (parent[u] != u) {
            parent[u] = find(parent[u]); // 路径压缩
        }
        return parent[u];
    }

    // 合并操作，按秩合并
    bool unionSets(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
            return true;
        }
        return false;
    }

private:
    vector<int> parent; // 存储每个节点的父节点
    vector<int> rank;   // 存储每个集合的秩（树的高度）
};

并查集（Disjoint Set Union, DSU）是一种数据结构，用于处理一些不相交集合的合并及查询操作。它支持两种操作：

- 查找（Find）：确定元素属于哪个集合。
- 合并（Union）：将两个集合合并成一个集合。
- 并查集常用于解决连通性问题，例如在Kruskal算法中用于检测是否形成环。

详细解释

1. 初始化：

UnionFind(int n)：构造函数，初始化 parent 和 rank 数组。parent[i] 表示节点 i 的父节点，初始时每个节点的父节点都是它自己。rank[i] 表示以节点 i 为根的树的高度，初始时所有树的高度为 0。

2. 查找操作（Find）：

int find(int u)：查找节点 u 所属集合的根节点，并进行路径压缩。路径压缩的目的是将树的高度降低，从而加快后续的查找操作。
如果 parent[u] != u，说明 u 不是根节点，递归查找 u 的父节点，并将 u 的父节点更新为根节点。

3. 合并操作（Union）：

bool unionSets(int u, int v)：将包含节点 u 和节点 v 的两个集合合并。首先查找 u 和 v 的根节点 rootU 和 rootV。
如果 rootU != rootV，说明 u 和 v 不在同一个集合中，将两个集合合并。合并时按秩合并，即将高度较小的树合并到高度较大的树上。如果两棵树高度相同，则任选一棵树作为根，并将其高度加一。
如果 rootU == rootV，说明 u 和 v 已经在同一个集合中，返回 false 表示合并失败。

最小生成树 Kruskal 算法

vector<vector<int>> kruskal(vector<vector<int>>& edges) {
    sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[2] < b[2];
    });
    UnionFind fa(n);
    vector<vector<int>> tree;
    for(auto &e : edges) {if(fa.unite(e[0], e[1])) tree.push_back(e);}
    return tree;
}

拓步排序

拓扑排序（Topological Sorting）是一种用于有向无环图（DAG）的排序算法，它将图中的所有节点排序，使得对于每一条有向边 ( u \rightarrow v )，节点 ( u ) 在排序中出现在节点 ( v ) 之前。拓扑排序常用于任务调度、编译依赖等场景。

此版本图示意：

vector<int> topologicalSort(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> inDegree(n, 0);
    vector<int> topoOrder;
    queue<int> q;

    // 计算每个节点的入度
    for (int u = 0; u < n; ++u) {
        for (int v : graph[u]) {
            inDegree[v]++;
        }
    }

    // 将所有入度为0的节点加入队列
    for (int i = 0; i < n; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // 处理队列中的节点
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);

        // 将节点 u 的所有邻接节点的入度减1
        for (int v : graph[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 检查是否存在环
    if (topoOrder.size() != n) {
        throw runtime_error("The graph has a cycle!");
    }

    return topoOrder;
}