Test Case Generation | Set 3 (Unweighted and Weighted Trees)
Generating Random Unweighted Trees
- Since this is a tree, the test data generation plan is such that no cycle gets formed.
- The number of edges is one less than the number of vertices
- For each RUN we first print the number of vertices – NUM first in a new separate line and the next NUM-1 lines are of the form (a b) where a is the parent of b
CPP
// A C++ Program to generate test cases for // an unweighted tree #include<bits/stdc++.h> using namespace std; // Define the number of runs for the test data // generated #define RUN 5 // Define the maximum number of nodes of the tree #define MAXNODE 20 class Tree { int V; // No. of vertices // Pointer to an array containing adjacency listss list< int > *adj; // used by isCyclic() bool isCyclicUtil( int v, bool visited[], bool *rs); public : Tree( int V); // Constructor void addEdge( int v, int w); // adds an edge void removeEdge( int v, int w); // removes an edge // returns true if there is a cycle in this graph bool isCyclic(); }; // Constructor Tree::Tree( int V) { this ->V = V; adj = new list< int >[V]; } void Tree::addEdge( int v, int w) { adj[v].push_back(w); // Add w to v’s list. } void Tree::removeEdge( int v, int w) { list< int >::iterator it; for (it=adj[v].begin(); it!=adj[v].end(); it++) { if (*it == w) { adj[v].erase(it); break ; } } return ; } // This function is a variation of DFSUytil() in bool Tree::isCyclicUtil( int v, bool visited[], bool *recStack) { if (visited[v] == false ) { // Mark the current node as visited and part of // recursion stack visited[v] = true ; recStack[v] = true ; // Recur for all the vertices adjacent to this vertex list< int >::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { if (!visited[*i] && isCyclicUtil(*i, visited, recStack)) return true ; else if (recStack[*i]) return true ; } } recStack[v] = false ; // remove the vertex from recursion stack return false ; } // Returns true if the graph contains a cycle, else false. // This function is a variation of DFS() in bool Tree::isCyclic() { // Mark all the vertices as not visited and not part of recursion // stack bool *visited = new bool [V]; bool *recStack = new bool [V]; for ( int i = 0; i < V; i++) { visited[i] = false ; recStack[i] = false ; } // Call the recursive helper function to detect cycle in different // DFS trees for ( int i = 0; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true ; return false ; } int main() { set<pair< int , int >> container; set<pair< int , int >>::iterator it; // Uncomment the below line to store // the test data in a file // freopen ("Test_Cases_Unweighted_Tree.in", "w", stdout); //For random values every time srand ( time (NULL)); int NUM; // Number of Vertices/Nodes for ( int i=1; i<=RUN; i++) { NUM = 1 + rand () % MAXNODE; // First print the number of vertices/nodes printf ( "%d\n" , NUM); Tree t(NUM); // Then print the edges of the form (a b) // where 'a' is parent of 'b' for ( int j=1; j<=NUM-1; j++) { int a = rand () % NUM; int b = rand () % NUM; pair< int , int > p = make_pair(a, b); t.addEdge(a, b); // Search for a random "new" edge everytime while (container.find(p) != container.end() || t.isCyclic() == true ) { t.removeEdge(a, b); a = rand () % NUM; b = rand () % NUM; p = make_pair(a, b); t.addEdge(a, b); } container.insert(p); } for (it=container.begin(); it!=container.end(); ++it) printf ( "%d %d\n" , it->first, it->second); container.clear(); printf ( "\n" ); } // Uncomment the below line to store // the test data in a file // fclose(stdout); return (0); } |
Java
import java.util.*; public class UnweightedTreeTestCasesGenerator { static final int RUN = 5 ; // Number of test cases to generate static final int MAXNODE = 20 ; // Maximum number of nodes in the tree static class Tree { int V; // Number of vertices (nodes) in the tree List<Integer>[] adj; // Adjacency list to represent the tree structure // Helper method to check if there is a cycle in the tree boolean isCyclicUtil( int v, boolean [] visited, boolean [] recStack) { if (!visited[v]) { visited[v] = true ; recStack[v] = true ; // Recur for all the vertices adjacent to this vertex for ( int i : adj[v]) { if (!visited[i] && isCyclicUtil(i, visited, recStack)) return true ; else if (recStack[i]) return true ; } } recStack[v] = false ; // Remove the vertex from the recursion stack return false ; } // Constructor to initialize the tree with a given number of vertices public Tree( int V) { this .V = V; adj = new ArrayList[V]; for ( int i = 0 ; i < V; i++) adj[i] = new ArrayList<>(); } // Method to add an edge between two vertices in the tree public void addEdge( int v, int w) { adj[v].add(w); } // Method to remove an edge between two vertices in the tree public void removeEdge( int v, int w) { adj[v].remove(Integer.valueOf(w)); } // Method to check if the tree has a cycle public boolean isCyclic() { boolean [] visited = new boolean [V]; boolean [] recStack = new boolean [V]; Arrays.fill(visited, false ); Arrays.fill(recStack, false ); // Call the recursive helper function to detect cycle in different DFS trees for ( int i = 0 ; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true ; return false ; } } public static void main(String[] args) { HashSet<Pair<Integer, Integer>> container = new HashSet<>(); // Set to store pairs of vertices Random rand = new Random(); for ( int i = 1 ; i <= RUN; i++) { int NUM = rand.nextInt(MAXNODE) + 1 ; // Randomly choose the number of nodes in the tree System.out.println(NUM); Tree t = new Tree(NUM); // Create a new tree with the specified number of nodes for ( int j = 1 ; j <= NUM - 1 ; j++) { int a = rand.nextInt(NUM); int b = rand.nextInt(NUM); Pair<Integer, Integer> p = new Pair<>(a, b); // Create a pair of vertices t.addEdge(a, b); // Add an edge between vertices a and b in the tree // Check if the pair is already used or if adding the edge creates a cycle while (container.contains(p) || t.isCyclic()) { t.removeEdge(a, b); // Remove the edge to avoid a cycle a = rand.nextInt(NUM); b = rand.nextInt(NUM); p = new Pair<>(a, b); // Generate a new pair t.addEdge(a, b); // Add the edge to the tree } container.add(p); // Add the pair to the set } for (Pair<Integer, Integer> p : container) System.out.println(p.getFirst() + " " + p.getSecond()); container.clear(); // Clear the set for the next test case System.out.println(); } } static class Pair<T, U> { private T first; private U second; public Pair(T first, U second) { this .first = first; this .second = second; } public T getFirst() { return first; } public U getSecond() { return second; } } } |
Python3
import random class Tree: def __init__( self , V): self .V = V self .adj = {i: [] for i in range (V)} # Initialize adjacency list for vertices def add_edge( self , v, w): self .adj[v].append(w) # Add edge from v to w def remove_edge( self , v, w): if w in self .adj[v]: self .adj[v].remove(w) # Remove edge from v to w if it exists def is_cyclic_util( self , v, visited, rec_stack): if not visited[v]: visited[v] = True rec_stack[v] = True for i in self .adj[v]: if not visited[i] and self .is_cyclic_util(i, visited, rec_stack): return True elif rec_stack[i]: return True rec_stack[v] = False return False def is_cyclic( self ): visited = [ False ] * self .V rec_stack = [ False ] * self .V for i in range ( self .V): if self .is_cyclic_util(i, visited, rec_stack): return True return False # Define the number of runs for the test data generated RUN = 5 # Define the maximum number of nodes of the tree MAXNODE = 20 for _ in range (RUN): NUM = random.randint( 1 , MAXNODE) # Generate a random number of nodes for the tree print (NUM) # Print the number of nodes t = Tree(NUM) # Create a tree with NUM nodes container = set () # Create a set to store unique edges for j in range ( 1 , NUM): a = random.randint( 0 , NUM - 1 ) # Generate random node 'a' b = random.randint( 0 , NUM - 1 ) # Generate random node 'b' p = (a, b) # Create a tuple representing the edge t.add_edge(a, b) # Add edge between 'a' and 'b' to the tree while p in container or t.is_cyclic(): # Check for cyclic behavior or duplicate edge t.remove_edge(a, b) # If cyclic or duplicate, remove the edge a = random.randint( 0 , NUM - 1 ) # Generate new random 'a' b = random.randint( 0 , NUM - 1 ) # Generate new random 'b' p = (a, b) # Create a new tuple representing the edge t.add_edge(a, b) # Add the new edge to the tree container.add(p) # Add the edge to the set of unique edges for edge in container: print (edge[ 0 ], edge[ 1 ]) # Print the unique edges container.clear() # Clear the container set for the next run print () # Print a newline for separation between test cases |
C#
using System; using System.Collections.Generic; namespace UnweightedTreeTestCasesGenerator { class Program { // Define the number of runs for the test data generated const int RUN = 5; // Define the maximum number of nodes of the tree const int MAXNODE = 20; class Tree { int V; List< int >[] adj; // Helper method to check if there is a cycle in the tree bool isCyclicUtil( int v, bool [] visited, bool [] recStack) { if (!visited[v]) { visited[v] = true ; recStack[v] = true ; // Recur for all the vertices adjacent to this vertex foreach ( int i in adj[v]) { if (!visited[i] && isCyclicUtil(i, visited, recStack)) return true ; else if (recStack[i]) return true ; } } recStack[v] = false ; return false ; } // Constructor to initialize the tree with a given number of vertices public Tree( int V) { this .V = V; adj = new List< int >[V]; for ( int i = 0; i < V; i++) adj[i] = new List< int >(); } // Method to add an edge between two vertices in the tree public void addEdge( int v, int w) { adj[v].Add(w); } // Method to remove an edge between two vertices in the tree public void removeEdge( int v, int w) { adj[v].Remove(w); } // Method to check if the tree has a cycle public bool isCyclic() { bool [] visited = new bool [V]; bool [] recStack = new bool [V]; for ( int i = 0; i < V; i++) { visited[i] = false ; recStack[i] = false ; } // Call the recursive helper function to detect cycle in different DFS trees for ( int i = 0; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true ; return false ; } } static void Main( string [] args) { // Set to store pairs of vertices HashSet<Tuple< int , int >> container = new HashSet<Tuple< int , int >>(); Random rand = new Random(); for ( int i = 1; i <= RUN; i++) { int NUM = rand.Next(1, MAXNODE + 1); Console.WriteLine(NUM); Tree t = new Tree(NUM); for ( int j = 1; j <= NUM - 1; j++) { int a = rand.Next(NUM); int b = rand.Next(NUM); Tuple< int , int > p = Tuple.Create(a, b); t.addEdge(a, b); // Check if the pair is already used or if adding the edge creates a cycle while (container.Contains(p) || t.isCyclic()) { t.removeEdge(a, b); a = rand.Next(NUM); b = rand.Next(NUM); p = Tuple.Create(a, b); t.addEdge(a, b); } container.Add(p); } // Print the pairs of vertices foreach (Tuple< int , int > p in container) Console.WriteLine($ "{p.Item1} {p.Item2}" ); container.Clear(); // Clear the set for the next test case Console.WriteLine(); } } } } |
Javascript
class Tree { constructor(V) { this .V = V; // Number of vertices (nodes) in the tree this .adj = new Array(V).fill( null ).map(() => []); // Adjacency list to represent the tree structure } // Helper method to check if there is a cycle in the tree isCyclicUtil(v, visited, recStack) { if (!visited[v]) { visited[v] = true ; recStack[v] = true ; // Recur for all the vertices adjacent to this vertex for (const i of this .adj[v]) { if (!visited[i] && this .isCyclicUtil(i, visited, recStack)) return true ; else if (recStack[i]) return true ; } } recStack[v] = false ; // Remove the vertex from the recursion stack return false ; } // Method to add an edge between two vertices in the tree addEdge(v, w) { this .adj[v].push(w); } // Method to remove an edge between two vertices in the tree removeEdge(v, w) { const index = this .adj[v].indexOf(w); if (index !== -1) { this .adj[v].splice(index, 1); } } // Method to check if the tree has a cycle isCyclic() { const visited = new Array( this .V).fill( false ); const recStack = new Array( this .V).fill( false ); // Call the recursive helper function to detect cycle in different DFS trees for (let i = 0; i < this .V; i++) if ( this .isCyclicUtil(i, visited, recStack)) return true ; return false ; } } function main() { const container = new Set(); // Set to store pairs of vertices const RUN = 5; // Number of test cases to generate const MAXNODE = 20; // Maximum number of nodes in the tree for (let i = 1; i <= RUN; i++) { const NUM = Math.floor(Math.random() * MAXNODE) + 1; // Randomly choose the number of nodes in the tree console.log(NUM); const t = new Tree(NUM); // Create a new tree with the specified number of nodes for (let j = 1; j <= NUM - 1; j++) { let a = Math.floor(Math.random() * NUM); let b = Math.floor(Math.random() * NUM); const p = [a, b]; // Create a pair of vertices t.addEdge(a, b); // Add an edge between vertices a and b in the tree // Check if the pair is already used or if adding the edge creates a cycle while (container.has(p) || t.isCyclic()) { t.removeEdge(a, b); // Remove the edge to avoid a cycle a = Math.floor(Math.random() * NUM); b = Math.floor(Math.random() * NUM); p[0] = a; // Generate a new pair p[1] = b; t.addEdge(a, b); // Add the edge to the tree } container.add(p); // Add the pair to the set } for (const p of container) console.log(p[0] + " " + p[1]); container.clear(); // Clear the set for the next test case console.log(); } } main(); // Pair class class Pair { constructor(first, second) { this .first = first; this .second = second; } } // Example usage const examplePair = new Pair(1, 2); console.log(examplePair.first); // Output: 1 console.log(examplePair.second); // Output: 2 |
Time Complexity : O(V + E)
Space Complexity : O(V)
Generating Random Weighted Trees
- Since this is a tree, the test data generation plan is such that no cycle gets formed.
- The number of edges is one less than the number of vertices
- For each RUN we first print the number of vertices – NUM first in a new separate line and the next NUM-1 lines are of the form (a b wt) where a is the parent of b and the edge has a weight of wt
CPP
// A C++ Program to generate test cases for // an unweighted tree #include<bits/stdc++.h> using namespace std; // Define the number of runs for the test data // generated #define RUN 5 // Define the maximum number of nodes of the tree #define MAXNODE 20 class Tree { int V; // No. of vertices // Pointer to an array containing adjacency listss list< int > *adj; // used by isCyclic() bool isCyclicUtil( int v, bool visited[], bool *rs); public : Tree( int V); // Constructor void addEdge( int v, int w); // adds an edge void removeEdge( int v, int w); // removes an edge // returns true if there is a cycle in this graph bool isCyclic(); }; // Constructor Tree::Tree( int V) { this ->V = V; adj = new list< int >[V]; } void Tree::addEdge( int v, int w) { adj[v].push_back(w); // Add w to v’s list. } void Tree::removeEdge( int v, int w) { list< int >::iterator it; for (it=adj[v].begin(); it!=adj[v].end(); it++) { if (*it == w) { adj[v].erase(it); break ; } } return ; } // This function is a variation of DFSUytil() in bool Tree::isCyclicUtil( int v, bool visited[], bool *recStack) { if (visited[v] == false ) { // Mark the current node as visited and part of // recursion stack visited[v] = true ; recStack[v] = true ; // Recur for all the vertices adjacent to this vertex list< int >::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { if (!visited[*i] && isCyclicUtil(*i, visited, recStack)) return true ; else if (recStack[*i]) return true ; } } recStack[v] = false ; // remove the vertex from recursion stack return false ; } // Returns true if the graph contains a cycle, else false. // This function is a variation of DFS() in bool Tree::isCyclic() { // Mark all the vertices as not visited and not part of recursion // stack bool *visited = new bool [V]; bool *recStack = new bool [V]; for ( int i = 0; i < V; i++) { visited[i] = false ; recStack[i] = false ; } // Call the recursive helper function to detect cycle in different // DFS trees for ( int i = 0; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true ; return false ; } int main() { set<pair< int , int >> container; set<pair< int , int >>::iterator it; // Uncomment the below line to store // the test data in a file // freopen ("Test_Cases_Unweighted_Tree.in", "w", stdout); //For random values every time srand ( time (NULL)); int NUM; // Number of Vertices/Nodes for ( int i=1; i<=RUN; i++) { NUM = 1 + rand () % MAXNODE; // First print the number of vertices/nodes printf ( "%d\n" , NUM); Tree t(NUM); // Then print the edges of the form (a b) // where 'a' is parent of 'b' for ( int j=1; j<=NUM-1; j++) { int a = rand () % NUM; int b = rand () % NUM; pair< int , int > p = make_pair(a, b); t.addEdge(a, b); // Search for a random "new" edge everytime while (container.find(p) != container.end() || t.isCyclic() == true ) { t.removeEdge(a, b); a = rand () % NUM; b = rand () % NUM; p = make_pair(a, b); t.addEdge(a, b); } container.insert(p); } for (it=container.begin(); it!=container.end(); ++it) printf ( "%d %d\n" , it->first, it->second); container.clear(); printf ( "\n" ); } // Uncomment the below line to store // the test data in a file // fclose(stdout); return (0); } |
Java
import java.util.*; class Tree { private int V; // No. of vertices private List<Integer>[] adj; // used by isCyclic() private boolean isCyclicUtil( int v, boolean [] visited, boolean [] recStack) { if (!visited[v]) { visited[v] = true ; recStack[v] = true ; for ( int i : adj[v]) { if (!visited[i] && isCyclicUtil(i, visited, recStack)) return true ; else if (recStack[i]) return true ; } } recStack[v] = false ; return false ; } public Tree( int V) { this .V = V; adj = new ArrayList[V]; for ( int i = 0 ; i < V; i++) { adj[i] = new ArrayList<>(); } } public void addEdge( int v, int w) { adj[v].add(w); } public void removeEdge( int v, int w) { adj[v].remove(Integer.valueOf(w)); } public boolean isCyclic() { boolean [] visited = new boolean [V]; boolean [] recStack = new boolean [V]; for ( int i = 0 ; i < V; i++) { visited[i] = false ; recStack[i] = false ; } for ( int i = 0 ; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true ; return false ; } } public class Main { public static void main(String[] args) { Set<Map.Entry<Integer, Integer>> container = new HashSet<>(); Scanner sc = new Scanner(System.in); // Uncomment the below line to store // the test data in a file // System.setOut(new PrintStream(new FileOutputStream("Test_Cases_Unweighted_Tree.in"))); int RUN = 5 ; // Number of runs for the test data generated int MAXNODE = 20 ; // Maximum number of nodes of the tree for ( int i = 1 ; i <= RUN; i++) { int NUM = 1 + ( int ) (Math.random() * MAXNODE); // First print the number of vertices/nodes System.out.println(NUM); Tree t = new Tree(NUM); // Then print the edges of the form (a b) where 'a' is the parent of 'b' for ( int j = 1 ; j <= NUM - 1 ; j++) { int a = ( int ) (Math.random() * NUM); int b = ( int ) (Math.random() * NUM); Map.Entry<Integer, Integer> p = new AbstractMap.SimpleEntry<>(a, b); t.addEdge(a, b); // Search for a random "new" edge every time while (container.contains(p) || t.isCyclic()) { t.removeEdge(a, b); a = ( int ) (Math.random() * NUM); b = ( int ) (Math.random() * NUM); p = new AbstractMap.SimpleEntry<>(a, b); t.addEdge(a, b); } container.add(p); } for (Map.Entry<Integer, Integer> it : container) System.out.println(it.getKey() + " " + it.getValue()); container.clear(); System.out.println(); } // Uncomment the below line to store // the test data in a file // System.setOut(new PrintStream(new FileOutputStream(FileDescriptor.out))); } } |
Python3
# A Python3 program to generate test cases for # an unweighted tree import random # Define the number of runs for the test data # generated RUN = 5 # Define the maximum number of nodes of the tree MAXNODE = 20 # Define the maximum weight of edges MAXWEIGHT = 200 class Tree: def __init__( self , V): self .V = V self .adj = [[] for i in range (V)] def addEdge( self , v, w): self .adj[v].append(w) def removeEdge( self , v, w): for i in self .adj[v]: if i = = w: self .adj[v].remove(i) break return # This function is a variation of DFSUytil() in def isCyclicUtil( self , v, visited, recStack): visited[v] = True recStack[v] = True # Recur for all the vertices adjacent to this vertex for i in self .adj[v]: if visited[i] = = False and self .isCyclicUtil(i, visited, recStack): return True elif recStack[i]: return True # remove the vertex from recursion stack recStack[v] = False return False # Returns true if the graph contains a cycle, else false. # This function is a variation of DFS() in def isCyclic( self ): # Mark all the vertices as not visited and not part # of recursion stack visited = [ False ] * self .V recStack = [ False ] * self .V # Call the recursive helper function to detect cycle # in different DFS trees for i in range ( self .V): if visited[i] = = False : if self .isCyclicUtil(i, visited, recStack) = = True : return True return False for i in range (RUN): NUM = 1 + random.randint( 0 , MAXNODE - 1 ) # First print the number of vertices/nodes print (NUM) t = Tree(NUM) # Then print the edges of the form (a b) # where 'a' is parent of 'b' for j in range (NUM - 1 ): a = random.randint( 0 , NUM - 1 ) b = random.randint( 0 , NUM - 1 ) t.addEdge(a, b) # Search for a random "new" edge everytime while t.isCyclic() = = True : t.removeEdge(a, b) a = random.randint( 0 , NUM - 1 ) b = random.randint( 0 , NUM - 1 ) t.addEdge(a, b) # Then print the weights of the form (a b wt) for j in range (NUM - 1 ): a = random.randint( 0 , NUM - 1 ) b = random.randint( 0 , NUM - 1 ) wt = 1 + random.randint( 0 , MAXWEIGHT - 1 ) print (f "{a} {b} {wt}" ) print () |
C#
using System; using System.Collections.Generic; class Tree { private int V; // No. of vertices // Pointer to an array containing adjacency lists private List< int >[] adj; // used by isCyclic() private bool IsCyclicUtil( int v, bool [] visited, bool [] recStack) { if (!visited[v]) { // Mark the current node as visited and part of // recursion stack visited[v] = true ; recStack[v] = true ; // Recur for all the vertices adjacent to this vertex foreach ( int i in adj[v]) { if (!visited[i] && IsCyclicUtil(i, visited, recStack)) return true ; else if (recStack[i]) return true ; } } recStack[v] = false ; // remove the vertex from recursion stack return false ; } public Tree( int V) { this .V = V; adj = new List< int >[V]; for ( int i = 0; i < V; i++) { adj[i] = new List< int >(); } } public void AddEdge( int v, int w) { adj[v].Add(w); // Add w to v’s list. } public void RemoveEdge( int v, int w) { adj[v].Remove(w); } // Returns true if the graph contains a cycle, else false. // This function is a variation of DFS() in public bool IsCyclic() { // Mark all the vertices as not visited and not part of recursion // stack bool [] visited = new bool [V]; bool [] recStack = new bool [V]; for ( int i = 0; i < V; i++) { visited[i] = false ; recStack[i] = false ; } // Call the recursive helper function to detect a cycle in different // DFS trees for ( int i = 0; i < V; i++) if (IsCyclicUtil(i, visited, recStack)) return true ; return false ; } } class Program { static void Main() { HashSet<Tuple< int , int >> container = new HashSet<Tuple< int , int >>(); // Uncomment the below line to store // the test data in a file // Console.SetOut(new System.IO.StreamWriter("Test_Cases_Unweighted_Tree.in")); // For random values every time Random rand = new Random(); int RUN = 5; // Number of runs for the test data generated int MAXNODE = 20; // Maximum number of nodes of the tree for ( int i = 1; i <= RUN; i++) { int NUM = 1 + rand.Next(MAXNODE); // First print the number of vertices/nodes Console.WriteLine(NUM); Tree t = new Tree(NUM); // Then print the edges of the form (a b) // where 'a' is the parent of 'b' for ( int j = 1; j <= NUM - 1; j++) { int a = rand.Next(NUM); int b = rand.Next(NUM); Tuple< int , int > tuple = Tuple.Create(a, b); t.AddEdge(a, b); // Search for a random "new" edge every time while (container.Contains(tuple) || t.IsCyclic()) { t.RemoveEdge(a, b); a = rand.Next(NUM); b = rand.Next(NUM); tuple = Tuple.Create(a, b); t.AddEdge(a, b); } container.Add(tuple); } foreach (Tuple< int , int > tuple in container) Console.WriteLine($ "{tuple.Item1} {tuple.Item2}" ); container.Clear(); Console.WriteLine(); } // Uncomment the below line to store // the test data in a file // Console.SetOut(new System.IO.StreamWriter(Console.OpenStandardOutput())); // Console.WriteLine("Test data written to file!"); } } //This code is contributed by Monu Yadav. |
Javascript
class Tree { constructor(V) { this .V = V; // Number of vertices in the tree this .adj = Array.from({ length: V }, () => []); // Adjacency list to store edges } // Function to add an edge between vertices v and w addEdge(v, w) { this .adj[v].push(w); } // Function to remove an edge between vertices v and w removeEdge(v, w) { const index = this .adj[v].indexOf(w); if (index > -1) { this .adj[v].splice(index, 1); } } // Utility function for checking cycle using Depth First Search (DFS) isCyclicUtil(v, visited, recStack) { visited[v] = true ; recStack[v] = true ; for (let i = 0; i < this .adj[v].length; i++) { const node = this .adj[v][i]; if (!visited[node] && this .isCyclicUtil(node, visited, recStack)) { return true ; } else if (recStack[node]) { return true ; } } recStack[v] = false ; return false ; } // Function to check if the tree contains a cycle isCyclic() { const visited = new Array( this .V).fill( false ); const recStack = new Array( this .V).fill( false ); for (let i = 0; i < this .V; i++) { if (!visited[i] && this .isCyclicUtil(i, visited, recStack)) { return true ; } } return false ; } } const RUN = 5; // Number of test runs const MAXNODE = 20; // Maximum number of nodes in the tree const MAXWEIGHT = 200; // Maximum weight of edges for (let i = 0; i < RUN; i++) { const NUM = 1 + Math.floor(Math.random() * MAXNODE); // Randomly select number of vertices console.log(NUM); // Print the number of vertices const t = new Tree(NUM); // Create a new tree instance // Generate edges while avoiding cycles in the tree for (let j = 0; j < NUM - 1; j++) { let a = Math.floor(Math.random() * NUM); let b = Math.floor(Math.random() * NUM); t.addEdge(a, b); // Ensure the tree remains acyclic after adding each edge while (t.isCyclic()) { t.removeEdge(a, b); a = Math.floor(Math.random() * NUM); b = Math.floor(Math.random() * NUM); t.addEdge(a, b); } } // Generate and print edge weights for the tree for (let j = 0; j < NUM - 1; j++) { const a = Math.floor(Math.random() * NUM); const b = Math.floor(Math.random() * NUM); const wt = 1 + Math.floor(Math.random() * MAXWEIGHT); console.log(`${a} ${b} ${wt}`); } console.log(); // Print an empty line between test cases } |
Time Complexity : O(V + E)
Space Complexity : O(V)
If you like w3wiki and would like to contribute, you can also write an article and mail your article to review-team@w3wiki.net. See your article appearing on the w3wiki main page and help other Beginner. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above