利用二维数组、Map或Graph类存储有向图,并完成如下操作: 输入:图的任意一个节点编号; 输出:该节点的入度、出度、入度边邻居和出度边邻居的编号。
时间: 2024-03-11 17:48:12 浏览: 118
好的,可以使用 Map 类来存储有向图。假设节点编号为整数类型。
首先,定义一个 Map 对象 graph 用来存储有向图。Map 的 key 是节点编号,value 是一个 List,存储该节点的出度边邻居的编号。
```
Map<Integer, List<Integer>> graph = new HashMap<>();
```
然后,对于每个节点,我们需要将它的出度边邻居添加到对应的 List 中。假设有一个节点类 Node,其中包含一个 List<Integer> outNeighbours,存储该节点的出度边邻居的编号。
```
class Node {
List<Integer> outNeighbours;
// ...
}
```
我们可以按照如下方式将节点加入到图中:
```
Node node = ...; // 初始化节点
graph.put(node.id, node.outNeighbours);
```
接下来,我们可以根据输入的节点编号来获取该节点的入度、出度、入度边邻居和出度边邻居的编号。假设输入的节点编号为 nodeId。
首先,我们可以通过 graph.get(nodeId) 来获取该节点的出度边邻居的编号。然后,遍历整个图,统计每个节点的入度,即出现在其他节点出度边邻居中的次数。同时,我们可以记录每个节点的入度边邻居的编号。
```
int outDegree = graph.get(nodeId).size();
int inDegree = 0;
List<Integer> inNeighbours = new ArrayList<>();
Map<Integer, List<Integer>> revGraph = new HashMap<>(); // 存储反向图
for (int u : graph.keySet()) {
if (u == nodeId) {
continue;
}
for (int v : graph.get(u)) {
if (v == nodeId) {
inDegree++;
inNeighbours.add(u); // 记录入度边邻居的编号
// 添加反向边
if (!revGraph.containsKey(nodeId)) {
revGraph.put(nodeId, new ArrayList<>());
}
revGraph.get(nodeId).add(u);
}
}
}
```
最后,我们可以通过 revGraph.get(nodeId) 来获取该节点的入度边邻居的编号。
完整代码如下:
阅读全文