Quel est le temps de la complexité de BFS selon la représentation du graphe?

La complexité de BFS mis en œuvre à l'aide d'une Matrice de Contiguïté O(|V|²). Et que lors de la mise en œuvre par une Liste d'Adjacence est O(|V| + |E|).

Pourquoi est-il plus dans le cas de la Matrice de Contiguïté?

C'est principalement parce que chaque fois que nous voulons trouver quels sont les bords adjacents à un sommet 'U', on aurait à parcourir l'ensemble du tableau AdjacencyMatrix[U], qui est bien sûr de la longueur |V|.

Imaginer la BFS progression de frontières. Vous prenez un départ vertex S, qui est au niveau 0. Tous les sommets sont adjacents au niveau 1. Ensuite, nous marquer tous les sommets adjacents de tous les sommets au niveau 1, qui n'ont pas un niveau, au niveau 2. Donc, tous les sommets appartiennent à une frontière (ou le niveau). Et quand un élément est dans un frontalier, nous vérifions une fois de ses sommets adjacents, qui prend O(|V|). Aussi, la frontière couvre |V| éléments au cours de l'algorithme, le temps total deviendrait O(|V| * |V|), qui est en O(|V|²).

La complexité différence dans BFS lors de la mise en œuvre par des Listes d'Adjacence et de la Matrice se produit en raison de ce fait que, dans la Matrice de Contiguïté, de dire quels sont les nœuds adjacents à un sommet, nous prenons en O(|V|) moment, indépendamment de bords. Alors que, dans la Contiguïté de la Liste, il est immédiatement disponible pour nous, il faut du temps proportionnel à la distance entre deux sommets, qui, lui, sur la sommation sur tous les sommets |V| est |E|. Donc, BFS par Liste d'Adjacence donne O(|V| + |E|).

OriginalL'auteur Vamsi Sangam

Examinons tout d'abord la complexité du temps. Si une matrice de contiguïté peut être stocké comme sparse matrix, l'espace de la complexité serait le même . Une matrice creuse essentiellement stocke uniquement les valeurs non nulles de la matrice de contiguïté, a donc le même espace de la complexité comme une liste d'adjacence de la représentation, i.e. O(|V| + |E|)

Maintenant, à l'heure de la complexité. Une façon de le faire d'une SECTION de recherche est d'utiliser simplement un clairsemée matrice de contiguïté, comme on le ferait normalement utiliser une liste d'adjacence de la représentation, i.e. O(|V| + |E|).

Une autre façon de faire un BFS sur une matrice de contiguïté est par l'utilisation de matrices creuses-vecteur de multiplications par des à plusieurs reprises l'application de Y=G X, où G est un clairsemée matrice de contiguïté et X est un clairsemée de vecteur avec des 1 sur la frontière. Cette opération est essentiellement une combinaison de colonnes de G. Si cette opération est mise en œuvre, de sorte que chaque multiplication prend du temps proportionnel à la taille des données accessibles dans chaque colonne de G et le nombre de nonzeros dans le vecteur X, alors la complexité du temps serait également en O(|V| + |E|). Un avantage de cette approche est qu'elle est bien en avant de l'étendre à plusieurs BFS recherches en remplaçant X par une matrice creuse représentant les frontières de plusieurs BFS recherches. Plus de détails peuvent être vus dans cette papier sur des implémentations des algorithmes de graphes à l'aide de matrices creuses.

Un bord liste n'est généralement pas utilisé pour le BFS, car il est coûteux de trouver les voisins d'un sommet.

OriginalL'auteur hakeem