Uses queue, but still needs to check matrix for neighbours.
2. Weighted Graph Implementation
If the graph is weighted, we replace 1 with the weight of the edge.
Code
import java.util.*;
class WeightedGraph {
private int vertices; // Number of vertices
private int[][] adjacencyMatrix; // Adjacency Matrix
// Constructor
public WeightedGraph(int vertices) {
this.vertices = vertices;
adjacencyMatrix = new int[vertices][vertices];
// Initialize the matrix with a large value to indicate no edge (-1 is used here)
for (int i = 0; i < vertices; i++) {
Arrays.fill(adjacencyMatrix[i], -1);
}
}
// Method to add an edge (Undirected Graph)
public void addEdge(int src, int dest, int weight) {
adjacencyMatrix[src][dest] = weight;
adjacencyMatrix[dest][src] = weight; // For undirected graph
}
// Method to add a directed edge
public void addDirectedEdge(int src, int dest, int weight) {
adjacencyMatrix[src][dest] = weight;
}
// Method to remove an edge
public void removeEdge(int src, int dest) {
adjacencyMatrix[src][dest] = -1;
adjacencyMatrix[dest][src] = -1; // For undirected graph
}
// Method to check if an edge exists
public boolean hasEdge(int src, int dest) {
return adjacencyMatrix[src][dest] != -1;
}
// Method to get the weight of an edge
public int getEdgeWeight(int src, int dest) {
return adjacencyMatrix[src][dest];
}
// Method to print the adjacency matrix
public void printGraph() {
System.out.println("Weighted Adjacency Matrix:");
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
System.out.print((adjacencyMatrix[i][j] == -1 ? "∞" : adjacencyMatrix[i][j]) + "\t");
}
System.out.println();
}
}
// Method to get neighbors of a given vertex
public List<Integer> getNeighbors(int vertex) {
List<Integer> neighbors = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
if (adjacencyMatrix[vertex][i] != -1) {
neighbors.add(i);
}
}
return neighbors;
}
// Depth-First Search (DFS)
public void dfs(int startVertex) {
boolean[] visited = new boolean[vertices];
System.out.print("DFS Traversal: ");
dfsHelper(startVertex, visited);
System.out.println();
}
private void dfsHelper(int vertex, boolean[] visited) {
visited[vertex] = true;
System.out.print(vertex + " ");
for (int i = 0; i < vertices; i++) {
if (adjacencyMatrix[vertex][i] != -1 && !visited[i]) {
dfsHelper(i, visited);
}
}
}
// Breadth-First Search (BFS)
public void bfs(int startVertex) {
boolean[] visited = new boolean[vertices];
Queue<Integer> queue = new LinkedList<>();
visited[startVertex] = true;
queue.add(startVertex);
System.out.print("BFS Traversal: ");
while (!queue.isEmpty()) {
int vertex = queue.poll();
System.out.print(vertex + " ");
for (int i = 0; i < vertices; i++) {
if (adjacencyMatrix[vertex][i] != -1 && !visited[i]) {
queue.add(i);
visited[i] = true;
}
}
}
System.out.println();
}
// Main Method for Testing
public static void main(String[] args) {
WeightedGraph graph = new WeightedGraph(5);
// Adding edges with weights
graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 2);
graph.addEdge(1, 3, 7);
graph.addEdge(1, 4, 1);
graph.addEdge(2, 4, 3);
// Printing the adjacency matrix
graph.printGraph();
// Checking if edge exists and its weight
System.out.println("Edge between 0 and 1: " + graph.hasEdge(0, 1));
System.out.println("Weight of edge (0,1): " + graph.getEdgeWeight(0, 1));
System.out.println("Edge between 2 and 3: " + graph.hasEdge(2, 3));
// Removing an edge
graph.removeEdge(1, 4);
graph.printGraph();
// Getting neighbors of a vertex
System.out.println("Neighbors of vertex 1: " + graph.getNeighbors(1));
// Performing DFS and BFS
graph.dfs(0);
graph.bfs(0);
}
}
