Plus longue séquence croissante de noeuds dans un graphique

Récemment assisté à une interview MSFT pour SDET position .. L'intervieweur 2ème tour m'a posé cette question: Étant donné un graphique qui a un nombre dans la valeur de noeud, trouver l'ensemble de toute la séquence croissante des sommets qui sont connectés. Pas capable de se rappeler la question exacte .. Le gars semblait très hostile et réfutait chacune de mes solutions .. Toute personne connaissant une telle question .. Enfin la solution était d'avoir une matrice d'adjacence .. Toujours pas sûr de savoir comment cela fonctionneraPlus longue séquence croissante de noeuds dans un graphique

Source

2010-12-10 user138645

Qu'avez-vous proposé? – ruslik

Je m'étais proposé de commencer à traverser le nœud racine .. garder trace des voisins liés .. s'ils forment une séquence, souvenez-vous d'eux .. Marquer également la racine comme visitée ... Faites la même chose maintenant pour chacune des verticies connectées de la racine et ainsi de suite et ainsi de suite .. Il était d'accord mais a dit de le considérer comme des motifs dans une matrice d'adjacence. – user138645

La première étape consiste à transformer les arêtes bidirectionnelles en arêtes directionnelles, en ne faisant que passer du noeud le plus petit au plus grand. Notez que le graphique résultant sera un graphe acyclique dirigé (DAG), car nous ne pouvons pas passer d'un petit-petit-grand nombre à un chemin. À partir de maintenant, nous pouvons ignorer la numérotation des nœuds.

Nous avons maintenant réduit le problème à longest path problem. La solution (décrite en détail dans le lien) consiste à effectuer un tri topologique sur le graphique, puis à utiliser la programmation dynamique pour trouver le chemin le plus long.

Tout cela peut être réalisé en temps linéaire.

Source

2010-12-10 09:04:51 marcog

@Saeed Cela n'est vrai que pour les graphes généraux, pas pour les DAG. Et ma réponse utilise des noeuds numérotés. – marcog

@Seed: les valeurs dans les nœuds sont trivialement équivalentes aux valeurs dans les arêtes. Mais je ne vois pas pourquoi nous parlons du plus long chemin, puisque la question semble demander * tous * les chemins (y compris les sous-chemins). – Beta

@Beta Je l'ai obtenu à partir du titre de la question, mais en relisant le texte de la question, je vois d'où vous venez. Trouver tous les chemins nécessite juste un DFS. – marcog

Plus longue séquence croissante de noeuds dans un graphique

Répondre

Questions connexes