# Algorithms Course – Graph Theory Tutorial from a Google Engineer

1 min read

This full course provides a complete introduction to Graph Theory algorithms in computer science. Knowledge of how to create and design excellent algorithms …

source

Skip to content # Algorithms Course – Graph Theory Tutorial from a Google Engineer

1 min read #### More Stories

## 27 thoughts on “Algorithms Course – Graph Theory Tutorial from a Google Engineer”

### Leave a Reply Cancel reply

#### You may have missed

July 27, 2021

Daily Global New Media

2 months ago freeCodeCamp.org

This full course provides a complete introduction to Graph Theory algorithms in computer science. Knowledge of how to create and design excellent algorithms …

source

Tags: "google" Algorithms algorithms course algorithms for beginners coding interview computer science cracking the coding interview data structures data structures and algorithms Engineer Graph graph theory graph theory course graph theory for beginners graph theory tutorial Java java algorithms java data structures java graph theory Theory tutorial

32:45

4:04 I feel bad for F 🥲

I wanted to know how much this course and concepts are important for fresher with different background coming in as developer.

Hi William,

Could you please explain how you've arrived at these 2 time complexities?

(1) max flow via Edmonds-Karp algo using BFS — O(E^2.V)

(2) max flow via Capacity Scaling algo using DFS — O(E^2.logU)

or cud u pls point at some doc where I can read?

@4:26 Isn't E log E and E log V same?

Because E is of the order of V^2

E log E

=> E log V^2

=> 2 E log V

And in terms of big-oh notation it will be E log V

Resume @ : 27:41

Resume @ : 1:12:35

Resume @ : 1:33:00

Resume @ : 1:54:00

ToDo : 1:43:25 – Dijkstras implementation

ToDo : 2:2:00 – Bellmard-ford implementation

ToDo : 2:20:00 – Floyd Warshall emplementation

Great course!

Playback at 2x for the win

Fantastic video! Thank you!

Maybe Python would be much better choice for this tutorial.

this guy is awesome..He covered almost all the concepts in Graph… really worth it…

Sharing my python code

With few modifications can create a random dungion and solve

It makes the adjacency list also by supplying number of rows and columns

Excludes rock cells

Finds start and end node on its own

import numpy as np

rows=5

columns=7

number_of_nodes=rows*columns

def create_dungeon():

'''

This method creates the dungeon

It returns a numpy array

The below are the representations of the cell

0-EMPTY CELL

1-START

2-END

3-ROCK

Arguments : –

rows :- Number of rows

columns :- Number of columns

start node

end node

number of rocks

'''

dungeon_arr = np.zeros([rows,columns])

dungeon_arr[0,0]=1

dungeon_arr[4,3]=2

dungeon_arr[4,0]=3

dungeon_arr[1,1]=3

dungeon_arr[2,1]=3

dungeon_arr[3,2]=3

dungeon_arr[4,2]=3

dungeon_arr[0,3]=3

dungeon_arr[3,3]=3

dungeon_arr[1,5]=3

dungeon_arr[4,5]=3

dungeon_arr[4,5]=3

return dungeon_arr

dungeon_arr=create_dungeon()

def get_adjacent_cells(curr_row,curr_col,dungeon_arr):

'''

This function is used to get the

adjacent cells assuming we can cannot move diagonally

Arguments :-

Current Row

Current Column

Dungeon Array

'''

dr = [-1,1,0,0]

dc = [0,0,1,-1]

adjacent_cells=[]

for i in range(4):

rr=curr_row+dr[i]

cc=curr_col+dc[i]

if cc < 0 or rr < 0 or rr >= rows or cc >= columns or dungeon_arr[rr,cc]==3:

continue

else:

adjacent_cells.append((rr,cc))

return adjacent_cells

def graph_to_adjacency_list(rows,columns,dungeon_arr):

'''

This function will convert the graph to an adjacency list

'''

graph_dict={}

graph_rev_dict={}

cnt=0

adjacency_list={}

for curr_row in range(rows):

for curr_col in range(columns):

graph_dict[(curr_row,curr_col)]=cnt

graph_rev_dict[cnt]=(curr_row,curr_col)

cnt += 1

for curr_row in range(rows):

for curr_col in range(columns):

adj_neb_idx =[]

adjacent_cells=get_adjacent_cells(curr_row,curr_col,dungeon_arr)

for cell in adjacent_cells:

adj_neb_idx.append(graph_dict[cell])

adjacency_list[graph_dict[curr_row,curr_col]]=adj_neb_idx

result=np.where(dungeon_arr == 1)

start_node=list(zip(result[0], result[1]))

start_node=graph_dict[start_node[0]]

result=np.where(dungeon_arr == 2)

end_node=list(zip(result[0], result[1]))

end_node=graph_dict[end_node[0]]

return adjacency_list,start_node,end_node,graph_rev_dict

adjacency_list,start_node,end_node,graph_rev_dict=graph_to_adjacency_list(rows,columns,dungeon_arr)

def solve(start_node):

global number_of_nodes

global adjacency_list

graph_queue=[]

graph_queue.append(start_node)

visited=[False for i in range(number_of_nodes+1)]

prev=[False for i in range(number_of_nodes+1)]

visited[start_node]=True

while len(graph_queue)!= 0:

curr_node=graph_queue.pop()

neighbours= adjacency_list[curr_node]

for next_node in neighbours:

if not visited[next_node]:

graph_queue.append(next_node)

visited[next_node]=True

prev[next_node]=curr_node

return prev

def reconstrucpath(start_node,end_node,prev):

path=[]

node_at=end_node

while type(node_at) != bool:

path.append(node_at)

node_at=prev[node_at]

return [node for node in reversed(path)]

def bredth_first_search(start_node,end_node):

prev = solve(start_node)

path=reconstrucpath(start_node,end_node,prev)

return path

path = bredth_first_search(start_node,end_node)

for index in path:

print(graph_rev_dict[index])

Output :-

(0, 0)

(0, 1)

(0, 2)

(1, 2)

(1, 3)

(1, 4)

(2, 4)

(3, 4)

(4, 4)

(4, 3)

Every time i come back to your video I want to give you one more like!

A good content is here, but what's the point in making almost 7hr video? It's better divide video on smaller parts and make a playlist with them, than clicking on a timestamp every time.

NO I DONT WANT TO BE A SOFTWAR ENGINEER AT GOOGLE. PLEASE LEAVE ME ALONE ALGO EXPERT. I JUST WANT A LEARN GRAPH THEORY

Pls watch it at 1.5x will save your 3 hrs

thank me later

what language are u using in this video? python and java?

Bridges algo — these also seem to be working? Why can't we do these and further simplify the algo?

(1) if ! visited[to] == true

{ low[at] = min( low[at], ==> low[to] <== ) }

(i.e. same min stmt for 'to' being a visited or an unvisited node)

(2) if ( ==> low[at] <== < low[to] )

to determine if at->lo is a bridge

Point is low[] array is sufficient, and ids[] array seems to be redundant

COMMENTS?

He is such a person <3

what is the difference between algorithms and graph theory? Is graph theory a subsection of algorithms?

Great content sir i just want to ask you like what type of questions could i get in big tech companies like Google or Facebook interview about graphs because it's such a big topic ?

Thank you so much William, for your kind attention to details. I did not receive any teaching on Graph Theory in the 90s when I thought I had graduated. Your patience has made it possible for me to understand a topic that has tremendous value, I believe both for other advanced topics and implementing real-world solutions right away! Thank you, again William!

40:38

yay just coded the first algo here is the ouput

=============================at=============================

0

=============================path=============================

0

=============================at=============================

1

=============================path=============================

0 1

=============================at=============================

8

=============================path=============================

0 1 8

=============================at=============================

7

=============================path=============================

0 1 8 7

=============================at=============================

10

=============================path=============================

0 1 8 7 10

=============================at=============================

11

=============================path=============================

0 1 8 7 10 11

=============================at=============================

3

=============================path=============================

0 1 8 7 3

=============================at=============================

2

=============================path=============================

0 1 8 7 3 2

=============================at=============================

4

=============================path=============================

0 1 8 7 3 4

=============================at=============================

5

=============================path=============================

0 1 8 7 3 5

=============================at=============================

6

=============================path=============================

0 1 8 7 3 5 6

=============================at=============================

9

=============================path=============================

0 9

Thank you for good content! The only thing I want to note is that at 26:50 you have only "visited[at] = true" but you never set it to false, so it will never actually "back track". I believe there is missing "visited[at] = false" right at the end of the function, so we unmark the node when leaving the function.

If the subtitles are available,it'll be great.. I request freecodecamp to add subtitle

I want something related to bipartite, graph coloring concepts

The most hardest part of Developer.