knapscak and graph optimization problems in order to best limit the continued spreadwhich uninfected people should be vaccinatedthis can be formalized as solving min cut problem let na be the set of active tb nodes and no be the set of all the other nodes each edge in the minimum cut between these two sets will contain one person with known active tb and one person without the people without known active tb are candidates for vaccination shortest pathdepth-first search and breadth-first search social networks are made up of individuals and relationships between individuals these are typically modeled as graphs in which the individuals are nodes and the edges relationships if the relationships are symmetricthe edges are undirectedif the relationships are asymmetric the edges are directed some social networks model multiple kinds of relationshipsin which case labels on the edges indicate the kind of relationship in the playwright john guare wrote six degrees of separation the slightly dubious premise underlying the play is that "everybody on this planet is separated by only six other people by this he meant that if one built social network including every person on the earth using the relation "knows,the shortest path between any two individuals would pass through at most six other nodes less hypothetical question is the distance using the "friendrelation between pairs of people on facebook for exampleyou might wonder if you have friend who has friend who has friend who is friend of mick jagger let' think about designing program to answer such questions the friend relation (at least on facebookis symmetrice if stephanie is friend of andreaandrea is friend of stephanie we willthereforeimplement the social network using type graph we can then define the problem of finding the shortest connection between you and mick jagger asfor the graph gfind the shortest sequence of nodespath [you,mick jagger]such that if ni and ni+ are consecutive nodes in paththere is an edge in connecting ni and ni+ figure contains recursive function that finds the shortest path between two nodesstart and endin digraph since graph is subclass of digraphit will work for our facebook problem the algorithm implemented by dfs is an example of recursive depth-firstsearch (dfsalgorithm in generala depth-first-search algorithm begins by choosing one child of the start node it then chooses one child of that node and so ongoing deeper and deeper until it either reaches the goal node or node with no children the search then backtracksreturning to the most recent node with children that it has not yet visited when all paths have been when mark zuckerberg was six years old