# Graph Code with DFS and modified Main user_0616194
plain_text
7 months ago
4.9 kB
8
Indexable
Never
```package dsa_finals;

import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Graph {
private int[][] adjacencyMatrix; // 2D array to represent the graph's adjacency matrix
private int numVertices; // number of vertices in the graph

public Graph(int numVertices) {
this.numVertices = numVertices;
adjacencyMatrix = new int[numVertices][numVertices]; // initialize the adjacency matrix with 0 values
}

public void addEdge(int src, int dest) {
adjacencyMatrix[src][dest] = 1; // add directed edge from src to dest by setting the corresponding value to 1
}

public void BFS(int startVertex) {
boolean[] visited = new boolean[numVertices]; // array to keep track of visited vertices
Queue<Integer> queue = new LinkedList<Integer>(); // queue to store vertices to be visited
visited[startVertex] = true; // mark the starting vertex as visited

while (!queue.isEmpty()) { // loop until all vertices have been visited
int node = queue.poll(); // get the next vertex from the queue
System.out.print(node + " -> "); // output the vertex being visited

for (int i = 0; i < numVertices; i++) { // loop through all vertices
if (adjacencyMatrix[node][i] == 1 && !visited[i]) { // if there is a directed edge from node to i and i has not been visited
visited[i] = true; // mark i as visited
}
}
}
System.out.println("Done"); // output message indicating that the BFS is complete
}

public void DFS(int startVertex) {
boolean[] visited = new boolean[numVertices]; // array to keep track of visited vertices
Stack<Integer> stack = new Stack<Integer>(); // stack to store vertices to be visited
visited[startVertex] = true; // mark the starting vertex as visited
stack.push(startVertex); // push the starting vertex onto the stack

while (!stack.isEmpty()) { // loop until all vertices have been visited
int node = stack.pop(); // get the next vertex from the top of the stack
System.out.print(node + " -> "); // output the vertex being visited

for (int i = 0; i < numVertices; i++) { // loop through all vertices
if (adjacencyMatrix[node][i] == 1 && !visited[i]) { // if there is a directed edge from node to i and i has not been visited
visited[i] = true; // mark i as visited
stack.push(i); // push i onto the stack to be visited later
}
}
}
System.out.println("Done"); // output message indicating that the DFS is complete
}

public void printMatrix() {
// Output the column labels
System.out.print("   ");
for (int i = 0; i < numVertices; i++) {
System.out.print(i + " ");
}
System.out.println();
// Output the rows of the matrix
for (int i = 0; i < numVertices; i++) {
// Output the row label (the vertex number)
System.out.print(i + ": ");
// Output the values in the row
for (int j = 0; j < numVertices; j++) {
// Output the value of the adjacency matrix for the current row and column
}
// Move to the next line after outputting the entire row
System.out.println();
}
}

public static void main(String[] args) {
Graph graph = new Graph(6); // create a graph with 6 vertices

graph.printMatrix(); // output the adjacency matrix

System.out.println();

try (Scanner sc = new Scanner(System.in)) {
int startVertex = 0;

System.out.print("Enter the starting vertex : ");
startVertex = sc.nextInt(); // get the starting vertex from the user

System.out.print("BFS starting from vertex " + startVertex + ": ");
graph.BFS(startVertex); // run BFS starting from the user-specified vertex

System.out.print("DFS starting from vertex " + startVertex + ": ");
graph.DFS(startVertex); // run DFS starting from the user-specified vertex
}
}
}```