Written by CCJ, Monday, Jan 18, 2021 @ Secaucus, NJ, USA.
find a path between two given vertices u
an z
;
Use a stack S
to keep track of the path between the start vertex and the current vertex
use a 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 defaultdict
;
DFS and BFS are implemented below;
# Python3 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
# Using List as defaultdict's default_factory
self.graph = defaultdict(list)
# function to add an edge to graph
def addEdge(self, u, v):
self.graph[u].append(v)
# A recursive function used by DFS
def DFSUtil(self, v, visited):
# Mark the current node as visited and print it
visited[v] = True
print(v, end = ' ')
# 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] * (max(self.graph)+1)
# Call the recursive helper function to print DFS traversal
self.DFSUtil(v, visited)
# Function to print a BFS of graph
def BFS(self, s): # s is int value;
# 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
# 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 it
for 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.
Method insertItem(k)
: insert a key to the heap.