gpt-3.5-turbo-0613· OpenAI
WildChat-4.8M (AI2)
Напиши dfs для графа в виде матрицы смежности на java.
- User
Напиши dfs для графа в виде матрицы смежности на java.
- Assistant
Вот пример реализации алгоритма поиска в глубину (DFS) для графа в виде матрицы смежности на языке Java:
import java.util.*; public class Graph { private int numVertices; private int[][] adjacencyMatrix; public Graph(int numVertices) { this.numVertices = numVertices; adjacencyMatrix = new int[numVertices][numVertices]; } public void addEdge(int src, int dest) { adjacencyMatrix[src][dest] = 1; } public void DFS(int startVertex) { boolean[] visited = new boolean[numVertices]; Stack<Integer> stack = new Stack<>(); stack.push(startVertex); while (!stack.isEmpty()) { int currentVertex = stack.pop(); if (!visited[currentVertex]) { System.out.print(currentVertex + " "); visited[currentVertex] = true; } for (int i = 0; i < numVertices; i++) { if (adjacencyMatrix[currentVertex][i] == 1 && !visited[i]) { stack.push(i); } } } } public static void main(String[] args) { Graph graph = new Graph(5); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); System.out.print("Depth First Traversal (starting from vertex 0): "); graph.DFS(0); } }В этом примере граф и его рёбра заданы вручную. Вы можете настроить входные данные в методе
mainдля тестирования вашего кода.