code na malinis

 avatar
user_0616194
plain_text
2 years ago
2.4 kB
4
Indexable
package dsa_finals;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Graph {
    private int[][] adjacencyMatrix; 
    private int numVertices; 

    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 BFS(int startVertex) {
        boolean[] visited = new boolean[numVertices]; 
        Queue<Integer> queue = new LinkedList<Integer>(); 
        visited[startVertex] = true; 
        queue.add(startVertex); 

        while (!queue.isEmpty()) { 
            int node = queue.poll(); 
            System.out.print(node + " -> "); 

            for (int i = 0; i < numVertices; i++) { 
                if (adjacencyMatrix[node][i] == 1 && !visited[i]) {
                    visited[i] = true; 
                    queue.add(i); 
                }
            }
        }
        System.out.println("Done"); 
    }

    public void printMatrix() {
        System.out.println("Adjacency matrix representation:");
        
        System.out.print("   ");
        for (int i = 0; i < numVertices; i++) {
            System.out.print(i + " ");
        }
        System.out.println();
        
        for (int i = 0; i < numVertices; i++) {
            
            System.out.print(i + ": ");
            
            for (int j = 0; j < numVertices; j++) {
                
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
        
        System.out.println();
        }
    }


    public static void main(String[] args) {
        Graph graph = new Graph(6); 
        graph.addEdge(0, 1); 
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);
        graph.addEdge(4, 5);

        graph.printMatrix(); 
        
        System.out.println();
        
        try (Scanner sc = new Scanner(System.in)) {
			int startVertex = 0;

			System.out.print("Enter the starting vertex for BFS: ");        
			startVertex = sc.nextInt(); 
			
			System.out.print("BFS starting from vertex " + startVertex + ": ");
			graph.BFS(startVertex); 
		}
    }
}