II B.Tech I Semester Supplementary Examinations, February 2007ADVANCED DATA STRUCTURES & ALGORITHMS( Common to Information Technology and Computer Science & SystemsEngineering)Time: 3 hoursMax Marks: 80Answer any FIVE QuestionsAll Questions carry equal marks. . . . .
1. (a) What is di. between malloc()/free() and new/delete.
(b) What are the access privileges in C++. What is the default access level.
(c) What is destructor.(d) What is passing by reference.[4+4+4+4]
2. (a) What’s the deal with operator overloading.
(b) What are the benefits of operator overloading.
(c) What are some examples of operator overloading.
(d) What operators can/cannot be overloaded.[4+4+4+4]
3. (a) How can we provide printing for an entire hierarchy of classes.
(b) How can we open a stream in binary mode.
(c) How can we “reopen" std::cin and std::cout in binary mode.[5+5+6]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. (a) What is a dictionary. Define the abstract data type for it. Write the abstractclass for the dictionary.
(b) Give the applications of dictionary or dictionary with duplicates in whichsequential access is desired.[8+8]
6. What is a Binary search tree. Provide a specification for the abstract data typeBSTree(binary search tree with duplicates). Define a C++ abstract class thatcorresponds to this ADT. Write a program to insert a pair into a binary searchtree.[16]
7. Write and explain a non recursive algorithm for post order traversal of a Binarytree with an example.[16]
8. (a) Explain the Job sequencing with deadlines with an example using the greedyapproach.
Wednesday, October 10, 2007
B.Tech I Semester Supplementary Examinations, February 2007ADVANCED DATA STRUCTURES & ALGORITHMS
B.Tech I Semester Supplementary Examinations, February 2007ADVANCED DATA STRUCTURES & ALGORITHMS( Common to Information Technology and Computer Science & SystemsEngineering)Time: 3 hoursMax Marks: 80Answer any FIVE QuestionsAll Questions carry equal marks. . . . .
1. (a) Explain about Object Oriented Programming principles.
(b) Comapare C++ with C.[8+8]
2. Define Inheritance. How many types of inheritances are there. Explain each withsuitable examples.[16]
3. (a) How does that funky while (std :: cin >> foo) syntax work.
(b) Why does input seem to process past the end of file.
(c) Should we end output lines with std::endl or ‘\n'.[5+5+6]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]6. (a) Write a method to delete the pair with the largest key from a Binary SearchTree.
(b) Write a method to find the height of a Binary Search Tree.[8+8]
7. Write and explain an algorithm to determine if the AND/OR tree T is solvable.[16]8. (a) Write a linear time algorithm that generates the OBST from the root table.
(b) Prove that the greedy method always obtains an optimal solution to the job-sequencing problem.[8+8]
1. (a) Explain about Object Oriented Programming principles.
(b) Comapare C++ with C.[8+8]
2. Define Inheritance. How many types of inheritances are there. Explain each withsuitable examples.[16]
3. (a) How does that funky while (std :: cin >> foo) syntax work.
(b) Why does input seem to process past the end of file.
(c) Should we end output lines with std::endl or ‘\n'.[5+5+6]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]6. (a) Write a method to delete the pair with the largest key from a Binary SearchTree.
(b) Write a method to find the height of a Binary Search Tree.[8+8]
7. Write and explain an algorithm to determine if the AND/OR tree T is solvable.[16]8. (a) Write a linear time algorithm that generates the OBST from the root table.
(b) Prove that the greedy method always obtains an optimal solution to the job-sequencing problem.[8+8]
2II B.Tech I Semester Supplementary Examinations, February 2007ADVANCED DATA STRUCTURES & ALGORITHMS
Code No: R059211201Set No. 2II B.Tech I Semester Supplementary Examinations, February 2007ADVANCED DATA STRUCTURES & ALGORITHMS( Common to Information Technology and Computer Science & SystemsEngineering)Time: 3 hoursMax Marks: 80Answer any FIVE QuestionsAll Questions carry equal marks. . . . .
1. (a) Explain about the friend function with a suitable example.
(b) Why is it best to use inline functions instead of plain old # define macros.
(c) How to tell the compiler to make a non-member function inline.
(d) How to tell the compiler to make a member function inline. [4+4+4+4]
2. What do you mean by run time polymorphism and how to implement run timepolymorphism using virtual functions in C++.[16]
3. (a) How do I use exceptions.
(b) Can I throw an exception from a constructor. From a destructor.
(c) Why doesn’t C++ provide a “finally" construct.
(d) What is an autoptr and why isn’t there an autoarray.
(e) Why can’t I resume after catching an exception.[3+3+3+3+4]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. (a) Explain the linear probing method in Hashing. Explain its performance analy-sis.
(b) What is hashing with Chains. Explain. Compare this with Linear Probing.[8+8]
6. (a) Prove that the insertion of a new node in a red-black tree with n nodes in .(logn) time in the worst case.
(b) Derive the amortized complexity of a find, insert or delete operation performedon a splay tree with n elements.[8+8]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.
(b) Explain divide and conquer strategy by means of its control abstraction.(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) What are the general characteristics of greedy algorithms and the problemssolved by these algorithms.
(b) What is 0/1 Knapsack problem. Explain how principle of optimality appliesto it. Also derive its dynamic recurrence relation.[8+8]
1. (a) Explain about the friend function with a suitable example.
(b) Why is it best to use inline functions instead of plain old # define macros.
(c) How to tell the compiler to make a non-member function inline.
(d) How to tell the compiler to make a member function inline. [4+4+4+4]
2. What do you mean by run time polymorphism and how to implement run timepolymorphism using virtual functions in C++.[16]
3. (a) How do I use exceptions.
(b) Can I throw an exception from a constructor. From a destructor.
(c) Why doesn’t C++ provide a “finally" construct.
(d) What is an autoptr and why isn’t there an autoarray.
(e) Why can’t I resume after catching an exception.[3+3+3+3+4]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. (a) Explain the linear probing method in Hashing. Explain its performance analy-sis.
(b) What is hashing with Chains. Explain. Compare this with Linear Probing.[8+8]
6. (a) Prove that the insertion of a new node in a red-black tree with n nodes in .(logn) time in the worst case.
(b) Derive the amortized complexity of a find, insert or delete operation performedon a splay tree with n elements.[8+8]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.
(b) Explain divide and conquer strategy by means of its control abstraction.(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) What are the general characteristics of greedy algorithms and the problemssolved by these algorithms.
(b) What is 0/1 Knapsack problem. Explain how principle of optimality appliesto it. Also derive its dynamic recurrence relation.[8+8]
1II B.Tech I Semester Supplementary Examinations, February 2007ADVANCED DATA STRUCTURES & ALGORITHMS
Code No: R059211201Set No. 1II B.Tech I Semester Supplementary Examinations, February 2007ADVANCED DATA STRUCTURES & ALGORITHMS( Common to Information Technology and Computer Science & SystemsEngineering)Time: 3 hoursMax Marks: 80Answer any FIVE QuestionsAll Questions carry equal marks. . . . .
1. (a) What do you mean by Data abstraction.
(b) Di.erence between “C structure" and “C++ structure"..
(c) Di.rence between a “assignment operator" and a “copy constructor".
(d) What is the di.erence between overloading and “overridding". [4+4+4+4]
2. (a) What is multilevel inheritance. Write a program to illustrate the concept ofMultilevel Inheritance.
(b) What is Hybrid inheritance. Write a program to illustrate the concept ofHybrid Inheritance.[8+8]
3. What is an Error and Exception. Explain the exception handling mechanism inC++ .[16]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]6. (a) Write a method to delete the pair with the largest key from a Binary SearchTree.(b) Write a method to find the height of a Binary Search Tree.[8+8]
7. Write and explain an algorithm to determine if the AND/OR tree T is solvable.[16]8. (a) Write a linear time algorithm that generates the OBST from the root table.(b) Prove that the greedy method always obtains an optimal solution to the job-sequencing problem.[8+8]
1. (a) What do you mean by Data abstraction.
(b) Di.erence between “C structure" and “C++ structure"..
(c) Di.rence between a “assignment operator" and a “copy constructor".
(d) What is the di.erence between overloading and “overridding". [4+4+4+4]
2. (a) What is multilevel inheritance. Write a program to illustrate the concept ofMultilevel Inheritance.
(b) What is Hybrid inheritance. Write a program to illustrate the concept ofHybrid Inheritance.[8+8]
3. What is an Error and Exception. Explain the exception handling mechanism inC++ .[16]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]6. (a) Write a method to delete the pair with the largest key from a Binary SearchTree.(b) Write a method to find the height of a Binary Search Tree.[8+8]
7. Write and explain an algorithm to determine if the AND/OR tree T is solvable.[16]8. (a) Write a linear time algorithm that generates the OBST from the root table.(b) Prove that the greedy method always obtains an optimal solution to the job-sequencing problem.[8+8]
4II B.Tech I Semester Regular Examinations, November 2006ADVANCED DATA STRUCTURES & ALGORITHMS
Code No: R059211201Set No. 4II B.Tech I Semester Regular Examinations, November 2006ADVANCED DATA STRUCTURES & ALGORITHMS( Common to Information Technology and Computer Science & SystemsEngineering)Time: 3 hoursMax Marks: 80Answer any FIVE QuestionsAll Questions carry equal marks. . . . .
1. (a) What is the di.erence between global static functions and static functions,class members.
(b) What is common and what is the di.erence between implementations of thecopy constructors, initialization and overloaded assignment operators.
(c) What is the di.erence between modifiers register, const and volatile. [5+5+6]
2. (a) Write a program to illustrate the concept of virtual base class with exampleprogram.
(b) How to implement run time polymorphism using virtual functions. [8+8]
3. (a) Explain about console I/O and formatted I/O streams in C++.
(b) Write a program to count the no of lines in given text file.[8+8]
4. Write and explain UNION and find algorithms with weighting and collapsing rule.[16]
5. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]
6. Define a Binary Search Tree. Write the procedures to perform insertion, deletionand searching in a binary search tree.[16]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.
(b) Explain divide and conquer strategy by means of its control abstraction.
(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) What are the general characteristics of greedy algorithms and the problemssolved by these algorithms.
(b) What is 0/1 Knapsack problem. Explain how principle of optimality appliesto it. Also derive its dynamic recurrence relation.[8+8]
1. (a) What is the di.erence between global static functions and static functions,class members.
(b) What is common and what is the di.erence between implementations of thecopy constructors, initialization and overloaded assignment operators.
(c) What is the di.erence between modifiers register, const and volatile. [5+5+6]
2. (a) Write a program to illustrate the concept of virtual base class with exampleprogram.
(b) How to implement run time polymorphism using virtual functions. [8+8]
3. (a) Explain about console I/O and formatted I/O streams in C++.
(b) Write a program to count the no of lines in given text file.[8+8]
4. Write and explain UNION and find algorithms with weighting and collapsing rule.[16]
5. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]
6. Define a Binary Search Tree. Write the procedures to perform insertion, deletionand searching in a binary search tree.[16]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.
(b) Explain divide and conquer strategy by means of its control abstraction.
(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) What are the general characteristics of greedy algorithms and the problemssolved by these algorithms.
(b) What is 0/1 Knapsack problem. Explain how principle of optimality appliesto it. Also derive its dynamic recurrence relation.[8+8]
3II B.Tech I Semester Regular Examinations, November 2006ADVANCED DATA STRUCTURES & ALGORITHMS
Code No: R059211201Set No. 3II B.Tech I Semester Regular Examinations, November 2006ADVANCED DATA STRUCTURES & ALGORITHMS( Common to Information Technology and Computer Science & SystemsEngineering)Time: 3 hoursMax Marks: 80Answer any FIVE QuestionsAll Questions carry equal marks. . . . .
1. (a) What do you mean by Stack unwinding.
(b) What is the di.erence between const char *myPointer and char *const
(c) Define precondition and post-condition to a member function.
(d) What are the conditions that have to be met for a condition to be an invariantof the class.[4+4+4+4]
2. (a) Explain the need for “Virtual Destructor".
(b) Can we have “Virtual Constructors".[8+8]
3. (a) What are some ways try / catch / throw can improve software quality.
(b) How can we handle a constructor that fails.
(c) How can we handle a destructor that fails.[5+5+6]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. What is Hashing. Explain the di.erent Hash table representations in detail. [16]6. Define a class called binarySearchTree to represent a Binary search tree. Extendthis class by adding a public method outputInRange (Low,High) that outputs,in ascending order of key, all elements in a binary search tree whose key lies betweenLow and High. Use recursion and avoid entering sub trees that cannot possiblycontain any elements with keys in desired range.[16]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.(b) Explain divide and conquer strategy by means of its control abstraction.
(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) Explain the Job sequencing with deadlines with an example using the greedyapproach.
(b) Describe the dynamic programming approach for the construction of OBSTfor a set of n keys, if all keys are equally likely to be searched for. [8+8]
1. (a) What do you mean by Stack unwinding.
(b) What is the di.erence between const char *myPointer and char *const
(c) Define precondition and post-condition to a member function.
(d) What are the conditions that have to be met for a condition to be an invariantof the class.[4+4+4+4]
2. (a) Explain the need for “Virtual Destructor".
(b) Can we have “Virtual Constructors".[8+8]
3. (a) What are some ways try / catch / throw can improve software quality.
(b) How can we handle a constructor that fails.
(c) How can we handle a destructor that fails.[5+5+6]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. What is Hashing. Explain the di.erent Hash table representations in detail. [16]6. Define a class called binarySearchTree to represent a Binary search tree. Extendthis class by adding a public method outputInRange (Low,High) that outputs,in ascending order of key, all elements in a binary search tree whose key lies betweenLow and High. Use recursion and avoid entering sub trees that cannot possiblycontain any elements with keys in desired range.[16]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.(b) Explain divide and conquer strategy by means of its control abstraction.
(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) Explain the Job sequencing with deadlines with an example using the greedyapproach.
(b) Describe the dynamic programming approach for the construction of OBSTfor a set of n keys, if all keys are equally likely to be searched for. [8+8]
B.Tech I Semester Regular Examinations, November 2006ADVANCED DATA STRUCTURES & ALGORITHMS
Code No: R059211201Set No. 2II B.Tech I Semester Regular Examinations, November 2006ADVANCED DATA STRUCTURES & ALGORITHMS( Common to Information Technology and Computer Science & SystemsEngineering)Time: 3 hoursMax Marks: 80Answer any FIVE QuestionsAll Questions carry equal marks. . . . .
1. (a) What are the two steps that happen with delete p.
(b) What are the advantages of new operator than malloc in C.
(c) Explain about the C++ classes in detail and design a class for playing cards.[5+5+6]
2. What is template. Explain about function templates and class templates withsuitable examples.[16]
3. (a) Write a program to change the case of each word in a file to initial capitals.(b) Write a program to concatenate the two given strings.[8+8]
4. What are the di.erent mathematical notations used for algorithm analysis. 16]
5. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]6. What is an AVL Tree. Write the algorithm to search for an element of an AVLSearch Tree. What is its time complexity.[16]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.
(b) Explain divide and conquer strategy by means of its control abstraction.
(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) What are the general characteristics of greedy algorithms and the problemssolved by these algorithms.
(b) What is 0/1 Knapsack problem. Explain how principle of optimality appliesto it. Also derive its dynamic recurrence relation.[8+8]
1. (a) What are the two steps that happen with delete p.
(b) What are the advantages of new operator than malloc in C.
(c) Explain about the C++ classes in detail and design a class for playing cards.[5+5+6]
2. What is template. Explain about function templates and class templates withsuitable examples.[16]
3. (a) Write a program to change the case of each word in a file to initial capitals.(b) Write a program to concatenate the two given strings.[8+8]
4. What are the di.erent mathematical notations used for algorithm analysis. 16]
5. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]6. What is an AVL Tree. Write the algorithm to search for an element of an AVLSearch Tree. What is its time complexity.[16]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.
(b) Explain divide and conquer strategy by means of its control abstraction.
(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) What are the general characteristics of greedy algorithms and the problemssolved by these algorithms.
(b) What is 0/1 Knapsack problem. Explain how principle of optimality appliesto it. Also derive its dynamic recurrence relation.[8+8]
II B.Tech I Semester Regular Examinations, November 2006
Code No: R059211201Set No. 1 II B.Tech I Semester Regular Examinations, November 2006ADVANCED DATA STRUCTURES & ALGORITHMS( Common to Information Technology and Computer Science & SystemsEngineering)Time: 3 hoursMax Marks: 80Answer any FIVE QuestionsAll Questions carry equal marks. . . . .
1.
(a) What is the default data hiding type for a class. Why are data membershidden. How would you access them.
(b) In a printf statement, what are the codes for integer. .oat. string. How canyou choose how many numbers occur before and after the decimal point fora .oat. How can you pad zeroes to the beginning of an integer to make it aspecific length.[8+8]
2. What do you mean by run time polymorphism and how to implement run timepolymorphism using virtual functions in C++.[16]
3. (a) What are some ways try / catch / throw can improve software quality.(b) How can we handle a constructor that fails.(c) How can we handle a destructor that fails.[5+5+6]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]6. What is an AVL Tree. Write the algorithm to search for an element of an AVLSearch Tree. What is its time complexity.[16]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.
(b) Explain divide and conquer strategy by means of its control abstraction.(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) Explain the Job sequencing with deadlines with an example using the greedyapproach
1.
(a) What is the default data hiding type for a class. Why are data membershidden. How would you access them.
(b) In a printf statement, what are the codes for integer. .oat. string. How canyou choose how many numbers occur before and after the decimal point fora .oat. How can you pad zeroes to the beginning of an integer to make it aspecific length.[8+8]
2. What do you mean by run time polymorphism and how to implement run timepolymorphism using virtual functions in C++.[16]
3. (a) What are some ways try / catch / throw can improve software quality.(b) How can we handle a constructor that fails.(c) How can we handle a destructor that fails.[5+5+6]
4. (a) What are the applications of stack explain with an example.
(b) Explain the list representation of a tree by means of an example.
(c) Mention some common computing times for algorithms in order of increasingdi.culty.[5+5+6]
5. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]6. What is an AVL Tree. Write the algorithm to search for an element of an AVLSearch Tree. What is its time complexity.[16]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.
(b) Explain divide and conquer strategy by means of its control abstraction.(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) Explain the Job sequencing with deadlines with an example using the greedyapproach
Saturday, October 6, 2007
Algorithm for DFS
Algorithm DFS(v)
//Given an undirected (directed) graph
//G=(v,E) with n vertices and an array visited[] initially set to zero
//ther algorithm visits all vertices reachable from v. G and visited are global.
{
visited[v]:=1;
for each vertex w adjacent from v do
{
if(visited[w]=0) then DFS(w);
}
}
//Given an undirected (directed) graph
//G=(v,E) with n vertices and an array visited[] initially set to zero
//ther algorithm visits all vertices reachable from v. G and visited are global.
{
visited[v]:=1;
for each vertex w adjacent from v do
{
if(visited[w]=0) then DFS(w);
}
}
Algorithm for BFS
Algorithm BFS(v)
//A breadth first search of G is carried out begining at vertex v. For any node i
//visited[i]=1 if i has already been visited. The graphs G and arry visited are
//global, visited is initialized to zero
{
u:=v;//q is a queue of unexplored vertices
visit[v]:=1;
repeat
{
for all vertices w adjacent from u do
{
if(visited[w]=0) then
{
Add w to q;//w is unexplored
visited[w]:=1;
}
}
if q is empty then return;
delete u from q;
}until(false);
}
Algorithm BFT(G,n)
//Breath first traversal of G
{
for i:=1 to n do //Mark all vertices on visited
visit[i]:=0;
for i:=1 to n do if(visited[i]=0) then BFS(i);
}
//A breadth first search of G is carried out begining at vertex v. For any node i
//visited[i]=1 if i has already been visited. The graphs G and arry visited are
//global, visited is initialized to zero
{
u:=v;//q is a queue of unexplored vertices
visit[v]:=1;
repeat
{
for all vertices w adjacent from u do
{
if(visited[w]=0) then
{
Add w to q;//w is unexplored
visited[w]:=1;
}
}
if q is empty then return;
delete u from q;
}until(false);
}
Algorithm BFT(G,n)
//Breath first traversal of G
{
for i:=1 to n do //Mark all vertices on visited
visit[i]:=0;
for i:=1 to n do if(visited[i]=0) then BFS(i);
}
Subscribe to:
Posts (Atom)
