用java语言分别基于图的邻接矩阵存储结构和邻接表存储结构,编程求一个有向图G的指定顶点的入度和出度。即,输入一个有向图G,和它的一个顶点,输出这个顶点的入度和出度。
时间: 2024-03-23 16:38:12 浏览: 70
好的,这里提供基于Java语言的代码,分别使用邻接矩阵和邻接表存储结构实现求有向图G的指定顶点的入度和出度。
1. 邻接矩阵存储结构
```java
public class Graph {
private int[][] adjMatrix; // 邻接矩阵
private int vertexNum; // 顶点数
public Graph(int vertexNum) {
this.vertexNum = vertexNum;
adjMatrix = new int[vertexNum][vertexNum];
}
// 添加边
public void addEdge(int v1, int v2) {
adjMatrix[v1][v2] = 1;
}
// 获取指定顶点的出度和入度
public void getDegree(int v) {
int inDegree = 0;
int outDegree = 0;
for (int i = 0; i < vertexNum; i++) {
if (adjMatrix[v][i] == 1) { // 统计出度
outDegree++;
}
if (adjMatrix[i][v] == 1) { // 统计入度
inDegree++;
}
}
System.out.println("Vertex " + v + " has an in-degree of " + inDegree + " and an out-degree of " + outDegree);
}
}
```
2. 邻接表存储结构
```java
import java.util.ArrayList;
import java.util.List;
public class Graph {
private List<List<Integer>> adjList; // 邻接表
private int vertexNum; // 顶点数
public Graph(int vertexNum) {
this.vertexNum = vertexNum;
adjList = new ArrayList<>();
for (int i = 0; i < vertexNum; i++) {
adjList.add(new ArrayList<>());
}
}
// 添加边
public void addEdge(int v1, int v2) {
adjList.get(v1).add(v2);
}
// 获取指定顶点的出度和入度
public void getDegree(int v) {
int inDegree = 0;
int outDegree = 0;
for (int i = 0; i < vertexNum; i++) {
List<Integer> neighbors = adjList.get(i);
for (int neighbor : neighbors) {
if (neighbor == v) { // 统计入度
inDegree++;
}
}
if (i == v) { // 统计出度
outDegree = neighbors.size();
}
}
System.out.println("Vertex " + v + " has an in-degree of " + inDegree + " and an out-degree of " + outDegree);
}
}
```
希望能够帮助到您。
阅读全文