Scribd Logo
Upload

Welcome to Scribd!

  • 30 views

    AP 2.1 Keshav

    Uploaded by

    keshav Sharma
    The document describes an experiment conducted by a student to implement graphs and find the shortest path between nodes using breadth-first search. It provides the student's name, course details, aim to implement graphs, and an objective to create a graph from edges and find the shortest distance from a starting node to all other nodes. It also includes sample code and output for creating an adjacency list representation of the graph and using BFS to return the distances.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    AP 2.1 Keshav

    Uploaded by

    keshav Sharma
    30 views5 pages
    The document describes an experiment conducted by a student to implement graphs and find the shortest path between nodes using breadth-first search. It provides the student's name, course details, aim to implement graphs, and an objective to create a graph from edges and find the shortest distance from a starting node to all other nodes. It also includes sample code and output for creating an adjacency list representation of the graph and using BFS to return the distances.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes an experiment conducted by a student to implement graphs and find the shortest path between nodes using breadth-first search. It provides the student's name, course details, aim to implement graphs, and an objective to create a graph from edges and find the shortest distance from a starting node to all other nodes. It also includes sample code and output for creating an adjacency list representation of the graph and using BFS to return the distances.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    30 views5 pages

    AP 2.1 Keshav

    Uploaded by

    keshav Sharma
    The document describes an experiment conducted by a student to implement graphs and find the shortest path between nodes using breadth-first search. It provides the student's name, course details, aim to implement graphs, and an objective to create a graph from edges and find the shortest distance from a starting node to all other nodes. It also includes sample code and output for creating an adjacency list representation of the graph and using BFS to return the distances.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 5

    DEPARTMENT OF

    COMPUTER SCIENCE & ENGINEERING

    Experiment 2.1

    Student Name: Keshav Sharma UID: 21BCS7598


    Branch:BE-CSE Section/Group-626-A
    Semester:5th Date of Performance:19/09/2023
    Subject Name: Advance Programming Lab Subject Code: 21CSP-314

    Aim: Graphs: To implement the concept of Graphs.

    Objective:
    Consider an undirected graph where each edge weighs 6 units. Each of the nodes is labeled
    consecutively from 1 to n.
    You will be given a number of queries. For each query, you will be given a list of edges
    describing an undirected graph. After you create a representation of the graph, you must
    determine and report the shortest distance to each of the other nodes from a given starting
    position using the breadth-first search algorithm (BFS). Return an array of distances from
    the start node in node number order. If a node is unreachable, return -1 for that node.

    Script and Output:

    import java.io.*; import


    java.math.*; import
    java.security.*;
    import static java.util.stream.Collectors.joining;
    import static java.util.stream.Collectors.toList;
    class Result {

    public static List<Integer> bfs(int n, int m, List<List<Integer>> edges, int s) {

    List<List<Integer>> adjList = new ArrayList<>();


    for (int i = 0; i <= n; i++) {
    DEPARTMENT OF
    COMPUTER SCIENCE & ENGINEERING
    adjList.add(new ArrayList<>());
    }
    for (List<Integer> edge : edges) {
    int u = edge.get(0);
    int v = edge.get(1);

    adjList.get(u).add(v);
    adjList.get(v).add(u); // Undirected graph, so add both directions
    }
    boolean[] visited = new boolean[n + 1];
    int[] distance = new int[n + 1];
    Arrays.fill(distance, -1);

    // Create a queue for BFS


    Queue<Integer> queue = new LinkedList<>();
    queue.add(s);
    visited[s] = true;
    distance[s] = 0;
    while (!queue.isEmpty()) {
    int current = queue.poll();
    for (int neighbor : adjList.get(current)) {
    if (!visited[neighbor]) {
    visited[neighbor] = true;
    distance[neighbor] = distance[current] + 6;
    queue.add(neighbor);
    }}}
    List<Integer> result = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
    if (i != s) {
    result.add(distance[i]);
    }}
    return result;
    }
    }
    DEPARTMENT OF
    COMPUTER SCIENCE & ENGINEERING
    Output

    Objective:
    Complete the quickestWayUp function in the editor below. It should return an integer that
    represents the minimum number of moves required.
    quickestWayUp has the following parameter(s):
     ladders: a 2D integer array where each ladders[i] contains the start and end cell
    numbers of a ladder
     snakes: a 2D integer array where each snakes[i] contains the start and end cell
    numbers of a snake

    Script and Output:

    import java.io.*; import


    java.math.*; import
    java.security.*;
    import static java.util.stream.Collectors.joining;
    import static java.util.stream.Collectors.toList;

    class Result {

    public static int quickestWayUp(List<List<Integer>> ladders, List<List<Integer>>


    snakes) {
    DEPARTMENT OF
    COMPUTER SCIENCE & ENGINEERING
    int[] board = new int[101];
    Arrays.fill(board, -1);
    // Mark the ladder bases and snake mouths on the board
    for (List<Integer> ladder : ladders) {
    int start = ladder.get(0);
    int end = ladder.get(1);
    board[start] = end;
    }
    for (List<Integer> snake : snakes) {
    int mouth = snake.get(0);
    int tail = snake.get(1);
    board[mouth] = tail;
    }

    Queue<Integer> queue = new LinkedList<>();


    queue.add(1); // Start from square 1
    board[1] = 0; // Mark square 1 as visited with 0 steps
    while (!queue.isEmpty()) {
    int currentSquare = queue.poll();

    // Roll the die from 1 to 6


    for (int i = 1; i <= 6; i++) {
    int nextSquare = currentSquare + i;

    // If the next square is within the board


    if (nextSquare <= 100) {
    // If the next square is a ladder or snake, use its endpoint as the next square
    if (board[nextSquare] != -1) {
    nextSquare = board[nextSquare];
    }

    // If the next square has not been visited yet


    if (board[nextSquare] == -1) {
    board[nextSquare] = board[currentSquare] + 1; // Increment steps
    queue.add(nextSquare);
    }
    }
    }
    }
    if (board[100] == -1) {
    return -1; // Square 100 is unreachable
    DEPARTMENT OF
    COMPUTER SCIENCE & ENGINEERING
    }
    else
    {
    return board[100];
    }
    }
    }

    Output:

    You might also like