拓扑排序
点击查看代码
public Boolean bfsOptimize(int n, int[][] edges) {
// 初始化入度数组,每个节点有两个元素,第一个元素表示入度,第二个元素暂时未使用
int[][] indegrees = new int[n][2];
// 初始化邻接表,用于存储图的连接关系
List<List<Integer>> adj = new ArrayList<>();
// 遍历所有节点,为每个节点创建一个空的邻接表
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
// 遍历所有边,构建邻接表并更新节点的入度
for (int i = 0; i < edges.length; i++) {
int pre = edges[i][1]; // 边的起点
int next = edges[i][0]; // 边的终点
adj.get(pre).add(next); // 将终点添加到起点的邻接表中
// 更新终点的入度
indegrees[next][0]++;
}
// 初始化队列,用于进行广度优先搜索
Deque<Integer> queue = new LinkedList<>();
// 将所有入度为0的节点加入队列
for (int i = 0; i < n; i++) {
if (indegrees[i][0] == 0) {
queue.addLast(i);
}
}
// 记录已经访问过的节点数量
int count = 0;
// 当队列不为空时,继续搜索
while (!queue.isEmpty()) {
int cur = queue.poll(); // 出队一个节点
System.out.println(cur); // 打印当前节点
count++; // 访问节点数量加1
// 遍历当前节点的所有邻接节点
for (int next : adj.get(cur)) {
indegrees[next][0]--; // 将邻接节点的入度减1
// 如果邻接节点的入度变为0,则将其加入队列
if (indegrees[next][0] == 0) {
queue.addLast(next);
}
}
}
// 如果访问过的节点数量等于总节点数,说明可以进行拓扑排序,返回true
return count == n;
}
并查集
点击查看代码
class Union {
int n;// 节点数
int[] p;// 父节点数组,p[i]表示节点i的父节点
int[] s;// 当前分支大小数组,s[i]表示以节点i为根的集合的大小
int count;// 连通分量数,即当前有多少个独立的集合
//初始化
public Union(int n) {
//注意事项:节点从0开始
// 注意事项:节点从0开始
this.n = n; // 将传入的参数n赋值给类的成员变量n,表示集合的大小
p = new int[n]; // 创建一个长度为n的数组p,用于存储每个节点的父节点
s = new int[n]; // 创建一个长度为n的数组s,用于存储以当前节点为根的集合的大小
count = n; // 初始化连通分量的数量为n,即每个节点初始时都是一个独立的集合
for (int i = 0; i < n; i++) { // 遍历所有节点
p[i] = i; // 将节点i的父节点设置为其自身,表示每个节点初始时都是自己的父节点
s[i] = 1; // 将节点i所在集合的大小设置为1,因为每个节点初始时都是一个独立的集合
}
}
public int find(int x){
// 如果节点x的父节点是它自己,说明x就是根节点,直接返回x
if(x==p[x])
return x;
else{
// 如果节点x的父节点不是它自己,递归查找其父节点的根节点
p[x] = find(p[x]);
// 路径压缩,将x的父节点直接设置为找到的根节点,优化后续查找操作
return p[x];
}
}
public void union(int x,int y){
// 查找节点x的根节点
int rootX = find(x);
// 查找节点y的根节点
int rootY = find(y);
// 如果x和y的根节点相同,说明它们已经在同一个集合中,无需合并
if (rootX == rootY)
return;
// 如果x的根节点所在集合的大小大于y的根节点所在集合的大小
if (s[rootX] > s[rootY]) {
// 将y的根节点的父节点设置为x的根节点,实现合并
p[rootY] = rootX;
// 更新x的根节点所在集合的大小,加上y的根节点所在集合的大小
s[rootX] += s[rootY];
} else {
// 如果y的根节点所在集合的大小大于等于x的根节点所在集合的大小
// 将x的根节点的父节点设置为y的根节点,实现合并
p[rootX] = rootY;
// 更新y的根节点所在集合的大小,加上x的根节点所在集合的大小
s[rootY] += s[rootX];
}
// 合并后,连通分量的数量减1
count--;
}
// 获取最大分支节点个数
public int getMaxCount(){
int max=0; // 初始化最大分支节点个数为0
for(int i=0;i<n;i++){ // 遍历所有节点
max=Math.max(max,s[i]); // 更新最大分支节点个数,取当前最大值与节点i所在集合大小的较大值
}
return max; // 返回最大分支节点个数
}
// 获取连通分量个数
public int getCount(){
return count; // 直接返回连通分量个数
}
}
Flody算法
点击查看代码
/**
* 弗洛伊德算法:任意两点之间最短距离
*/
public void floyd() {
//对中间顶点遍历
for (int k = 0; k < dis.length; k++) {
//从i顶点开始出发
for (int i = 0; i < dis.length; i++) {
//到达j顶点
for (int j = 0; j < dis.length; j++) {
//求出从i顶点出发经过k到达j的距离
if(dis[i][k] + dis[k][j] < dis[i][j]) {
//更新距离
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}