Scribd Logo
Upload

Welcome to Scribd!

  • 18 views

    20BCS7358 CC Exp.5

    Uploaded by

    Shudhashekhar Das
    Student Name: ROHIT MOHAN completed an experiment on competitive coding to learn about graphs and trees. The experiment involved implementing breadth-first search (BFS) on a graph to find shortest distances between nodes. It also involved finding the maximum number of edges that can be removed from a tree to create a forest with all even-numbered components. The student wrote Python code to solve both problems and learned how to implement BFS and about graph and tree data structures.

    Copyright:

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

    20BCS7358 CC Exp.5

    Uploaded by

    Shudhashekhar Das
    18 views4 pages
    Student Name: ROHIT MOHAN completed an experiment on competitive coding to learn about graphs and trees. The experiment involved implementing breadth-first search (BFS) on a graph to find shortest distances between nodes. It also involved finding the maximum number of edges that can be removed from a tree to create a forest with all even-numbered components. The student wrote Python code to solve both problems and learned how to implement BFS and about graph and tree data structures.

    Original Title

    20BCS7358_CC_EXP.5

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Student Name: ROHIT MOHAN completed an experiment on competitive coding to learn about graphs and trees. The experiment involved implementing breadth-first search (BFS) on a graph to find shortest distances between nodes. It also involved finding the maximum number of edges that can be removed from a tree to create a forest with all even-numbered components. The student wrote Python code to solve both problems and learned how to implement BFS and about graph and tree data structures.

    Copyright:

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

    20BCS7358 CC Exp.5

    Uploaded by

    Shudhashekhar Das
    Student Name: ROHIT MOHAN completed an experiment on competitive coding to learn about graphs and trees. The experiment involved implementing breadth-first search (BFS) on a graph to find shortest distances between nodes. It also involved finding the maximum number of edges that can be removed from a tree to create a forest with all even-numbered components. The student wrote Python code to solve both problems and learned how to implement BFS and about graph and tree data structures.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    Experiment Title 5

    Student Name: ROHIT MOHAN UID: 20BCS7358


    Branch: BE (CSE) Section/Group: WM_604(B)
    Semester: 5th sem Subject Code: 20CSP-314
    Subject Name: COMPETITIVE CODING

    1. Aim/Overview of the practical: Learn about the Graph and tree.

    2. Task to be done/ Which logistics used:

     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.

     You are given a tree (a simple connected graph with no cycles).Find the maximum number of edges you
    can remove from the tree to get a forest such that each connected component of the forest contains an
    even number of nodes.As an example, the following tree with 4 nodes can be cut at most1 time to create
    an even forest.

    3. Requirement Analysis :-

    Software Requirement: Google Chrome, Hackerrank Platform, Online Compiler.

    Hardware Requirement: Computer, Windows 10, Power Supply.

    4. Steps for experiment/practical/Code:

    BFS
    import queue
    t = int(input())
    for i in range(t):
    v, e = map(int, input().split())
    l = [[0 for x in range(v)] for y in range(v)]

    visited = [0 for x in range(v)]


    distance = [-1 for x in range(v)]
    q = queue.Queue()

    for j in range(e):
    a, b = map(int, input().split())
    l[a - 1][b - 1] = l[b - 1][a - 1] = 1
    s = int(input())
    q.put(s - 1)
    visited[s - 1] = 1
    distance[s - 1] = 0

    while not q.empty():


    a = q.get()
    for j in range(v):
    if l[a][j] and not visited[j]:
    q.put(j)
    visited[j] = 1
    distance[j] = distance[a] + 6

    for j in range(v):
    if j != s - 1:
    print(distance[j], end = ' ')

    print()

    Even Tree:

    tn, te = map(int, input().rstrip().split())


    ch = {}
    tr = {}

    for i in range(te):
    tf, tt = map(int, input().rstrip().split())
    if tt not in tr.keys(): tr[tt] = [tf]
    else: tr[tt].append(tf)
    ch[i] = 1

    for i in range(te+1, 1, -1):


    if i not in tr.keys():
    ch[i] = 1
    else:
    for j in tr[i]:
    ch[i] += ch[j]
    c=0
    for i in range(te):
    if ch[i] % 2 == 0:
    c+=1

    print(c)

    5. Output:
    BFS
    Even Tree

    6. Learning outcomes (What I have learnt):


    1. Write a python program to implement breadth-first search algorithm (BFS).

    2. Learnt about graph and tree data structure.

    Evaluation Grid (To be created as per the SOP and Assessment guidelines by the faculty):

    Sr. No. Parameters Marks Obtained Maximum Marks


    1.
    2.
    3.

    You might also like