Transposition sur un graphe orienté

Question

Le problème suivant m'a été attribué, mais j'ai des problèmes pour le trouver. Je sais ce que j'aimerais accomplir, mais étant donné le code du squelette qu'il nous a décrit, je ne sais pas trop par où commencer ... J'ai dessiné une photo pour illustrer ce que j'aimerais accomplir (je pense ...)

http://i802.photobucket.com/albums/yy304/Growler2009/Transposing-1.jpg

C'est ce que je dois faire:

Considérons un graphe orienté G (V, a). La transposée de G écrit GT (V; AT) n'est rien de plus que G où tous les arcs ont été transposés, c'est-à-dire que l'origine de l'arc devient la fin et la fin devient l'origine. Dans un sens, GT est la version \ backward "de G. Pour cette question, vous devez implémenter un algorithme qui, donné un graphe orienté, produit sa transposition L'API de l'algorithme est donnée par l'interface suivante:

public interface Transpose<VT,AT> { 
public DIGraph<VT,AT> doIt(DIGraph<VT,AT> src); 
} 

Mettre en œuvre l'algorithme de transposition donné ci-dessus. Vous avez pas de restrictions sur la façon de le faire (sauf qu'il doit fonctionner sur un graphique représenté comme une liste de contiguïté et il ne peut pas modifier le graphique d'origine. Rapport (dans les commentaires) les complexités de l'espace et du temps en grande notation O et brie y justifier (c'est-à-dire, combien de temps faut-il et combien d'espace utilise-t-il pour transposer un graphique h n sommets et m arcs).

Toute aide que vous pouvez me proposer pour commencer serait formidable.

Merci!

Answer 1

dans pseudolanguagecode:

create new empty set of edges E 
for I in all edges: 
    (X,Y) = vertices of edge I ; 
    insert edge (Y,X) to E; 
result is in E. 

complexité spatiale: aucune exigence

complexité Temps: (num.) Des arêtes O