Java强连通分量(含面试大厂题和源码)

强连通分量（Strongly Connected Components, SCCs）是图论中的一个概念，主要用于有向图。在有向图中，如果从图中的某个顶点 A 能够到达另一个顶点 B，并且从顶点 B 也能到达顶点 A，则称这两个顶点是强连通的。一个强连通分量是这样一个子图，其内部任意两个顶点都是强连通的。

强连通分量的算法：

  1. Kosaraju 算法：这是一个经典的算法，它首先对原图进行深度优先搜索（DFS），记录顶点的完成顺序，并建立一个逆序的顶点栈。然后，对原图的逆图（即边的方向全部反转）再次进行 DFS，每次 DFS 会找到原图中的一个强连通分量。

  2. Tarjan 算法：Tarjan 算法也是一种用于寻找强连通分量的算法，它在同一个图中完成寻找过程，不需要构建逆图。Tarjan 算法在 DFS 的过程中为每个顶点分配三个值：发现时间戳（disc）、最低可达时间戳（low），以及一个标记用来判断顶点是否在栈上。

强连通分量的 Java 实现（Kosaraju 算法）：

import java.util.*;

public class StronglyConnectedComponents {
    private int time;
    private List<List<Integer>> adjList;
    private Stack<Integer> postOrder;
    private List<List<Integer>> sccList;

    public List<List<Integer>> getSCCs(int n, List<List<Integer>> edges) {
        adjList = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }
        postOrder = new Stack<>();
        sccList = new ArrayList<>();
        time = 0;

        // Build the adjacency list and perform DFS on the original graph
        for (List<Integer> edge : edges) {
            adjList.get(edge.get(0)).add(edge.get(1));
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }

        // Create the transpose of the graph
        List<List<Integer>> transpose = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            transpose.add(new ArrayList<>());
        }
        for (List<Integer> edge : edges) {
            transpose.get(edge.get(1)).add(edge.get(0));
        }

        // Perform DFS on the transpose graph
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfsOnTranspose(transpose, i);
            }
        }

        return sccList;
    }

    private void dfs(int v) {
        visited[v] = true;
        for (int neighbor : adjList.get(v)) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
        postOrder.push(v);
    }

    private void dfsOnTranspose(List<List<Integer>> transpose, int v) {
        visited[v] = true;
        sccList.add(v);
        for (int neighbor : transpose.get(v)) {
            if (!visited[neighbor]) {
                dfsOnTranspose(transpose, neighbor);
            }
        }
    }

    // Helper method to initialize visited array and call getSCCs
    public List<List<Integer>> scc(int n, List<List<Integer>> edges) {
        boolean[] visited = new boolean[n];
        getSCCs(n, edges);
        return sccList;
    }

    public static void main(String[] args) {
        StronglyConnectedComponents scc = new StronglyConnectedComponents();
        int n = 5;
        List<List<Integer>> edges = Arrays.asList(
            Arrays.asList(1, 0),
            Arrays.asList(0, 2),
            Arrays.asList(2, 1),
            Arrays.asList(0, 3),
            Arrays.asList(3, 4)
        );
        List<List<Integer>> result = scc.scc(n, edges);
        System.out.println("Strongly Connected Components: " + result);
    }
}

在面试中，强连通分量是一个重要的图算法问题，它考察应聘者对图算法的理解和算法实现能力。通过实现强连通分量的算法，可以展示你对深度优先搜索和图算法的掌握程度。希望这些知识点和示例代码能够帮助你更好地准备面试！强连通分量（SCC）是图算法中的一个高级话题，经常出现在大厂的面试中。以下是三道与强连通分量相关的面试题目，以及相应的Java源码实现。

题目 1：社交网络中的社交圈子

描述：
在社交网络中，如果两个人是朋友，那么他们之间是双向关注的。给定社交网络中的关注关系，找出所有的社交圈子。

示例：

输入：社交网络关系图的邻接表表示，例如：
{
  1: [2],
  2: [1, 3],
  3: [2],
  4: [5],
  5: [4]
}
输出：[[1, 2, 3], [4, 5]]

Java 源码（使用Kosaraju算法）：

import java.util.*;

public class SocialCircles {
    List<List<Integer>> sccList;
    int time;
    Stack<Integer> postOrder;
    Map<Integer, List<Integer>> graph;

    public List<List<Integer>> findCircles(int n, Map<Integer, List<Integer>> graph) {
        this.graph = new HashMap<>(graph);
        sccList = new ArrayList<>();
        time = 0;
        postOrder = new Stack<>();
        boolean[] visited = new boolean[n];

        // DFS on original graph
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, visited);
            }
        }

        // Create transpose of the graph
        Map<Integer, List<Integer>> transpose = new HashMap<>();
        for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
            for (int neighbor : entry.getValue()) {
                if (!transpose.containsKey(neighbor)) {
                    transpose.put(neighbor, new ArrayList<>());
                }
                transpose.get(neighbor).add(entry.getKey());
            }
        }

        // DFS on transpose graph
        visited = new boolean[n];
        while (!postOrder.isEmpty()) {
            int node = postOrder.pop();
            if (!visited[node]) {
                dfsOnTranspose(transpose, node, visited, new ArrayList<>());
                sccList.add(visitedSubgraph);
            }
        }
        return sccList;
    }

    private void dfs(int node, boolean[] visited) {
        visited[node] = true;
        for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited);
            }
        }
        postOrder.push(node);
    }

    private void dfsOnTranspose(Map<Integer, List<Integer>> transpose, int node, boolean[] visited, List<Integer> visitedSubgraph) {
        visited[node] = true;
        visitedSubgraph.add(node);
        for (int neighbor : transpose.getOrDefault(node, Collections.emptyList())) {
            if (!visited[neighbor]) {
                dfsOnTranspose(transpose, neighbor, visited, visitedSubgraph);
            }
        }
    }

    public static void main(String[] args) {
        SocialCircles solution = new SocialCircles();
        int n = 5;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Collections.singletonList(2));
        graph.put(2, Arrays.asList(1, 3));
        graph.put(3, Collections.singletonList(2));
        graph.put(4, Collections.singletonList(5));
        graph.put(5, Collections.singletonList(4));

        List<List<Integer>> result = solution.findCircles(n, graph);
        System.out.println("Social circles: " + result);
    }
}

题目 2：课程的先决条件

描述：
给定 n 门课程和一个先决条件列表，请你检查是否存在课程之间的循环依赖，如果存在则返回 true；否则，返回 false。

示例：

输入：n = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
输出：false

Java 源码：

import java.util.*;

public class CoursePrerequisites {
    public boolean hasCycle(int n, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[n];
        
        // Build the graph and calculate in-degrees
        for (int[] edge : prerequisites) {
            graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
            inDegree[edge[0]]++;
        }
        
        // Use a queue to perform BFS on the graph
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int visitedCount = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int course = queue.poll();
                visitedCount++;
                for (int prereq : graph.get(course)) {
                    if (--inDegree[prereq] == 0) {
                        queue.offer(prereq);
                    }
                }
            }
        }
        
        return visitedCount != n;
    }

    public static void main(String[] args) {
        CoursePrerequisites solution = new CoursePrerequisites();
        int n = 4;
        int[][] prerequisites = {{1, 0}, [2, 0], [3, 1], [3, 2]};

        boolean result = solution.hasCycle(n, prerequisites);
        System.out.println("Does the course have a cycle of prerequisites? " + result);
    }
}

题目 3：构建离线图

描述：
给定一个包含 n 个顶点和 m 个边的有向图，边具有权重。设计一个算法，根据给定的边权重，构建一个离线图，使得在离线图中，任意两个强连通分量之间的边的权重之和最小。

示例：

输入：n = 4, edges = [[1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 1, 6]]
输出：最小权重和

Java 源码：

import java.util.*;

public class OfflineGraph {
    public int buildOfflineGraph(int n, int[][] edges) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        int[] inDegree = new int[n];
        int totalWeight = 0;
        
        // Build the graph and calculate in-degrees
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(new int[]{edge[0], edge[2]});
            inDegree[edge[0]]++;
            totalWeight += edge[2];
        }
        
        // Use a queue to perform BFS on the graph
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int vertex = queue.poll();
                for (int[] edge : graph.get(vertex)) {
                    if (--inDegree[edge[0]] == 0) {
                        queue.offer(edge[0]);
                    }
                }
            }
        }
        
        // Calculate the remaining weight considering SCCs
        // (This part requires a more complex algorithm and is not fully implemented here)
        // ...

        return totalWeight; // Placeholder for the minimum weight sum
    }

    public static void main(String[] args) {
        OfflineGraph solution = new OfflineGraph();
        int n = 4;
        int[][] edges = {{1, 2, 3}, [2, 3, 4}, [3, 4, 5}, [4, 1, 6]];

        int result = solution.buildOfflineGraph(n, edges);
        System.out.println("Minimum weight sum of the offline graph: " + result);
    }
}

这些题目和源码展示了强连通分量在图算法中的应用。在面试中，能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/555405.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

文件IO基础

文件IO基础

一、文件描述符 调用 open 函数会有一个返回值&#xff0c;该返回值就是一个文件描述符&#xff08; file descriptor&#xff09;&#xff0c;这说明文件描述符是一个 非负整数&#xff1b;对于 Linux 内核而言&#xff0c;所有打开的文件都会通过文件描述符进行索引。 当调用…
阅读更多...
2024年第十六届“华中杯”（B题）大学生数学建模挑战赛| 时间序列，滑动窗口 | 数学建模完整代码+建模过程全解全析

2024年第十六届“华中杯”（B题）大学生数学建模挑战赛| 时间序列，滑动窗口 | 数学建模完整代码+建模过程全解全析

当大家面临着复杂的数学建模问题时&#xff0c;你是否曾经感到茫然无措&#xff1f;作为2022年美国大学生数学建模比赛的O奖得主&#xff0c;我为大家提供了一套优秀的解题思路&#xff0c;让你轻松应对各种难题。 让我们来看看华中杯 (B题&#xff09;&#xff01; CS团队倾…
阅读更多...
《四月女友》定档5月18日 佐藤健、长泽雅美演绎唯美爱情

《四月女友》定档5月18日 佐藤健、长泽雅美演绎唯美爱情

由川村元气担任编剧&#xff0c;山田智和导演&#xff0c;佐藤健、长泽雅美、森七菜主演的唯美爱情电影《四月女友》今日正式宣布定档5月18日&#xff0c;并发布了“相恋”版预告和“相拥”版海报。预告中&#xff0c;优美宁静的风景令人心生向往&#xff0c;藤代俊&#xff08…
阅读更多...
【深度学习实战（8）】如何绘制loss曲线图

【深度学习实战（8）】如何绘制loss曲线图

一、步骤 我们先定义一个dict&#xff0c;每一个key对应的value都是一个list。 loss_history dict((k, []) for k in ["epoch", "train_loss", "val_loss"])每一轮或者每一次迭代的损失都通过list记录下来。 loss_history["epoch"…
阅读更多...
改手机IP地址的软件推荐

改手机IP地址的软件推荐

随着移动互联网的普及&#xff0c;手机已成为人们日常生活中不可或缺的一部分。而在使用手机的过程中&#xff0c;IP地址作为一个重要的网络标识&#xff0c;有时也需要进行修改或更改。为了满足这一需求&#xff0c;市面上涌现出了许多改手机IP地址的软件。虎观代理将对这些软…
阅读更多...
2024年腾讯云服务器价格一览表

2024年腾讯云服务器价格一览表

随着云计算技术的快速发展&#xff0c;越来越多的企业和个人开始选择使用云服务器来满足他们的数据存储和计算需求。腾讯云作为国内领先的云服务提供商&#xff0c;其服务器产品因性能稳定、安全可靠而备受用户青睐。那么&#xff0c;2024年腾讯云服务器的价格情况如何呢&#…
阅读更多...
Flattened Butterfly 扁平蝶形拓扑

Flattened Butterfly 扁平蝶形拓扑

Flattened Butterfly 扁平蝶形拓扑 1. 传统蝶形网络 Butterfly Topology2. 扁平蝶形拓扑 Flattened Butterfly3.On-Chip Flattened Butterfly 扁平蝶形拓扑应用于片上网络 Flattened Butterfly 扁平蝶形拓扑 扁平蝶形拓扑是一种经济高效的拓扑&#xff0c;适用于高基数路由器…
阅读更多...
复合升降机器人教学科研平台——技术方案

复合升降机器人教学科研平台——技术方案

一&#xff1a;功能概述 1.1 功能简介 复合升降机器人是一款集成移动底盘、机械臂、末端执行器、边缘计算平台等机构形成的教学科研平台&#xff0c;可实现机器人建图导航、路径规划&#xff0c;机械臂运动学、动力学、轨迹规划、视觉识别等算法功能和应用&#xff0c;提供例如…
阅读更多...
前后端交互实例(javaweb05)

前后端交互实例(javaweb05)

文章开始前,先给大家看一张图,这是黑马javaweb-day05请求响应实例,也是第一个实现了前后端交互,这是我画的流程图,搞懂了前后端是如何交互的.(文件的所有路径不能出现中文,否则会报错,这个我暂时不知道该怎么解决). 那么这里面涉及到的东西,除了emp.html这是已经提供了的前端页…
阅读更多...
C++：深入理解operator new/operator delete

C++：深入理解operator new/operator delete

动态内存管理 1.语法层面1.基本语法注意点 2.new/delete和malloc/free的区别3.operator new和operator delete函数&#xff08;底层重点&#xff09;1.operator new/delete原理2.图解1.new/new[]2.delete/delete[] 3.new[n]和delete[] 4.定位new1.定义2.使用格式 1.语法层面 1…
阅读更多...
【前端面试3+1】13 JS特性、JS是单线程还是多线程、JS中的一部和同步、【合并两个有序数组】

【前端面试3+1】13 JS特性、JS是单线程还是多线程、JS中的一部和同步、【合并两个有序数组】

一、JavaScript特性 弱类型&#xff1a;JavaScript是一种弱类型语言&#xff0c;变量的类型可以动态改变&#xff0c;不需要事先声明类型。动态性&#xff1a;JavaScript是一种动态语言&#xff0c;可以在运行时修改对象的结构和属性。基于原型的&#xff1a;JavaScript是一种基…
阅读更多...
WdatePicker异常，无法弹出日期选择框

WdatePicker异常，无法弹出日期选择框

官网&#xff1a;My97日期控件官方网站 My97 DatePickerhttp://www.my97.net/ 可能使版本太老了&#xff0c;可以更新一下&#xff0c;然后根据官方的文件进行使用。 我的异常是因为在网上找的包里面缺少文件&#xff0c;去官网拉了一下最新的就行了。
阅读更多...
状态压缩DP题单

状态压缩DP题单

P1433 吃奶酪&#xff08;最短路&#xff09; dp(i, s) 表示从 i 出发经过的点的记录为 s 的路线距离最小值 #include<bits/stdc.h> #define int long long using namespace std; const int N 20; signed main() { int n; cin >> n;vector<double>x(n 1),…
阅读更多...
FreeRTOS之动态创建任务与删除任务

FreeRTOS之动态创建任务与删除任务

1.本文是利用FreeRTOS来动态创建任务和删除任务。主要是使用FreeRTOS的两个API函数&#xff1a;xTaskCreate()和vTaskDelete()。 任务1和任务2是让LED0、LED1闪烁。任务3是当按键按下时删除任务1。 使用动态创建任务时&#xff0c;需要动态的堆中申请任务所需的内存空间&…
阅读更多...
OpenHarmony多媒体-ohos_videocompressor

OpenHarmony多媒体-ohos_videocompressor

介绍 videoCompressor是一款ohos高性能视频压缩器。 目前实现的能力&#xff1a; 支持视频压缩 使用本工程 有两种方式可以下载本工程&#xff1a; 开发者如果想要使用本工程,可以使用git命令 git clone https://gitee.com/openharmony-sig/ohos_videocompressor.git --…
阅读更多...
Redis学习记录

Redis学习记录

Redis安装 首先是Redis的下载地址&#xff0c;事实上&#xff0c;Redis已经出到7的版本了&#xff0c;我们这里使用的是5的版本。&#xff08;3也能用&#xff09; Redis下载地址 我们将Redis下载下来并解压&#xff1a; 我们如何启动呢? redis-server.exe redis.windows.…
阅读更多...
单分支：if语句

单分支：if语句

示例&#xff1a; /*** brief how about if? show you here.* author wenxuanpei* email 15873152445163.com(query for any question here)*/ #define _CRT_SECURE_NO_WARNINGS//support c-library in Microsoft-Visual-Studio #include <stdio.h>#define if_state…
阅读更多...
学习笔记------约束的管理

学习笔记------约束的管理

此篇记录FPGA的静态时序分析&#xff0c;在学习FPGA的过程中&#xff0c;越发觉得对于时序约束只是懂了个皮毛。现在记录一下自己的学习过程。 本文摘自《VIVADO从此开始》高亚军 为什么要进行约束&#xff1f;约束的目的是什么&#xff1f; 简单来说&#xff0c;就是需要在…
阅读更多...
Unity（MVC思想）

Unity（MVC思想）

MVC 一下演示使用MVC和不使用MVC的做法区别。 前两个没有使用MVC 主面板逻辑&#xff1a; mainPanel是该脚本名字 每个场景中不一定存在该面板&#xff0c;单纯的显隐需要去手动挂载过于麻烦。 所以自己读取创建面板出来(每个场景仅创建一次)&#xff0c;存下该面板&#xf…
阅读更多...
OpenHarmony网络请求库-httpclient

OpenHarmony网络请求库-httpclient

简介 HTTP是现代应用程序通过网络交换数据和媒体的的主要方式。httpclient是OpenHarmony 里一个高效执行的HTTP客户端&#xff0c;使用它可使您的内容加载更快&#xff0c;并节省您的流量。httpclient以人们耳熟能详的OKHTTP为基础&#xff0c;整合android-async-http&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站