graph = defaultdict(set)
graph = defaultdict(dict)
# Here, weight will be value and vertex will be dictionary keys
Consider that you start at node A. The discovery time of this node will be 1 as it is the first node. As we go deep into the graph, keep incrementing this number. When we reach a node which has no outgoing edge, we consider that the discovery of this node is complete, thats when we mark it as finish time. As we come one level up after completed discovery, we still keep on incrementing this time untill the end of algorithm. This time can be imaginary and we dont have to keep track of it. Its just the order in which we discover and finish discovering a node. Thus the source will be the first one to be discovered and last one to be finished in its own tree.
Here,
set , we will have to maintain 3 sets, one each for white, grey and black.According to Algorithm Design-CLRS
TOPOLOGICAL-SORT(G)
1. call DFS(G) to compute finishing times v.f for each vertex v
2. as each vertex is finished, insert it onto the front of a linked list
3. return the linked list of vertices
from collections import defaultdict
class Listnode(object):
def __init__(self,key):
self.key=key
# self.val=val
self.next=None
class Solution(object):
def canFinish(self, n, pres):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
self.graph = defaultdict(set)
for req in pres:
prereq=req[1]
subj=req[0]
self.graph[prereq].add(subj)
self.ordered=Listnode(float("inf"))
self.white= set([i for i in xrange(n)])
self.black=set()
self.cycles=set()
self.grey=set()
for i in xrange(n):
if i in self.white:
self.dfs(i)
# print self.white,self.grey,self.black,self.cycles
return len(self.cycles)==0
def dfs(self,node):
if node in self.black:
return
elif node in self.grey:
self.cycles.add(node)
return
else:
self.white.remove(node)
self.grey.add(node)
for nd in self.graph[node]:
self.dfs(nd)
ll=Listnode(node)
ll.next=self.ordered.next
self.ordered.next=ll
self.grey.remove(node)
self.black.add(node)
return
# Simple application of Topological Sort to detect circles in graph
# 207. Course Schedule on Leetcode
from collections import defaultdict
class Solution(object):
def canFinish(self, N, relations):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
if not relations:
return True
self.graph = defaultdict(set)
for prereq, course in relations:
self.graph[course].add(prereq)
self.depend=[1]*(N) # Stores number of nodes the current node is dependent on
nds=range(0,N) # All the nodes in the graph
self.white= set(nds) # Number of nodes to visit
self.grey=set()
self.black=set()
self.cycle=set()
self.res=[] # Stores topologically sorted order of nodes
for i in nds:
if i in self.white:
self.dfs(i)
return len(self.cycle)==0
def dfs(self,node):
if node in self.grey:
self.cycle.add(node)
return
elif node in self.black:
return
else:
self.white.remove(node)
self.grey.add(node)
for nd in self.graph[node]:
self.depend[node]=max(self.depend[node],self.depend[nd]+1) # Storing the depth of node
self.dfs(nd)
self.grey.remove(node)
self.black.add(node)
self.res.append(node)
SCC - Sub group of vertices where all U -> V are reachable.
* Stage 1:
Run DFS :
get Nodes with highest finish time
* Stage 2:
Run DFS on Graph(V, reverse edges) starting from highest finish time
(Because when we reverse edges, all the cycles can be reached, but all the outside nodes will be cut off)
An Euler tour of a strongly connected, directed graph G = (V,E) is a cycle that traverses each edge of G exactly once, although it may visit a vertex more than once.
# 332. Reconstruct Itinerary on Leetcode
from collections import defaultdict
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
tickets = sorted(tickets)[::-1]
graph = defaultdict(list)
for src,dst in tickets:
graph[src].append(dst)
res=[]
def visit(airport):
while graph[airport]:
visit(graph[airport].pop())
res.append(airport)
visit("JFK")
return res[::-1]
A minimum spanning tree or minimum weight spanning tree is a subset of all the edges of a connected, edge weighted directed graph that connects all the vertices together, without any circle and with minumum possible total edge weight.
Typical use case of Minimum spanning trees is to solve minimum cost problems.
# 1168. Optimize Water Distribution in a Village on Leetcode
class Solution(object):
def minCostToSupplyWater(self, n, wells, pipes):
"""
:type n: int
:type wells: List[int]
:type pipes: List[List[int]]
:rtype: int
"""
graph = []
for i,well in enumerate(wells):
graph.append((well,(0,i+1)))
for pipe in pipes:
graph.append((pipe[2],(pipe[0],pipe[1])))
graph = sorted(graph, key=lambda x:x[0])
data = [i for i in xrange(n+1)]
cost=0
# print graph
for wt, (frm, to) in graph:
retcost=self.union(data,frm,to,wt)
cost+=retcost
# print retcost, frm ,to
# print data, cost
return cost
def find(self,data,i):
if data[i]!=i:
data[i]=self.find(data,data[i])
return data[i]
def union(self,data,i,j,cost):
pi,pj= self.find(data,i), self.find(data,j)
if pi!=pj:
data[pi]=pj
return cost
return 0
# Check if two components are connected. (Not used in this example)
def connected(self,data,i,j):
return self.find(data,i)==self.find(data,j)
Some instances of the single-source shortest-paths problem may include edges whose weights are negative. If the graph G=(V,E) contains no negative- weight cycles reachable from the source s, then for all v belonging to V , the shortest-path weight SP(s,v) remains well defined, even if it has a negative value. If the graph contains a negative-weight cycle reachable from s, however, shortest-path weights are not well defined. No path from s to a vertex on the cycle can be a shortest-path—-we can always find a path with lower weight by following the proposed “shortest” path and then traversing the negative-weight cycle. If there is a negative- weight cycle on some path from s to v, we define SP(s,v)=-infinity
Shortest path of edges of the path are relaxed in path order
ESP(S,V) = SP(S,V) found so far
# S = Starting point
# ESP = Estimated Shortest Path
if ESP(S,V) + E(U,V) < ESP(S,V):
Update(Relax) ESP(S,V) = ESP(S,U)+ESP(U,V)
Optimal Solution Structure
(S)-------(U)-------(V)
If SP(S,V), then SP(S,U) and SP(U,V)
# If this is the given shortest path from (S,V) then, (S,U) is shortest path and (U,V) is shortest path
For each vertex v in G.v
v.d = infinity
v.pi = None
S.d = 0
Here,
S = Source
pi = Parent
d = Distance from S
G = Graph
Relax(u,v,w):
if v.d > (u.d+w(u,v)):
v.d = u.d +w(u,v)
v.pi= u
Here,
u-> source
v-> destination
w-> weight from u to v
The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative.
The Bellman-Ford algorithm returns a boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights.
The algorithm relaxes edges, progressively decreasing an estimate :d on the weight of a shortest path from the source s to each vertex v belonging to V until it achieves the actual shortest-path weight SP(s,v) The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source.
Bellmanford(G,w,s):
InitializeSingleSource(G,s)
for i=1 to |G.V|-1 #-----> i
for each edge(u,v) in G.E:
Relax(u,v,w)
for each edge(u,v) in G.E: # -----> ii
if v.d>u.d+w(u,v):
return False
return True
G.V = Number of vertices
i -> Shortest path from one node to all other nodes in a graph
ii-> Checks if there is any negative edge cycle in the graph, if there is, returns False
n-1 times, where n is number of verticesRun time for BellmanFord is O(VE)
Since the initialization takes O(V) time, each of the |V|-1 passes over the edges takes O(E) time, and the for loop(ii) takes O(E) time.
# 787. Cheapest Flights Within K Stops on Leetcode
from collections import defaultdict
class Solution(object):
def findCheapestPrice(self, n, flights, source, dest, K):
"""
:type n: int
:type flights: List[List[int]]
:type src: int
:type dst: int
:type K: int
:rtype: int
"""
#create graph
graph = defaultdict(dict)
for flight in flights:
src= flight[0]
to= flight[1]
cost=flight[2]
graph[src][to]=cost
#initializeSingleSource
distdict= defaultdict(int)
for i in range(n):
distdict[i]=float("inf")
distdict[source]=0
#BellManFord
for _ in range(n-1):
for fro in graph:
for to in graph[fro]:
newdist= distdict[fro]+graph[fro][to]
distdict[to]=min(newdist,distdict[to])
return -1 if distdict[dest]==float("inf") else distdict[dest]
By relaxing the edges of a weighted dag (directed acyclic graph) G=(V,E) according to a topological sort of its vertices, we can compute shortest paths from a single source in O(V+E) time.
Shortest paths are always well defined in a dag, since even if there are negative-weight edges, no negative-weight cycles can exist.
DAG-Shortest-Paths(G,w,s):
TopologicalSort(G)
InitializeSingleSource(G,s)
for each vertex u, taken in topologically dorted order:
for each vertex v in G.Adj[u]:
Relax(u,v,w)
G.Adj[u]–> Every vertex connected to u
Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted, directed graph G=(V,E) for the case in which all edge weights are nonnegative.
With a good implementation, the running time of Dijkstra’s algorithm is lower than that of the Bellman-Ford algorithm.
Dijkstra(G,w,s):
InitializeSingleSource(G,s)
s = set() # Set, initialize to empty
Q = G.V
while Q != None:
u = ExtractMin(Q) # ---->i
s = S.add(u)
for each vertex v in G.Adj[u]:
Relax(u,v,w)
G.Adj[u]–> Every vertex connected to u
We use priority queues(heaps) to store Q
i -> Extract minimum from Q -(Q holds vertices sorted by their d values). \
# 743. Network Delay Time On Leetcode
from collections import defaultdict
from heapq import *
class Solution(object):
def networkDelayTime(self, times, N, K):
"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
#Create Graph
graph=defaultdict(dict)
for node in times:
src= node[0]
dst=node[1]
wt= node[2]
graph[src][dst]=wt
start=K
dist=[float("inf")]*N
dist[start-1]=0
S=set()
Q=[]
#populate the Q for source
heappush(Q,(0,start))
while Q:
# print Q
wt,u=heappop(Q)
S.add(u)
# Q=[]
for v in graph[u]:
#Relax all vertices
dist[v-1]=min(dist[v-1],dist[u-1]+graph[u][v])
#greedy algo, replace q by greedy vertices for current vertice
if v not in S:
heappush(Q,(graph[u][v],v))
# print dist
return max(dist) if max(dist)<float("inf") else -1