Java 环 无向图

Java环无向图可以看作是一个没有重复边和自环的简单无向图，它的特点是存在一个环包围了整个图。在Java编程中，我们可以用邻接表或邻接矩阵来表示Java环无向图，其中邻接表是一种链式存储结构，用于存储Java环无向图中的每个节点以及它们之间的边信息；邻接矩阵则是一个二维数组，用于表示Java环无向图中节点之间的连接关系。

在Java环无向图中，我们可以使用深度优先搜索或广度优先搜索等算法来遍历图中的节点。对于Java环无向图而言，我们可以使用DFS算法来判断它是否存在环路。如果在遍历图的过程中遇到了一个已经访问过的节点，同时这个节点又不是当前节点的父节点，那么就说明这个图中存在环路。

相关问题

java遍历有向图_循环有向图的遍历

循环有向图的遍历可以使用拓扑排序来实现。拓扑排序是一种对有向无环图进行排序的算法，它将图中所有顶点排成一个线性序列，使得图中任意一条有向边的起点在序列中都排在终点的前面。

具体实现步骤如下：

1. 统计每个节点的入度，即有多少个节点指向该节点。
2. 将所有入度为 0 的节点加入队列。
3. 取出队首节点，将其加入结果集中，并将其所有指向的节点的入度减 1。
4. 如果某个节点的入度减为 0，则将该节点加入队列。
5. 重复步骤 3 和步骤 4，直到队列为空。

在遍历过程中，如果遇到了环，则说明该图不是有向无环图，无法进行拓扑排序。

下面是 Java 代码实现：

import java.util.*;

public class TopologicalSort {
    public List<Integer> sort(int[][] graph) {
        int n = graph.length;
        int[] inDegree = new int[n];
        List<Integer> result = new ArrayList<>();

        // 统计入度
        for (int[] edge : graph) {
            inDegree[edge[1]]++;
        }

        // 将入度为 0 的节点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 拓扑排序
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            for (int[] edge : graph) {
                if (edge[0] == node) {
                    inDegree[edge[1]]--;
                    if (inDegree[edge[1]] == 0) {
                        queue.offer(edge[1]);
                    }
                }
            }
        }

        // 如果存在环，则返回空列表
        if (result.size() != n) {
            return new ArrayList<>();
        } else {
            return result;
        }
    }
}

按时间加权 有向图 关键路径 java 代码

为了计算一个按时间加权有向图的关键路径，可以使用 Java 语言来实现 DAG（有向无环图）算法。

以下是示例代码：

import java.util.*;

public class DAG {
    private int V; 
    private LinkedList<Integer> adj[]; 
    private int[] indegree; 

    DAG(int v) { 
        V = v; 
        adj = new LinkedList[v]; 
        indegree = new int[V]; 
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList(); 
            indegree[i] = 0; 
        }
    } 

    void addEdge(int v, int w) { 
        adj[v].add(w); 
        indegree[w]++; 
    } 

    void topologicalSort() { 
        Stack<Integer> stack = new Stack<>(); 
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MIN_VALUE);
        dist[0] = 0;

        for (int i = 0; i < V; i++) 
            if (indegree[i] == 0) 
                stack.push(i); 

        while (!stack.isEmpty()) { 
            int u = stack.pop(); 

            for (int i = 0; i < adj[u].size(); i++) { 
                int v = adj[u].get(i); 
                if (dist[u] + 1 > dist[v])
                    dist[v] = dist[u] + 1;
                if (--indegree[v] == 0) 
                    stack.push(v); 
            } 
        }

        System.out.println("The length of the critical path is " + dist[V-1]);
    } 

    public static void main(String args[]) { 
        DAG dag = new DAG(6); 
        dag.addEdge(0, 1); 
        dag.addEdge(0, 2); 
        dag.addEdge(1, 3); 
        dag.addEdge(2, 3); 
        dag.addEdge(3, 4);
        dag.addEdge(3, 5);

        dag.topologicalSort(); 
    } 
}

这段代码通过入度和拓扑排序的方式计算了关键路径的长度。在这个示例中，我们有一个图（0，1，2，3，4，5）和一些有向边。

输出为： The length of the critical path is 3

意思是从顶点 0 到顶点 5 的关键路径长度是 3。