Working on below problem and post problem and my current code. My idea is to always iterate from the minimal in-degree node which has not been visited before. Then based on this node to do a BFS. I am not sure if there are better ways to implement in terms of performance. If you also find any other code issues or bugs, please point them out as well.
Let's suppose that I'd like to spread a promotion message across all people in Twitter. Assuming the ideal case, if a person tweets a message, then every follower will re-tweet the message.
You need to find the minimum number of people to reach out (for example, who doesn't follow anyone etc) so that your promotion message is spread out across entire network in Twitter.
Also, we need to consider loops like, if A follows B, B follows C, C follows D, D follows A (A -> B -> C -> D -> A) then reaching only one of them is sufficient to spread your message.
Input: A 2x2 matrix like below. In this case, a follows b, b follows c, c follows a.
a b c a 1 1 0 b 0 1 1 c 1 0 1
Output: List of people to be reached to spread out message across everyone in the network.
My code ,
# below two connectMatrix are just two test cases, you can use either one for the testing, or use new ones connectMatrix=[ [1,1,0,0], [1,1,1,0], [0,0,1,1], [1,0,0,1] ] connectMatrix=[ [1,1,0], [0,1,1], [1,0,1] ] inDegree =  * len(connectMatrix) visited =  * len(connectMatrix) allVisited = 0 # if (x,y) == 1, it means x follows y # if (x,y) == 1, it means y can send message to x def BFS(connectMatrix, visitedPersons, personID): global allVisited visitQueue =  result =  visitQueue.append(personID) result.append(personID) visitedPersons[personID]=1 allVisited += 1 while len(visitQueue) > 0: personID = visitQueue.pop(0) # downstream: check what other person this person can reach to for i in range(len(connectMatrix)): if connectMatrix[i][personID] == 1 and visitedPersons[i] == 0: visitedPersons[i] = 1 visitQueue.append(i) allVisited += 1 result.append(i) return result if __name__ == "__main__": for j in range (len(connectMatrix)): degree = 0 for i in range(len(connectMatrix)): if connectMatrix[i][j] == 1: degree += 1 inDegree[j] = degree results =  # find non-visited person with minimal in-degree while allVisited < len(connectMatrix): minDegree = max(inDegree) + 1 nextIndex = -1 # find next person to iterate for i in range(len(connectMatrix)): if (visited[i] == 0) and inDegree[i] < minDegree: nextIndex = i minDegree = inDegree[i] results.append(nextIndex) print BFS(connectMatrix, visited, nextIndex) print 'persons to send message, ', results