lab

 from collections import defaultdict




class Graph:


    def __init__(self):


        self.graph = defaultdict(list)




    def add_edge(self, u, v):


        self.graph[u].append(v)




    def bfs(self, start):


        visited = set()


        queue = [start]




        while queue:


            vertex = queue.pop(0)


            if vertex not in visited:


                print(vertex, end=" ")


                visited.add(vertex)




                for neighbor in self.graph[vertex]:


                    if neighbor not in visited:


                        queue.append(neighbor)




# Example usage:


if __name__ == "__main__":


    g = Graph()


    g.add_edge(0, 1)


    g.add_edge(0, 2)


    g.add_edge(1, 2)


    g.add_edge(2, 0)


    g.add_edge(2, 3)


    g.add_edge(3, 3)




    print("Breadth-First Traversal (starting from vertex 2):")


    g.bfs(2)






VIVA



BFS Purpose: Find shortest paths, explore nodes layer by layer.


Heuristic in A*: Estimate node-to-goal distance, guides efficient search.


A Advantages/Limitations*:


Advantages: Completeness, Optimality, Efficiency.

Limitations: Memory usage, Heuristic quality, Admissibility.

TSP (Traveling Salesman Problem): Find shortest route visiting cities once, NP-hard, various solving methods (Exact, Approximation, Heuristics), practical applications in routing and optimization.


Comments

Post a Comment

Popular posts from this blog

1d array

 1. A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the  left. For example, if 2 left rotations are performed on array [1,2,3,4,5], then the array would  become [3,4,5,1,2]. Given an array of n integers and a number, d, perform d left rotations on  the array. Then print the updated array as a single line of spaceseparated integers. Sol: #include<stdio.h> int main() {  int i,s,j,t;  long long int n;  scanf("%lld",&n);  int a[n];  scanf("%d",&s);  for(i=0;i<n;i++)  {  scanf("%d",&a[i]);  }  for(j=1;j<=s;j++)  {  t=a[0];  for(i=0;i<=n-1;i++)  {  a[i]=a[i+1];  }  a[n-1]=t;  }  for(i=0;i<n;i++)  {  printf("%d ",a[i]);  }  return 0; } 2. Develop a program to accept the age of n students of class, rearrange the data in ascending  order and display the age of youngest and eldest stu...
Read more

strings

 /* 1. You have been given a String S. You need to find and print whether this string is a  palindrome or not. If yes, print"YES" (without quotes), else print "NO" (without quotes) */ #include <stdio.h> #include <string.h> int main()  { int h,l=0,count=0; char ch[100]; scanf("%s", ch); h=(strlen(ch)-1); while(h>l){  if(ch[l++]!=ch[h--]){  count++;  }  } if(count>0){  printf("NO"); } else{  printf("YES"); }  return 0; } /* 2. Alice wrote a sequence of words in CamelCase as a string of letters, s, having the  following properties: It is a concatenation of one or more words consisting of English  letters., All letters in the first word are lowercase., For each of the subsequent words, the  first letter is uppercase and rest of the letters are lowercase. Given s, print the number of  words in s on a new line.Sample Input: saveChangesInTheEditor Sample Output: 5 */ #include<stdio.h> int main() { ...
Read more

2d array

1. Given two matrices of order M1*N1 and M2*N2. Write function to perform matrix multiplication and display the resultant matrix if matrix multiplication is possible otherwise display the message "Invalid Matrices".  Sol: #include int main()  {  i nt m, n, p, q, c, d, k, sum = 0;   int first[10][10], second[10][10], z[10][10];  printf("\nEnter the number of rows and columns of first matrix:\n");   scanf("%d%d", &m, &n);   printf("\nEnter the number of rows and columns of second matrix:\n");   scanf("%d%d", &p, &q);  if ( n != p )  {  printf("\nMatrices with entered orders can't be multiplied with each other.\n");   printf("\nThe column of first matrix should be equal to row of second.\n");   }  else   {   printf("\nEnter the elements of first matrix:\n");   for ( c = 0 ; c < m ; c++ )   for ( d = 0 ; d < n ; d++ )  scanf...
Read more