Lab4
unknown
java
a month ago
12 kB
1
Indexable
import java.util.*; public class CODINGEXERCISE4 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); Graph graph = null; while (true) { // Step 1: User chooses graph representation (Adjacency Matrix or Adjacency List) while (graph == null) { System.out.println("Select Graph Representation:"); System.out.println("1. Adjacency Matrix"); System.out.println("2. Adjacency List"); System.out.print("Enter your choice: "); int choice = scanner.nextInt(); scanner.nextLine(); // Consume newline if (choice == 1) { graph = new AdjacencyMatrixGraph(); System.out.println("Graph initialized with Adjacency Matrix."); } else if (choice == 2) { graph = new AdjacencyListGraph(); System.out.println("Graph initialized with Adjacency List."); } else { System.out.println("Invalid choice. Please try again."); } } // Step 2: Add vertices System.out.print("Enter the number of vertices: "); int numVertices = scanner.nextInt(); scanner.nextLine(); // Consume newline for (int i = 0; i < numVertices; i++) { System.out.print("Enter label for vertex " + (i + 1) + ": "); String label = scanner.nextLine(); graph.addVertex(label); } // Step 3: Add edges (Directed or Undirected) while (true) { System.out.print("\nAdd an edge? (yes=1 / no=0): "); int addEdgeChoice = scanner.nextInt(); scanner.nextLine(); // Consume newline if (addEdgeChoice == 0) break; System.out.print("Enter source vertex: "); String src = scanner.nextLine(); System.out.print("Enter destination vertex: "); String dest = scanner.nextLine(); System.out.print("Is this edge directed? (yes=1 / no=0): "); int isDirected = scanner.nextInt(); scanner.nextLine(); // Consume newline graph.addEdge(src, dest, isDirected == 1); } // Step 4: Perform operations (DFS, BFS, or Display Graph) while (true) { System.out.println("\nGraph Operations Menu:"); System.out.println("1. Perform DFS Traversal"); System.out.println("2. Perform BFS Traversal"); System.out.println("3. Display Graph"); System.out.println("4. Reset Graph Representation"); System.out.println("5. Exit"); System.out.print("Enter your choice: "); int choice = scanner.nextInt(); scanner.nextLine(); // Consume newline switch (choice) { case 1: System.out.print("Enter starting vertex for DFS: "); String startDfs = scanner.nextLine(); graph.dfs(startDfs); break; case 2: System.out.print("Enter starting vertex for BFS: "); String startBfs = scanner.nextLine(); graph.bfs(startBfs); break; case 3: graph.display(); break; case 4: graph = null; // Reset graph representation System.out.println("Graph representation reset. Returning to selection menu..."); break; case 5: System.out.println("Exiting program..."); scanner.close(); return; default: System.out.println("Invalid choice. Please try again."); } if (choice == 4) break; // Break to reset graph } } } // Graph interface defining common methods for all graph types interface Graph { void addVertex(String label); // Add a vertex void addEdge(String src, String dest, boolean directed); // Add an edge void dfs(String start); // Perform DFS traversal void bfs(String start); // Perform BFS traversal void display(); // Display the graph } // Adjacency Matrix Implementation of Graph static class AdjacencyMatrixGraph implements Graph { private final Map<String, Integer> vertexMap = new HashMap<>(); private final List<String> vertices = new ArrayList<>(); private int[][] matrix; @Override public void addVertex(String label) { if (!vertexMap.containsKey(label)) { vertexMap.put(label, vertices.size()); vertices.add(label); resizeMatrix(); System.out.println("Vertex " + label + " added."); } else { System.out.println("Vertex " + label + " already exists."); } } @Override public void addEdge(String src, String dest, boolean directed) { if (!vertexMap.containsKey(src) || !vertexMap.containsKey(dest)) { System.out.println("One or both vertices not found."); return; } int srcIndex = vertexMap.get(src); int destIndex = vertexMap.get(dest); matrix[srcIndex][destIndex] = 1; if (!directed) { matrix[destIndex][srcIndex] = 1; } System.out.println("Edge added from " + src + " to " + dest + "."); } @Override public void dfs(String start) { if (!vertexMap.containsKey(start)) { System.out.println("Vertex not found."); return; } boolean[] visited = new boolean[vertices.size()]; System.out.print("DFS Traversal: "); dfsHelper(vertexMap.get(start), visited); System.out.println(); } private void dfsHelper(int index, boolean[] visited) { visited[index] = true; System.out.print(vertices.get(index) + " "); for (int i = 0; i < vertices.size(); i++) { if (matrix[index][i] == 1 && !visited[i]) { dfsHelper(i, visited); } } } @Override public void bfs(String start) { if (!vertexMap.containsKey(start)) { System.out.println("Vertex not found."); return; } boolean[] visited = new boolean[vertices.size()]; Queue<Integer> queue = new LinkedList<>(); int startIndex = vertexMap.get(start); visited[startIndex] = true; queue.add(startIndex); System.out.print("BFS Traversal: "); while (!queue.isEmpty()) { int index = queue.poll(); System.out.print(vertices.get(index) + " "); for (int i = 0; i < vertices.size(); i++) { if (matrix[index][i] == 1 && !visited[i]) { visited[i] = true; queue.add(i); } } } System.out.println(); } @Override public void display() { System.out.println("Adjacency Matrix:"); System.out.print(" "); for (String vertex : vertices) { System.out.print(vertex + " "); } System.out.println(); for (int i = 0; i < vertices.size(); i++) { System.out.print(vertices.get(i) + " "); for (int j = 0; j < vertices.size(); j++) { System.out.print(matrix[i][j] + " "); } System.out.println(); } } private void resizeMatrix() { int size = vertices.size(); int[][] newMatrix = new int[size][size]; if (matrix != null) { for (int i = 0; i < matrix.length; i++) { System.arraycopy(matrix[i], 0, newMatrix[i], 0, matrix[i].length); } } matrix = newMatrix; } } // Adjacency List Implementation of Graph static class AdjacencyListGraph implements Graph { private final Map<String, List<String>> adjList = new HashMap<>(); @Override public void addVertex(String label) { if (!adjList.containsKey(label)) { adjList.put(label, new ArrayList<>()); System.out.println("Vertex " + label + " added."); } else { System.out.println("Vertex " + label + " already exists."); } } @Override public void addEdge(String src, String dest, boolean directed) { if (!adjList.containsKey(src) || !adjList.containsKey(dest)) { System.out.println("One or both vertices not found."); return; } adjList.get(src).add(dest); if (!directed) { adjList.get(dest).add(src); } System.out.println("Edge added from " + src + " to " + dest + "."); } @Override public void dfs(String start) { if (!adjList.containsKey(start)) { System.out.println("Vertex not found."); return; } Set<String> visited = new HashSet<>(); System.out.print("DFS Traversal: "); dfsHelper(start, visited); System.out.println(); } private void dfsHelper(String vertex, Set<String> visited) { visited.add(vertex); System.out.print(vertex + " "); for (String neighbor : adjList.get(vertex)) { if (!visited.contains(neighbor)) { dfsHelper(neighbor, visited); } } } @Override public void bfs(String start) { if (!adjList.containsKey(start)) { System.out.println("Vertex not found."); return; } Set<String> visited = new HashSet<>(); Queue<String> queue = new LinkedList<>(); visited.add(start); queue.add(start); System.out.print("BFS Traversal: "); while (!queue.isEmpty()) { String vertex = queue.poll(); System.out.print(vertex + " "); for (String neighbor : adjList.get(vertex)) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.add(neighbor); } } } System.out.println(); } @Override public void display() { System.out.println("Adjacency List:"); for (Map.Entry<String, List<String>> entry : adjList.entrySet()) { System.out.print(entry.getKey() + ": "); for (String neighbor : entry.getValue()) { System.out.print(neighbor + " "); } System.out.println(); } } } }
Editor is loading...
Leave a Comment