利用二维数组、Map或Graph类存储有向图,并完成如下操作: 输入:图的任意一个节点编号; 输出:该节点的入度、出度、入度边邻居和出度边邻居的编号。
时间: 2024-03-11 16:48:13 浏览: 102
好的,以下是一个用 Java 实现的示例代码:
```
import java.util.*;
public class DirectedGraph {
private Map<Integer, List<Integer>> graph; // 存储有向图
private Map<Integer, List<Integer>> revGraph; // 存储反向图
public DirectedGraph(int[][] edges) {
graph = new HashMap<>();
revGraph = new HashMap<>();
// 初始化有向图和反向图
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
if (!graph.containsKey(u)) {
graph.put(u, new ArrayList<>());
}
graph.get(u).add(v);
if (!revGraph.containsKey(v)) {
revGraph.put(v, new ArrayList<>());
}
revGraph.get(v).add(u);
}
}
public void printNodeInfo(int nodeId) {
int outDegree = graph.containsKey(nodeId) ? graph.get(nodeId).size() : 0;
int inDegree = 0;
List<Integer> inNeighbours = new ArrayList<>();
List<Integer> outNeighbours = graph.getOrDefault(nodeId, new ArrayList<>());
// 统计入度和入度边邻居
for (int u : revGraph.keySet()) {
for (int v : revGraph.get(u)) {
if (v == nodeId) {
inDegree++;
inNeighbours.add(u);
}
}
}
System.out.println("节点 " + nodeId + " 的信息:");
System.out.println("出度:" + outDegree);
System.out.println("入度:" + inDegree);
System.out.println("出度边邻居:" + outNeighbours);
System.out.println("入度边邻居:" + inNeighbours);
}
public static void main(String[] args) {
int[][] edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}, {4, 1}};
DirectedGraph graph = new DirectedGraph(edges);
graph.printNodeInfo(1);
graph.printNodeInfo(2);
graph.printNodeInfo(3);
graph.printNodeInfo(4);
}
}
```
我们定义了一个 DirectedGraph 类来存储有向图,并提供了一个 printNodeInfo 方法来输出指定节点的信息。在构造方法中,我们通过 edges 数组初始化有向图和反向图。在 printNodeInfo 方法中,我们首先获取该节点的出度边邻居,然后遍历反向图来统计该节点的入度和入度边邻居。最后,我们输出节点的信息。
在 main 方法中,我们使用一个示例图来测试我们的代码。输出如下:
```
节点 1 的信息:
出度:2
入度:1
出度边邻居:[2, 3]
入度边邻居:[4]
节点 2 的信息:
出度:2
入度:2
出度边邻居:[3, 4]
入度边邻居:[1, 3]
节点 3 的信息:
出度:1
入度:2
出度边邻居:[4]
入度边邻居:[1, 2]
节点 4 的信息:
出度:1
入度:3
出度边邻居:[1]
入度边邻居:[2, 3]
```
阅读全文