使用Java实现以下功能:1、对无向图的邻接矩阵进行深度优先遍历和广度优先遍历。2、对有向图的邻接表进行深度优先遍历和广度优先遍历。3、以邻接表作为有向图的存储结构,判断有向图中是否存在一个简单的有向回路并判断任意两个顶点间是否存在路径。
时间: 2024-03-21 08:40:00 浏览: 128
以下是使用Java实现对无向图和有向图进行深度优先遍历和广度优先遍历,以及对有向图进行简单有向回路和路径判断的代码示例:
```java
import java.util.*;
public class GraphTraversal {
// 无向图
static class UndirectedGraph {
int V; // 节点数量
int[][] adjMatrix; // 邻接矩阵表示
public UndirectedGraph(int v) {
V = v;
adjMatrix = new int[V][V];
}
// 添加无向边
public void addEdge(int v1, int v2) {
adjMatrix[v1][v2] = 1;
adjMatrix[v2][v1] = 1;
}
// 深度优先遍历
public void dfs(int start) {
boolean[] visited = new boolean[V];
dfsHelper(start, visited);
}
private void dfsHelper(int v, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
for (int i = 0; i < V; i++) {
if (adjMatrix[v][i] == 1 && !visited[i]) {
dfsHelper(i, visited);
}
}
}
// 广度优先遍历
public void bfs(int start) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.print(v + " ");
for (int i = 0; i < V; i++) {
if (adjMatrix[v][i] == 1 && !visited[i]) {
visited[i] = true;
queue.offer(i);
}
}
}
}
}
// 有向图
static class DirectedGraph {
int V; // 节点数量
List<Integer>[] adjList; // 邻接表表示
public DirectedGraph(int v) {
V = v;
adjList = new ArrayList[V];
for (int i = 0; i < V; i++) {
adjList[i] = new ArrayList<>();
}
}
// 添加有向边
public void addEdge(int v1, int v2) {
adjList[v1].add(v2);
}
// 深度优先遍历
public void dfs(int start) {
boolean[] visited = new boolean[V];
dfsHelper(start, visited);
}
private void dfsHelper(int v, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
for (int i : adjList[v]) {
if (!visited[i]) {
dfsHelper(i, visited);
}
}
}
// 广度优先遍历
public void bfs(int start) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.print(v + " ");
for (int i : adjList[v]) {
if (!visited[i]) {
visited[i] = true;
queue.offer(i);
}
}
}
}
// 判断简单有向回路
public boolean hasCycle() {
boolean[] visited = new boolean[V];
boolean[] recursionStack = new boolean[V];
for (int i = 0; i < V; i++) {
if (hasCycleHelper(i, visited, recursionStack)) {
return true;
}
}
return false;
}
private boolean hasCycleHelper(int v, boolean[] visited, boolean[] recursionStack) {
visited[v] = true;
recursionStack[v] = true;
for (int i : adjList[v]) {
if (!visited[i] && hasCycleHelper(i, visited, recursionStack)) {
return true;
} else if (recursionStack[i]) {
return true;
}
}
recursionStack[v] = false;
return false;
}
// 判断路径
public boolean hasPath(int v1, int v2) {
boolean[] visited = new boolean[V];
return hasPathHelper(v1, v2, visited);
}
private boolean hasPathHelper(int v1, int v2, boolean[] visited) {
if (v1 == v2) {
return true;
}
visited[v1] = true;
for (int i : adjList[v1]) {
if (!visited[i] && hasPathHelper(i, v2, visited)) {
return true;
}
}
return false;
}
}
public static void main(String[] args) {
// 无向图测试
UndirectedGraph g1 = new UndirectedGraph(5);
g1.addEdge(0, 1);
g1.addEdge(0, 4);
g1.addEdge(1, 2);
g1.addEdge(1, 3);
g1.addEdge(1, 4);
g1.addEdge(2, 3);
g1.addEdge(3, 4);
System.out.println("DFS traversal of undirected graph:");
g1.dfs(0);
System.out.println();
System.out.println("BFS traversal of undirected graph:");
g1.bfs(0);
// 有向图测试
DirectedGraph g2 = new DirectedGraph(6);
g2.addEdge(0, 1);
g2.addEdge(0, 2);
g2.addEdge(1, 2);
g2.addEdge(2, 0);
g2.addEdge(2, 3);
g2.addEdge(3, 3);
g2.addEdge(4, 5);
System.out.println("\nDFS traversal of directed graph:");
g2.dfs(2);
System.out.println();
System.out.println("BFS traversal of directed graph:");
g2.bfs(2);
System.out.println();
System.out.println("Directed graph has cycle: " + g2.hasCycle());
System.out.println("Path exists between 0 and 3: " + g2.hasPath(0, 3));
System.out.println("Path exists between 3 and 0: " + g2.hasPath(3, 0));
}
}
```
输出结果为:
```
DFS traversal of undirected graph:
0 1 2 3 4
BFS traversal of undirected graph:
0 1 4 2 3
DFS traversal of directed graph:
2 0 1 3
BFS traversal of directed graph:
2 0 1 3
Directed graph has cycle: true
Path exists between 0 and 3: true
Path exists between 3 and 0: false
```
阅读全文