无向图中两点(x1,y1)(x2,y2)是否连通(bfs&并查集)两种方法解决(c++)

1.bfs

//bfs看两点是否联通
#include <bits/stdc++.h>
using namespace std;
 
// 用于BFS的辅助函数，检查坐标是否在网格内
bool isValid(int x, int y, int n, int m) {
	return x >= 0 && x < n && y >= 0 && y < m;
}
 
// BFS函数，判断两个点是否连通
bool bfs(const vector<vector<int>>& grid, int startX, int startY, int targetX, int targetY) {
	int n = grid.size();
	int m = grid[0].size();
	
	// 访问标记数组
	vector<vector<bool>> visited(n, vector<bool>(m, false));
	
	// 队列用于存储待访问的节点
	queue<pair<int, int>> q;
	
	// 初始点入队
	q.push({startX, startY});
	visited[startX][startY] = true;
	
	while (!q.empty()) {
		auto front = q.front();
		q.pop();
		
		int x = front.first;
		int y = front.second;
		
		// 检查是否到达目标点
		if (x == targetX && y == targetY) {
			return true; // 连通
		}
		
		// 检查上下左右四个方向
		vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
		for (auto& dir : directions) {
			int newX = x + dir.first;
			int newY = y + dir.second;
			
			if (isValid(newX, newY, n, m) && !visited[newX][newY] && grid[newX][newY] == 0) {
				q.push({newX, newY});
				visited[newX][newY] = true;
			}
		}
	}
	
	return false; // 不连通
}
 
int main() {
	// 示例网格，0 表示可通行，1 表示障碍物
	vector<vector<int>> grid = {
		{0, 0, 1, 0, 0},
		{0, 1, 0, 1, 0},
		{0, 0, 0, 0, 0},
		{1, 1, 0, 1, 0},
		{0, 0, 0, 0, 0}
	};
	
	int startX = 0; // 起始点 x 坐标
	int startY = 0; // 起始点 y 坐标
	int targetX = 4; // 目标点 x 坐标
	int targetY = 4; // 目标点 y 坐标
	
	if (bfs(grid, startX, startY, targetX, targetY)) {
		cout << "Points are connected." << endl;
	} else {
		cout << "Points are not connected." << endl;
	}
	
	return 0;
}

2.并查集

#include <iostream>
#include <vector>
using namespace std;
 
class UnionFind {
private:
	vector<int> parent;
	vector<int> rank;
	
	int find(int x) {
		if (x != parent[x]) {
			parent[x] = find(parent[x]); // 路径压缩
		}
		return parent[x];
	}
	
public:
	UnionFind(int n, int m) : parent(n * m), rank(n * m, 1) {
		for (int i = 0; i < n * m; ++i) {
			parent[i] = i; // 初始时，每个节点的父节点是它自己
		}
	}
	
	void unionSets(int x, int y) {
		int rootX = find(x);
		int rootY = find(y);
		if (rootX != rootY) {
			if (rank[rootX] < rank[rootY]) {
				parent[rootX] = rootY;
			} else if (rank[rootX] > rank[rootY]) {
				parent[rootY] = rootX;
			} else {
				parent[rootY] = rootX;
				rank[rootX]++;
			}
		}
	}
	
	bool isConnected(int x, int y) {
		return find(x) == find(y);
	}
};
 
bool isValid(int x, int y, int n, int m) {
	return x >= 0 && x < n && y >= 0 && y < m;
}
 
int main() {
	vector<vector<int>> grid = {
		{0, 0, 1, 0, 0},
		{0, 1, 0, 1, 0},
		{0, 0, 0, 0, 0},
		{1, 1, 0, 1, 0},
		{0, 0, 0, 0, 0}
	};
	
	int n = grid.size();
	int m = grid[0].size();
	int x1 = 0, y1 = 0; // 起始点坐标
	int x2 = n - 1, y2 = m - 1; // 目标点坐标
	
	UnionFind uf(n, m);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (grid[i][j] == 0) {
				if (i + 1 < n && grid[i + 1][j] == 0) {
					int id1 = i * m + j;
					int id2 = (i + 1) * m + j;
					uf.unionSets(id1, id2);
				}
				if (j + 1 < m && grid[i][j + 1] == 0) {
					int id1 = i * m + j;
					int id2 = i * m + (j + 1);
					uf.unionSets(id1, id2);
				}
			}
		}
	}
	
	bool connected = uf.isConnected(y1 * m + x1, y2 * m + x2);
	cout << "Points (" << x1 << ", " << y1 << ") and (" << x2 << ", " << y2 << ") are "
	<< (connected ? "connected" : "not connected") << "." << endl;
	
	return 0;
}

3.总结

对于这两种算法，它们的时间复杂度在最坏情况下都可以达到 O(n * m)。然而，在实际应用中，由于并查集的路径压缩优化，它在处理大规模数据时通常比 BFS 更高效。BFS 可能需要遍历更多的节点，尤其是在网格中有大量障碍物时。而并查集则通过减少查找操作的次数来提高效率。