Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

Напиши dfs для графа в виде матрицы смежности на java.

  1. User

    Напиши dfs для графа в виде матрицы смежности на java.

  2. 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 для тестирования вашего кода.