matrix[i][j] indicates an edge between vertex i and j.O(V^2).O(V + E).Depth First Search (DFS):
void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
visited[node] = true;
System.out.print(node + " ");
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, visited, graph);
}
}
}
Breadth First Search (BFS):
void bfs(int startNode, List<List<Integer>> graph) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> queue = new LinkedList<>();
queue.add(startNode);
visited[startNode] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
Topological Sort:
void topologicalSort(int node, boolean[] visited, Stack<Integer> stack, List<List<Integer>> graph) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
topologicalSort(neighbor, visited, stack, graph);
}
}
stack.push(node);
}
Shortest Path Algorithms:
Dijkstra's Algorithm: Finds shortest paths from a source vertex.
void dijkstra(int src, int vertices, List<List<int[]>> graph) {
int[] dist = new int[vertices];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.add(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int node = curr[0], weight = curr[1];
for (int[] neighbor : graph.get(node)) {
int nextNode = neighbor[0], edgeWeight = neighbor[1];
if (dist[node] + edgeWeight < dist[nextNode]) {
dist[nextNode] = dist[node] + edgeWeight;
pq.add(new int[]{nextNode, dist[nextNode]});
}
}
}
System.out.println(Arrays.toString(dist));
}