Written by CCJ, Monday, Jan 18, 2021 @ Secaucus, NJ, USA.
find a path between two given vertices
Use a stack
S to keep track of the path between the start vertex and the current vertex
stack S to keep track of the path between the start vertex and the current vertex
As soon as a
back edge (v, w) is encountered, we return the
cycle as the protion of the stack from the top to vertex 𝑤w
Shown as below:
Graph in Python can be implemented by
DFS and BFS are implemented below;
# Python3 program to print DFS traversal# from a given given graphfrom collections import defaultdict
# This class represents a directed graph using# adjacency list representationclass Graph: # Constructordef __init__(self):# default dictionary to store graph# Using List as defaultdict's default_factoryself.graph = defaultdict(list) # function to add an edge to graphdef addEdge(self, u, v):self.graph[u].append(v) # A recursive function used by DFSdef DFSUtil(self, v, visited):# Mark the current node as visited and print itvisited[v] = Trueprint(v, end = ' ') # Recur for all the vertices adjacent to this vertexfor 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 visitedvisited = [False] * (max(self.graph)+1) # Call the recursive helper function to print DFS traversalself.DFSUtil(v, visited) # Function to print a BFS of graphdef BFS(self, s): # s is int value;# Mark all the vertices as not visitedvisited = [False] * (len(self.graph)) # Create a queue for BFSqueue =  # Mark the source node as visited and enqueue itqueue.append(s)visited[s] = True while queue:# Dequeue a vertex from queue and print it# current vertex v:# and the first value of v will be the starting node s;v = queue.pop(0)print (v, end = " ") # Get all adjacent vertices of the# dequeued vertex v. If an adjacent# has not been visited, then mark it# visited and enqueue itfor i in self.graph[v]: # for all incidentEdges(v), that is,edge (v, i)if visited[i] == False:queue.append(i)visited[i] = True
A heap is a binary tree storing keys at its internal nodes and satisfying the following properties:
Heap-Order: for every internal node other than the root, key() key(parent()).
Complete Binary Tree: let be the height of the heap
for , there are nodes of depth ;
at depth , the internal nodes are to the left of the external nodes. By saying that all the internal nodes on level are “to the left” of the external nodes, we mean that all the internal nodes on this level will be visited before any external nodes on this level in an inorder traversal.
The last node of a heap is the rightmost internal node of depth h − 1.
insertItem(k): insert a key to the heap.