用java编写程序输入优先图的邻接矩阵来判断它是否是简单有向图。输出每个顶点的输入和输出度数。使用两种方式输入数据,一种方式来自控制台,另一种方式来自CSV文件。
时间: 2024-05-12 12:20:56 浏览: 68
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路
5星 · 资源好评率100%
以下是Java代码实现:
```
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
public class SimpleDirectedGraph {
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of vertices: ");
int n = scanner.nextInt();
int[][] graph = new int[n][n];
System.out.println("Enter the adjacency matrix:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = scanner.nextInt();
}
}
scanner.close();
checkSimpleDirectedGraph(graph);
}
public static void checkSimpleDirectedGraph(int[][] graph) {
int n = graph.length;
boolean isSimpleDirectedGraph = true;
int[] inDegrees = new int[n];
int[] outDegrees = new int[n];
for (int i = 0; i < n; i++) {
int inDegree = 0;
int outDegree = 0;
for (int j = 0; j < n; j++) {
if (graph[i][j] == 1) {
outDegree++;
inDegrees[j]++;
if (inDegrees[j] > 1) {
isSimpleDirectedGraph = false;
}
}
if (graph[j][i] == 1) {
inDegree++;
outDegrees[j]++;
if (outDegrees[j] > 1) {
isSimpleDirectedGraph = false;
}
}
}
System.out.println("Vertex " + (i + 1) + ": in-degree = " + inDegree + ", out-degree = " + outDegree);
}
if (isSimpleDirectedGraph) {
System.out.println("The graph is a simple directed graph.");
} else {
System.out.println("The graph is not a simple directed graph.");
}
}
public static void checkSimpleDirectedGraphFromFile(String filename) throws IOException {
BufferedReader reader = new BufferedReader(new FileReader(filename));
int n = Integer.parseInt(reader.readLine());
int[][] graph = new int[n][n];
for (int i = 0; i < n; i++) {
String[] row = reader.readLine().split(",");
for (int j = 0; j < n; j++) {
graph[i][j] = Integer.parseInt(row[j]);
}
}
reader.close();
checkSimpleDirectedGraph(graph);
}
}
```
首先,我们定义了一个`checkSimpleDirectedGraph`方法来检查一个给定的邻接矩阵是否是简单有向图,并输出每个顶点的输入和输出度数。该方法接受一个二维整数数组作为输入,表示邻接矩阵。我们通过遍历矩阵中的每个元素来计算每个顶点的输入和输出度数,同时记录每个顶点的入度和出度。如果一个顶点的入度或出度大于1,则该图不是简单有向图。最后,我们在控制台输出每个顶点的输入和输出度数,并根据图是否是简单有向图输出相应的结果。
然后,我们定义了一个`checkSimpleDirectedGraphFromFile`方法来从CSV文件中读取邻接矩阵并检查它是否是简单有向图。该方法接受一个字符串参数作为输入,表示CSV文件的路径。我们使用`BufferedReader`类从文件中读取邻接矩阵,然后调用`checkSimpleDirectedGraph`方法来检查它是否是简单有向图。
最后,在`main`方法中,我们使用两种方式输入数据。首先,我们从控制台读取邻接矩阵并调用`checkSimpleDirectedGraph`方法来检查它是否是简单有向图。然后,我们从CSV文件中读取邻接矩阵并调用`checkSimpleDirectedGraphFromFile`方法来检查它是否是简单有向图。
阅读全文