Depth first search in weighted graph using recursion

In a social network, an individual person is a node. Between two people there is an undirected edge because they are mutual friends. When one person tells another person a story, they both know the story. Given timestamp as the time two people meet, timestamp can be seen as the weight of the edge. This post is about depth first search in weighted graph, with timestamp as the weight associated with the edge.

A weighted graph can be represented as a adjacency list. The data structure HashMap is used. The keys are all people who spread the story. The values are the edges from a person (key) to his neighbors. The edges contains the timestamps when two people meet and tell the story. We are going to find out all people who know the story by checking the timestamp.


graph dfs with timestamp

Depth first search uses recursion here. The timestamp’s initial value is 0. It is passed as a parameter of DFS recursive method. In the method, the input timestamp is compared with the timestamp stored within the edge. If the input time is smaller than the edge’s timestamp, that means these two people have the opportunity to tell the story when they meet. This neighbor will be in the group who know the story. Otherwise, he is excluded. At the end, we can find all people who know the story.

Google Interview Question :
When a person who knows it meets any other person, they immediately share the story with them. Initially, only person 1 knows the story. Given a list of meetings between people in a form of (person_1_id, person_2_id, timestamp) construct a list of the persons who will know the story at the very end.

Example: [(1, 2, 100), (3,4, 200), (1,3, 300), (2,5, 400)], 1 // The events could be out of order.
Person 2 will learn the story at the moment 100, person 3 — at the moment 300, person 5 — in the moment 400. Person 4 will never learn the story. So the answer is [1, 2, 3, 5].

Eg2: [(1, 2, 100), (2, 3, 100), (4, 5, 100)], 2
where the first parameter is array of the Persons meet at particular timestamp, second parameter is the PersonId who knows the story first.
Output: [1, 2, 3].

Java

JavaScript

Python

Doodle

graph dfs doodle

Output:
graph:
1-[2 100, 3 300]
2-[1 100, 5 400]
3-[4 200, 1 300]
4-[3 200]
5-[2 400]
People who know story: [1, 2, 3, 5]
graph:
1-[2 100]
2-[1 100, 3 100]
3-[2 100]
4-[5 100]
5-[4 100]
People who know story: [1, 2, 3]

O Notation:
Time complexity: O(V+E)
Space complexity: O(V)
V is total number of people, E is number of connections

How to do depth first search in weighted graph?

The weighted graph is represented as adjacency list. Depth first search uses recursion. The weight will be passed as parameter in the DFS recursive method. Inside the method, the input weight is compared with the weight associated with the edge. If the input is smaller than the edge’s weight, that means these edge is eligible to visit. Otherwise, the edge is excluded. At the end, you will get the visited edges based on the weight comparison.


Download PeopleWhoKnowStoryByTimeStamp.java
Download PeopleWhoKnowStoryByTimeStamp.js
Download PeopleWhoKnowStoryByTimeStamp.py

Comments are closed