A Graph is a mathematical structure defined by a set of vertices V connected by edges E, where the distance from vertex u to vertex v is E[u][v]. A Graph can be directed or undirected. Graph objects support the following methods:
count_components()
Return the number of connected components.
def numIslands(grid):
return to_graph(grid, color='1').count_components()import collections
import itertools
def findCircleNum(M):
V = set(range(len(M)))
E = collections.defaultdict(dict)
for i, j in itertools.permutations(V, 2):
if M[i][j]:
E[i][j] = 1
return Graph(V, E, directed=False).count_components()dijkstra(source, trace=False)
Apply Dijkstra's algorithm. Return a dictionary in the form of {u: distance} where there is some distance from vertex source to vertex u. If trace is True, instead return a dictionary in the form of {u: [[source...u]]} where each list in the value is a path from source to u.
import collections
def networkDelayTime(times, N, K):
E = collections.defaultdict(dict)
for u, v, w in times:
E[u][v] = w
time = max(Graph(set(range(1, N + 1)), E).dijkstra(K).values())
return int(time) if time < float('inf') else -1import collections
import itertools
def numBusesToDestination(routes, S, T):
E = collections.defaultdict(dict)
for route in routes:
for u, v in itertools.permutations(route, 2):
if u != v:
E[u][v] = 1
dist = Graph(set(itertools.chain(*routes)), E).dijkstra(S)
return dist[T] if T in dist and T < float('inf') else -1import collections
def snakesAndLadders(board):
arr = []
while board:
arr += board.pop()
if board: arr += board.pop()[::-1]
m = len(arr)
V = set(range(m))
E = collections.defaultdict(dict)
for u in V:
for i in range(1, 7):
v = u + i
if v < m:
if arr[v] == -1:
E[u][v] = 1
else: E[u][arr[v] - 1] = 1
moves = Graph(V, E).dijkstra(0)[m - 1]
return moves if moves < float('inf') else -1def shortestPathBinaryMatrix(grid):
dist = to_graph(grid, color=0, k=8).dijkstra((0, 0))
m = len(grid) - 1
k = m, m
return dist[k] + 1 if k in dist and dist[k] < float('inf') else -1Shortest Path with Alternating Colors
import collections
def shortestAlternatingPaths(n, red_edges, blue_edges):
r = range(n)
V = set()
for X in r:
V.add((X, 'red'))
V.add((X, 'blue'))
E = collections.defaultdict(dict)
for u, v in red_edges:
E[(u, 'red')][(v, 'blue')] = 1
for u, v in blue_edges:
E[(u, 'blue')][(v, 'red')] = 1
graph = Graph(V, E)
start_red, start_blue = graph.dijkstra((0, 'red')), graph.dijkstra((0, 'blue'))
answer = []
for X in r:
u, v = (X, 'red'), (X, 'blue')
length = min(start_red[u], start_red[v], start_blue[u], start_blue[v])
answer += [length if length < float('inf') else -1]
return answerimport collections
def canReach(arr, start):
E = collections.defaultdict(dict)
for i, x in enumerate(arr):
j = i + x
if j < len(arr):
E[i][j] = 1
j = i - x
if 0 <= j:
E[i][j] = 1
dist = Graph(set(range(len(arr))), E).dijkstra(start)
return any(dist[i] < float('inf') and x == 0 for i, x in enumerate(arr))Time Needed to Inform All Employees
import collections
def numOfMinutes(n, headID, manager, informTime):
E = collections.defaultdict(dict)
for i, x in enumerate(manager):
E[x][i] = float('inf')
for employee in V:
for subordinate in E[employee]:
E[employee][subordinate] = informTime[employee]
return max(Graph(set(range(n)), E).dijkstra(headID).values())bellman_ford(source)
Apply the Bellman-Ford algorithm. Return a collections.defaultdict(dict) object in the form of defaultdict(<class 'dict'>, {u: distance}) where there is some distance from vertex source to vertex u.
floyd_warshall()
Apply the Floyd-Warshall algorithm. Return a dictionary in the form of {u: {v: distance}} where there is some distance from vertex u to vertex v.
Find the City With the Smallest Number of Neighbors at a Threshold Distance
import collections
def findTheCity(n, edges, distanceThreshold):
V = set(range(n))
E = collections.defaultdict(dict)
for from_, to_, weight in edges:
E[from_][to_] = weight
dist = Graph(V, E, directed=False).floyd_warshall()
return min(V, key = lambda y: (sum(map(
lambda x: x <= distanceThreshold, dist[y].values()
)), -y))bipartite()
Return whether the graph is bipartite.
import collections
def isBipartite(graph):
E = collections.defaultdict(dict)
for u, x in enumerate(graph):
for v in x:
E[u][v] = 1
return Graph(set(range(len(graph))), E, directed=False).bipartite()import collections
def possibleBipartition(N, dislikes):
E = collections.defaultdict(dict)
for u, v in dislikes:
E[u][v] = 1
return Graph(set(range(1, N + 1)), E, directed=False).bipartite()kruskal()
Apply Kruskal's algorithm to an undirected graph. Return a minimum spanning tree MST in the form of a collections.defaultdict(dict) object, where the distance from vertex u to vertex v is MST[u][v].
toposort()
Return a topological sort of the graph. If the graph has cycles, return None.
import collections
def canFinish(numCourses, prerequisites):
E = collections.defaultdict(dict)
for v, u in prerequisites:
E[u][v] = 1
return Graph(set(range(numCourses)), E).toposort() != Noneimport collections
def findOrder(numCourses, prerequisites):
E = collections.defaultdict(dict)
for v, u in prerequisites:
E[u][v] = 1
ordering = Graph(set(range(numCourses)), E).toposort()
return ordering if ordering != None else []prim()
Apply Prim's algorithm to an undirected graph. Return a minimum spanning tree MST in the form of a collections.defaultdict(dict) object MST.
Cheapest Flights Within K Stops
import collections
def findCheapestPrice(n, flights):
E = collections.defaultdict(dict)
for u, v, w in flights:
E[u][v] = w
ordering = Graph(set(range(n)), E, False).prim()
return sum(ordering.values())In a matrix, nodes are marked color and are k-directionally connected to their neighbors, where k can be 4 or 8. Given a node at (i, j), return its neighbors.
def updateBoard(board, click):
i, j = click
if board[i][j] == 'M':
board[i][j] = 'X'
elif board[i][j] == 'E':
stack = [(i, j)]
visited = set()
while stack:
i, j = stack.pop()
visited.add((i, j))
m = len(get_neighbors(board, i, j, color='M', k=8))
if m:
board[i][j] = str(m)
else:
board[i][j] = 'B'
for u in get_neighbors(board, i, j, color='E', k=8):
if u not in visited:
stack += [u]
return boardConvert a matrix to a Graph. Each node is marked color and are k-directionally connected to its neighbors, where k can be 4 or 8.
Flood fill a matrix in-place at coordinate (i, j) with color. Update (i, j) with color. Recursively update all k-directionally connected neighbors of (i, j) of the original color with color.
def floodFill(image, sr, sc, newColor):
flood_fill(image, sr, sc, newColor)
return imageFlood fill the border of a matrix with color, where the nodes are k-directionally connected.
def numEnclaves(A):
flood_fill_border(A, 0)
return sum(map(sum, A))def closedIsland(grid):
flood_fill_border(grid, 1)
return to_graph(grid, color=0).count_components()Solve the problem:
Given two words
startandendand a word listbank, find the least number of transformations fromstarttoend, such that only one letter can be changed at a time and each transformed word must exist inbank.startisn't necessarily a transformed word. All words have the same length.
If trace is True, this method will instead output all transformation sequences from start to end.
def findLadders(beginWord, endWord, wordList):
return word_ladder(beginWord, endWord, wordList, trace=True)def findLadderLength(beginWord, endWord, wordList):
length = word_ladder(beginWord, endWord, wordList)
return length + 1 if length < float('inf') else 0def minMutation(start, end, bank):
mutations = word_ladder(start, end, bank)
return mutations if mutations < float('inf') else -1