Graph Problems in Java

2025年3月29日 | 阅读 4 分钟

在计算机科学的众多学科中，其中一个最重要的就是图问题，它包括表示事物之间成对关系的。图是由节点或顶点以及它们之间的连接或边组成的。

这意味着，根据图中表示的关系性质，它可以是定向图或无向图。可以是有权图，其中每条边都有一定的成本；否则可以是无权图，其中每条边与其他边都一样。

图算法可用于解决许多问题，并可能涉及解决“路径”问题、开发节点之间的“连接”、确定“连通度”、检查是否存在“环形”路径和/或计算“最短路径”。

在本文中，我们将使用图的思想来解决不同的问题

问题：字符串能否组成一个环？

问题陈述：找出您是否可以将各种字符串链接在一起以创建圆。只有当一个字符串的最后一个字符与下一个字符串的首字符匹配时，一个字符串才能跟随另一个字符串。目标是确定整个字符串数组是否可以组织起来，以便最后一个字符串的最后一个字符与第一个字符串的第一个字符匹配，从而形成一个圆。

方法

该问题可以表示为图问题，其中

每个字符串是一个节点。
如果字符串 A 的最后一个字符与字符串 B 的第一个字符匹配，则存在从字符串 A 到字符串 B 的边。任务是检查此图是否可以形成欧拉回路，即

所有度数非零的顶点都已连接。
在有向图中，每个节点的入度等于出度。入度定义了多少个节点指向该节点，而出度定义了多少个节点被该节点指向。

算法

创建图：如果字符串可以作为实体连接在一起，则图的形状实际上是节点连接到一切，从两个字符的边到每个字符的边。
检查度数条件：确保每个顶点的入度与出度都相等。
验证图的连通性：通过查看是否有路径连接任何两个节点来检查图的连通性。如果存在这种情况，则链式过程的顶点应是强连通的。
结果：如果两个条件都满足，则字符串可以连接起来形成一个圆。

文件名: StringChainCircle.java

import java.util.*;
public class StringChainCircle {
    // Function to check if the given array of strings can be chained to form a circle
    public boolean canFormCircle(String[] strings) {
        // Number of vertices (26 for each alphabet letter)
        int numVertices = 26;
        // Arrays to track in-degree and out-degree of vertices
        int[] inDegree = new int[numVertices];
        int[] outDegree = new int[numVertices];
        // Create a graph to track edges between first and last characters
        List<List<Integer>> graph = new ArrayList<>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            graph.add(new ArrayList<>());
        }
        // Fill in-degree, out-degree and build the graph
        for (String str : strings) {
            int firstChar = str.charAt(0) - 'a';  
            int lastChar = str.charAt(str.length() - 1) - 'a';  
            outDegree[firstChar]++;  // Increment out-degree for firstChar
            inDegree[lastChar]++;    // Increment in-degree for lastChar
            graph.get(firstChar).add(lastChar);  // Add edge from firstChar to lastChar
        }
        // Check if all vertices with non-zero degrees are strongly connected
        if (!isStronglyConnected(graph, strings[0].charAt(0) - 'a', numVertices, outDegree)) {
            return false;
        }
        // Check if in-degree equals out-degree for each vertex
        for (int i = 0; i < numVertices; i++) {
            if (inDegree[i] != outDegree[i]) {
                return false;  // In-degree and out-degree do not match
            }
        }
        return true;  // The strings can be chained into a circle
    }
    private boolean isStronglyConnected(List<List<Integer>> graph, int startVertex, int numVertices, int[] outDegree) {
        // Perform DFS to check connectivity
        boolean[] visited = new boolean[numVertices];
        dfs(graph, startVertex, visited);
        // Check if all vertices with non-zero degrees are visited
        for (int i = 0; i < numVertices; i++) {
            if (outDegree[i] > 0 && !visited[i]) {
                return false;  // A vertex with outgoing edges is not reachable
            }
        }
        return true;
    }
    // Depth-First Search (DFS) to traverse the graph
    private void dfs(List<List<Integer>> graph, int vertex, boolean[] visited) {
        visited[vertex] = true;  // Mark the current vertex as visited
        // Recursively visit all adjacent vertices
        for (int adjVertex : graph.get(vertex)) {
            if (!visited[adjVertex]) {
                dfs(graph, adjVertex, visited);
            }
        }
    }
    // Main function to test the solution
    public static void main(String[] args) {
        StringChainCircle circleChecker = new StringChainCircle();
        String[] strings1 = {"abc", "cde", "efg", "gha"};
        System.out.println(circleChecker.canFormCircle(strings1));  // Output: true
        String[] strings2 = {"abc", "cda", "bca"};
        System.out.println(circleChecker.canFormCircle(strings2));  // Output: false
    }
}   

输出

 
true
false

下一主题Java中的虚拟函数

Graph Problems in Java

问题：字符串能否组成一个环？

方法

算法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Graph Problems in Java

问题：字符串能否组成一个环？

方法

算法

相关帖子

Java 中 & 运算符是什么

Sylvester's Sequence in Java

Java 中个位数是 K 的数字之和

Java 中的常量列表

Circular Tour Problem in Java

CharsetEncoder replacement() Method in Java with Examples

String Pool in Java

Find Primitive Root of a Prime Number Modulo n in Java

Java 泛型队列

Java 中的无法访问代码错误

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器