使用Java程序设计语言,编程计算图中结点的度数,并设计相应的图作为测试用例,进行功能测试。
时间: 2024-09-12 13:02:51 浏览: 44
图中结点的度数指的是与该结点相连的边的数量。在无向图中,度数是与该结点直接相连的其他结点的数量;在有向图中,度数分为入度(有向边指向该结点的数量)和出度(从该结点指向其他结点的数量)。
为了计算图中结点的度数,我们可以使用邻接表或邻接矩阵来表示图。以下是使用邻接表表示无向图,并用Java程序设计语言编写计算结点度数的功能代码示例:
```java
import java.util.ArrayList;
import java.util.List;
// 图的表示
class Graph {
// 使用邻接表表示图
private List<List<Integer>> adjList;
public Graph(int numVertices) {
adjList = new ArrayList<>(numVertices);
for (int i = 0; i < numVertices; i++) {
adjList.add(new ArrayList<>());
}
}
// 添加边
public void addEdge(int src, int dest) {
adjList.get(src).add(dest);
adjList.get(dest).add(src); // 无向图需要添加两次
}
// 计算所有结点的度数
public int[] getDegrees() {
int[] degrees = new int[adjList.size()];
for (int i = 0; i < adjList.size(); i++) {
degrees[i] = adjList.get(i).size();
}
return degrees;
}
}
public class GraphDemo {
public static void main(String[] args) {
// 创建一个图实例,有4个结点
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
// 计算并打印结点的度数
int[] degrees = g.getDegrees();
for (int i = 0; i < degrees.length; i++) {
System.out.println("结点 " + i + " 的度数是: " + degrees[i]);
}
}
}
```
在上面的代码中,`Graph` 类使用邻接表来表示图,并提供了添加边和计算度数的方法。`addEdge` 方法添加了一条无向边,并同时更新了两个结点的邻接列表。`getDegrees` 方法计算并返回了一个包含所有结点度数的数组。
对于有向图,只需要在添加边的时候区分源结点和目标结点,并且在计算度数时分别计算入度和出度即可。
测试用例应该包含不同类型的图,比如没有边的图、有环的图、有多个连通分量的图等,以确保程序能够正确处理各种情况。
阅读全文