can you explain me the code i ammentioning

Question

#Practical 1 : BFS
class Vertex:
    def __init__(self,n):
        self.name=n
        self.neighbors=list()

        self.distance=9999
        self.color='blue'
    def add_neighbors(self,v):
        if v not in self.neighbors:
            self.neighbors.append(v)
            self.neighbors.sort()

class Graph:
    vertices={}
    def add_vertex(self,vertex):
        if isinstance (vertex,Vertex) and vertex.name not in self.vertices:
            self.vertices[vertex.name]=vertex
            return True
        else:
            return False
        
    def add_edge(self,u,v):
        if u in self.vertices and v in self.vertices:
            for key,value in self.vertices.items():
                if key==u:
                    value.add_neighbors(v)
                if key==v:
                    value.add_neighbors(u)
            return True
        else:
            return False

    def print_graph(self):
        for key in sorted(list(self.vertices.keys())):
                          print(key +str(self.vertices[key].neighbors)+""+str(self.vertices[key].distance))
    def bfs(self,vert):
                          q=list()
                          vert.distance=0
                          vert.color='red'
                          for v in vert.neighbors:
                              self.vertices[v].distance=vert.distance + 1
                              q.append(v)
                          while len(q)>0:
                              u=q.pop(0)
                              node_u=self.vertices[u]
                              node_u.color='red'

                              for v in node_u.neighbors:
                                  node_v=self.vertices[v]
                                  if node_v.color=='black':
                                      q.append(v)
                                      if node_v.distance > node_u.distance + 1:
                                          node_v.distance=node_u.distance + 1              

            
                                
g=Graph()
a=Vertex('A')
g.add_vertex(a)
g.add_vertex(Vertex('B'))
for i in range(ord('A'),ord('K')):
  g.add_vertex(Vertex(chr(i)))
  
edges=['AB','AE','BF','CG','DE','EH','FG','FI','FJ','GF','GJ','HI','HE']

for edge in edges:
  g.add_edge(edge[:1],edge[1:])
                          
g.bfs(a)
g.print_graph()

Answer 1

1. BFS & DFS (Combined)

This version includes the shared graph and visited array management.

Java

import java.util.*;

public class Main {
    static void bfs(int start, ArrayList<Integer>[] adj, boolean[] vis) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        vis[start] = true;

        while (!q.isEmpty()) {
            int u = q.poll();
            System.out.print(u + " ");
            for (int v : adj[u]) {
                if (!vis[v]) {
                    vis[v] = true;
                    q.add(v);
                }
            }
        }
    }

    static void dfs(int u, ArrayList<Integer>[] adj, boolean[] vis) {
        vis[u] = true;
        System.out.print(u + " ");
        for (int v : adj[u]) {
            if (!vis[v]) {
                dfs(v, adj, vis);
            }
        }
    }

    public static void main(String[] args) {
        int n = 6;
        ArrayList<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();

        adj[1].add(2); adj[2].add(1);
        adj[1].add(3); adj[3].add(1);
        adj[2].add(4); adj[4].add(2);
        adj[2].add(5); adj[5].add(2);

        boolean[] vis = new boolean[n];
        System.out.println("BFS Traversal:");
        bfs(1, adj, vis);

        Arrays.fill(vis, false);
        System.out.println("\nDFS Traversal:");
        dfs(1, adj, vis);
    }
}

---

2. BFS Shortest Path (Unweighted)

Finds the number of edges from the source to every other node.

Java

import java.util.*;

public class Main {
    static int[] bfsShortestPath(int start, ArrayList<Integer>[] adj, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        dist[start] = 0;

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.add(v);
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int n = 5;
        ArrayList<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        adj[0].add(1); adj[1].add(0);
        adj[0].add(2); adj[2].add(0);
        adj[1].add(3); adj[3].add(1);
        adj[3].add(4); adj[4].add(3);

        int[] res = bfsShortestPath(0, adj, n);
        for(int i=0; i<n; i++) System.out.println("Node " + i + " distance: " + res[i]);
    }
}

---

Comments

3. Dijkstra's Algorithm (Weighted Shortest Path)
Includes the Pair helper class and priority queue logic.

Java

import java.util.*;

public class Main {
    static class Pair {
        int node, cost;
        Pair(int node, int cost) { this.node = node; this.cost = cost; }
    }

    static int[] dijkstra(int start, ArrayList<Pair>[] adj, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);

        dist[start] = 0;
        pq.add(new Pair(start, 0));

        while (!pq.isEmpty()) {
            Pair cur = pq.poll();
            int u = cur.node;
            if (cur.cost > dist[u]) continue;
            for (Pair edge : adj[u]) {
                if (dist[u] + edge.cost < dist[edge.node]) {
                    dist[edge.node] = dist[u] + edge.cost;
                    pq.add(new Pair(edge.node, dist[edge.node]));
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int n = 4;
        ArrayList<Pair>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        adj[0].add(new Pair(1, 5));
        adj[0].add(new Pair(2, 1));
        adj[2].add(new Pair(1, 2));
        adj[1].add(new Pair(3, 1));

        int[] d = dijkstra(0, adj, n);
        for(int i=0; i<n; i++) System.out.println("Cost to " + i + ": " + d[i]);
    }
}
4. Bellman-Ford (Negative Weights & Cycles)
Includes the negative cycle detection logic.

Java

import java.util.*;

public class Main {
    static class Edge {
        int u, v, w;
        Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
    }

    static int[] bellmanFord(int start, ArrayList<Edge> edges, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, 1000000000);
        dist[start] = 0;

        for (int i = 0; i < n - 1; i++) {
            for (Edge e : edges) {
                if (dist[e.u] != 1000000000 && dist[e.u] + e.w < dist[e.v]) {
                    dist[e.v] = dist[e.u] + e.w;
                }
            }
        }
        return dist;
    }

    static boolean hasNegativeCycle(ArrayList<Edge> edges, int[] dist) {
        for (Edge e : edges) {
            if (dist[e.u] != 1000000000 && dist[e.u] + e.w < dist[e.v]) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int n = 4;
        ArrayList<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 4));
        edges.add(new Edge(1, 2, -6));
        edges.add(new Edge(2, 3, 2));
        edges.add(new Edge(3, 1, 1)); // This creates a negative cycle!

        int[] dist = bellmanFord(0, edges, n);
        if (hasNegativeCycle(edges, dist)) System.out.println("Negative Cycle Detected!");
        else System.out.println("No Negative Cycle.");
    }
}
5. Kruskal's Algorithm (Minimum Spanning Tree)
Includes the Disjoint Set Union (DSU) structure.

Java

import java.util.*;

public class Main {
    static class Edge {
        int u, v, w;
        Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
    }

    static int[] parent, rank;
    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    static boolean union(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (rootA == rootB) return false;
        if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
        else if (rank[rootA] > rank[rootB]) parent[rootB] = rootA;
        else { parent[rootB] = rootA; rank[rootA]++; }
        return true;
    }

    static int kruskal(ArrayList<Edge> edges, int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        edges.sort((a, b) -> a.w - b.w);
        int mstCost = 0;
        for (Edge e : edges) {
            if (union(e.u, e.v)) mstCost += e.w;
        }
        return mstCost;
    }

    public static void main(String[] args) {
        int n = 4;
        ArrayList<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));

        System.out.println("MST Cost: " + kruskal(edges, n));
    }
}

---

....................