有向图 广度优先 java
时间: 2023-08-31 20:32:15 浏览: 35
### 回答1:
以下是 Java 语言实现有向图的广度优先遍历算法:
```java
import java.util.*;
public class Graph {
private int V; // 顶点数
private LinkedList<Integer>[] adj; // 邻接表
public Graph(int v) {
V = v;
adj = new LinkedList[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkedList<Integer>();
}
}
// 添加边
public void addEdge(int v, int w) {
adj[v].add(w);
}
// 广度优先遍历
public void BFS(int s) {
boolean[] visited = new boolean[V]; // 记录已访问的顶点
LinkedList<Integer> queue = new LinkedList<Integer>(); // 存储待访问的顶点
visited[s] = true;
queue.add(s);
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.print(v + " ");
Iterator<Integer> it = adj[v].listIterator();
while (it.hasNext()) {
int n = it.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String[] args) {
Graph g = new Graph(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
System.out.println("Following is Breadth First Traversal " + "(starting from vertex 0)");
g.BFS(0);
}
}
```
这里实现了一个 `Graph` 类,其中包括了添加边和 BFS 遍历方法。在 `main` 方法中创建了一个有向图,并从顶点 0 开始进行广度优先遍历。
### 回答2:
广度优先搜索(BFS)是一种常用的图搜索算法,用于在有向图中从给定的起始节点开始遍历,并逐步延伸到其相邻节点,直到遍历完所有可达节点为止。下面是一个用Java实现的有向图广度优先搜索算法示例:
```java
import java.util.LinkedList;
import java.util.Queue;
public class BreadthFirstSearch {
private int V; // 图中节点的个数
private LinkedList<Integer>[] adj; // 邻接表表示的有向图
public BreadthFirstSearch(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList<>();
}
}
// 添加节点的边
public void addEdge(int v, int w) {
adj[v].add(w);
}
// 广度优先搜索遍历
public void BFS(int s) {
boolean[] visited = new boolean[V]; // 用于记录节点是否被访问过
Queue<Integer> queue = new LinkedList<>(); // 用于队列操作
visited[s] = true;
queue.add(s);
while (!queue.isEmpty()) {
s = queue.poll();
System.out.print(s + " ");
for (int n : adj[s]) {
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String[] args) {
BreadthFirstSearch graph = new BreadthFirstSearch(4); // 创建一个有向图,节点个数为4
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
System.out.println("广度优先遍历结果为:");
graph.BFS(2); // 从节点2开始进行广度优先搜索
}
}
```
以上是一个简单的有向图广度优先搜索的Java实现。根据给定的起始节点,该算法将依次输出所有可达的节点,并按广度优先的顺序进行遍历。
### 回答3:
广度优先搜索(BFS)是一种图遍历算法,可以用于有向图。它通过逐层地遍历节点,首先访问起始节点的所有相邻节点,然后再访问这些相邻节点的相邻节点,以此类推,直到所有可达节点都被遍历。具体实现可以借助队列来实现。
在Java中,我们可以通过使用一个队列来实现广度优先搜索。首先创建一个队列,并将起始节点加入到队列中。然后开始循环,直到队列为空。在每一次循环中,取出队列的头部节点,并将其标记为已访问。然后访问该节点的所有相邻节点,将未访问的相邻节点加入到队列中。这样可以保证先访问起始节点的所有相邻节点,然后再逐层遍历其他节点。
下面是一个示例代码:
```java
import java.util.*;
public class BfsJava {
public void bfs(Graph graph, int startNode) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[graph.numNodes()];
queue.offer(startNode);
visited[startNode] = true;
while (!queue.isEmpty()) {
int currentNode = queue.poll();
System.out.println("Visiting node: " + currentNode);
List<Integer> neighbors = graph.getNeighbors(currentNode);
for (int neighbor : neighbors) {
if (!visited[neighbor]) {
queue.offer(neighbor);
visited[neighbor] = true;
}
}
}
}
public static void main(String[] args) {
Graph graph = new Graph(); // 构建图
int startNode = 0; // 起始节点
BfsJava bfs = new BfsJava();
bfs.bfs(graph, startNode);
}
}
```
在这个示例代码中,我们假设有一个Graph类来表示图,其中numNodes()方法返回图中节点的数量,getNeighbors(int node)方法返回给定节点的相邻节点列表。我们创建一个Graph对象,然后调用bfs方法,将起始节点和图作为参数传入。
这样就可以使用广度优先搜索来遍历有向图,以及找到起始节点的所有可达节点。