1. Code a breadth First traversal.
2. Code a depth First traversal.
Note, your traversals should return a string listing the nodes added to the min spanning tree and the order they are added.
Using Python.
Starter code:
from collections import deque class Edge: def __init__(self, endIndex, next = None): self.endIndex = endIndex self.next = next class Node: def __init__(self, name): self.name = name self.visited = False self.connects = None class Graph: def __init__(self): self.nodeList = [] self.size = 20 self.numNodes = 0 self.edgeMatrix = [] for i in range(self.size): self.edgeMatrix.append([]) for j in range(self.size): self.edgeMatrix[i].append(0) def addNode(self,name): if self.numNodes >= self.size: return False if self.findNode(name) != -1: return False temp = Node(name) self.nodeList.append(temp) self.numNodes += 1 return True def addEdge(self, starts, ends): if starts == ends: return False startIndex = self.findNode(starts) endIndex = self.findNode(ends) if startIndex == -1 or endIndex == -1: return False self.edgeMatrix[startIndex][endIndex] = 1 self.edgeMatrix[endIndex][startIndex] = 1 startEnd = Edge(endIndex) startEnd.next = self.nodeList[startIndex].connects self.nodeList[startIndex].connects = startEnd endStart = Edge(startIndex) endStart.next = self.nodeList[endIndex].connects self.nodeList[endIndex].connects = endStart return True def findNode(self, name): for index in range(self.numNodes): if self.nodeList[index].name == name: return index return -1 def listNodes(self): nodes = "The Nodes are: " for index in range(self.numNodes): nodes += self.nodeList[index].name if index != self.numNodes - 1: nodes += ", " return nodes def displayEdges(self): edges = "The EdgeList is: (Node: its edges)\n" for index in range(self.numNodes): edges += self.nodeList[index].name edges += ": " ptr = self.nodeList[index].connects while ptr: edges += self.nodeList[ptr.endIndex].name edges += " " ptr = ptr.next edges += "\n" return edges def displayMatrix(self): matrix = "The edgeMatrix is: \n " for index in range(self.numNodes): matrix += self.nodeList[index].name matrix += " " matrix += "\n" for index1 in range(self.numNodes): matrix += self.nodeList[index1].name matrix += " " for index2 in range(self.numNodes): matrix += str(self.edgeMatrix[index1][index2]) matrix += " " matrix += "\n" return matrix def resetVisited(self): for index in range(self.numNodes): self.nodeList[index].visited = False # create a min tree with depthFirst Traversal starting at a given node # then lists non-reachable nodes def depthFirst(self, name): tree = "Depth First Traversal starting at " + name + "\n" return tree + "\n" def breadthFirst(self, name): tree = "Breadth First Traversal starting at " + name + "\n" return tree + "\n"
Driver:
from NonDirectedGraph import Graph def main(): #define tree tree = Graph() tree.addNode('A') tree.addNode('C') tree.addNode('T') tree.addNode('Z') tree.addNode('X') tree.addNode('K') tree.addNode('Q') tree.addNode('J') tree.addNode('M') tree.addNode('U') print(tree.listNodes(), end = "\n") tree.addEdge('A', 'C') tree.addEdge('A', 'T') tree.addEdge('A', 'Z') tree.addEdge('X', 'C') tree.addEdge('C', 'K') tree.addEdge('T', 'Q') tree.addEdge('K', 'Q') tree.addEdge('Q', 'J') tree.addEdge('J', 'M') tree.addEdge('Z', 'X') print(tree.displayEdges(), end = "\n") print(tree.displayMatrix(), end = "\n") print(tree.breadthFirst('Q'), end = "\n") print(tree.depthFirst('Q'), end = "\n") if __name__ == '__main__': main()
Breadth First Search Traversal -
# Python3 Program to print BFS traversal
# from a given source vertex. BFS(int s)
# traverses vertices reachable from s.
from collections import defaultdict
# This class represents a directed graph
# using adjacency list representation
class Graph:
# Constructor
def __init__(self):
# default dictionary to store graph
self.graph = defaultdict(list)
# function to add an edge to graph
def addEdge(self,u,v):
self.graph[u].append(v)
# Function to print a BFS of graph
def BFS(self, s):
# Mark all the vertices as not visited
visited = [False] * (len(self.graph))
# Create a queue for BFS
queue = []
# Mark the source node as
# visited and enqueue it
queue.append(s)
visited[s] = True
while queue:
# Dequeue a vertex from
# queue and print it
s = queue.pop(0)
print (s, end = " ")
# Get all adjacent vertices of the
# dequeued vertex s. If a adjacent
# has not been visited, then mark it
# visited and enqueue it
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True
# Driver code
# Create a graph given in
# the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print ("Following is Breadth First Traversal"
" (starting from vertex 2)")
g.BFS(2)
Depth First Search Traversal -
# Python program to print DFS traversal from a
# given given graph
from collections import defaultdict
# This class represents a directed graph using
# adjacency list representation
class Graph:
# Constructor
def __init__(self):
# default dictionary to store graph
self.graph = defaultdict(list)
# function to add an edge to graph
def addEdge(self,u,v):
self.graph[u].append(v)
# A function used by DFS
def DFSUtil(self,v,visited):
# Mark the current node as visited and print it
visited[v]= True
print v,
# Recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
# The function to do DFS traversal. It uses
# recursive DFSUtil()
def DFS(self,v):
# Mark all the vertices as not visited
visited = [False]*(len(self.graph))
# Call the recursive helper function to print
# DFS traversal
self.DFSUtil(v,visited)
# Driver code
# Create a graph given in the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print "Following is DFS from (starting from vertex 2)"
g.DFS(2)
1. Code a breadth First traversal. 2. Code a depth First traversal. Note, your traversals should return a string listing...
Implement the class MaxHeapPriorityQueue as a heap with the following operations: • MaxHeapPriorityQueue() creates a new heap that is empty. It needs no parameters and returns nothing. Note that as discussed in the video lecture, the index range of the array implementation of a heap is 1:n, NOT 0:n-1 • parent(index) returns the value of the parent of heap[index]. index is between 1 and the size of the heap. If index<=1 or index>size of the heap, it returns None •...
PYTHON QUESTION... Building a Binary Tree with extended Binary Search Tree and AVL tree. Create a class called MyTree with the methods __init__(x), getLeft(), getRight(), getData(), insert(x) and getHeight(). Each child should itself be a MyTree object. The height of a leaf node should be zero. The insert(x) method should return the node that occupies the original node's position in the tree. Create a class called MyBST that extends MyTree. Override the method insert(x) to meet the definitions of a...
Below is the Graph file that needs to be modified(using Python3) : #!/usr/bin/python3 # Simple Vertex class class Vertex: """ Lightweight vertex structure for a graph. Vertices can have the following labels: UNEXPLORED VISITED Assuming the element of a vertex is string type """ __slots__ = '_element', '_label' def __init__(self, element, label="UNEXPLORED"): """ Constructor. """ self._element = element self._label = label def element(self): """ Return element associated with this vertex. """ return self._element def getLabel(self): """ Get label assigned to...
PYTHON. Continues off another code. I don't understand this. Someone please help! Comment the lines please so I can understand LinkedList ADT: class myLinkedList: def __init__(self): self.__head = None self.__tail = None self.__size = 0 def insert(self, i, data): if self.isEmpty(): self.__head = listNode(data) self.__tail = self.__head elif i <= 0: self.__head = listNode(data, self.__head) elif i >= self.__size: self.__tail.setNext(listNode(data)) self.__tail = self.__tail.getNext() else: current = self.__getIthNode(i - 1) current.setNext(listNode(data,...
PYTHON. Continues off another code(other code is below). I don't understand this. Someone please help! Comment the lines please so I can understand. There are short and med files lengths for each the list of names/ids and then search id file. These are the input files: https://codeshare.io/aVQd46 https://codeshare.io/5M3XnR https://codeshare.io/2W684E https://codeshare.io/5RJwZ4 LinkedList ADT to store student records(code is below). Using LinkedList ADT instead of the Python List. You will need to use the Student ADT(code is below) Imports the Student class...
(Please help me with Coding in Python3) AVLTree complete the following implementation of the balanced (AVL) binary search tree. Note that you should not be implementing the map-based API described in the plain (unbalanced) BSTree notebook — i.e., nodes in the AVLTree will only contain a single value. class AVLTree: class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def rotate_right(self): n = self.left self.val, n.val = n.val, self.val self.left, n.left, self.right, n.right...
in c++ please program for this code #include <iostream> #include <fstream> #include <string> #include <cstring> // for string tokenizer and c-style string processing #include <algorithm> // max function #include <stdlib.h> #include <time.h> using namespace std; // Extend the code here as needed class BTNode{ private: int nodeid; int data; int levelNum; BTNode* leftChildPtr; BTNode* rightChildPtr; public: BTNode(){} void setNodeId(int id){ nodeid = id; } int getNodeId(){ return nodeid; } void setData(int d){ data = d; } int getData(){ return data;...
Q1. Write a program to simulate a grocery waiting queue. Your program should ask the user if they want to add a customer to the queue, serve the next customer in the queue, or exit. When a customer is served or added to the queue, the program should print out the name of that customer and the remaining customers in the queue. The store has two queues: one is for normal customers, another is for VIP customers. Normal customers can...
Use your Food class, utilities code, and sample data from Lab 1 to complete the following Tasks. def average_calories(foods): """ ------------------------------------------------------- Determines the average calories in a list of foods. foods is unchanged. Use: avg = average_calories(foods) ------------------------------------------------------- Parameters: foods - a list of Food objects (list of Food) Returns: avg - average calories in all Food objects of foods (int) ------------------------------------------------------- """ your code here is the...
ProgramIntro.pngProgramIntro2.pngProgramIntro1.pngProgram1.pngProgram2.pngGraph Class:import java.util.ArrayList;//Graph is a class whose objects represent graphs. public class Graph { ArrayList<Node> nodeList; ArrayList<Edge> edgeList; public Graph() { nodeList = new ArrayList<Node>(); edgeList = new ArrayList<Edge>(); } public ArrayList<Node> getNodeList() { return nodeList; } public ArrayList<Edge> getEdgeList() { return edgeList; } public void addNode(Node n) { nodeList.add(n); } public void addEdge(Edge e) { edgeList.add(e); } public String...