Dans ce didacticiel, vous apprendrez ce qu'est une matrice de contiguïté. Vous trouverez également des exemples pratiques de matrice de contiguïté en C, C ++, Java et Python.
Une matrice de contiguïté est une manière de représenter un graphe G = (V, E) comme une matrice de booléens.
Représentation de la matrice d'adjacence
La taille de la matrice est VxVoù Vest le nombre de sommets dans le graphe et la valeur d'une entrée Aijest 1 ou 0 selon qu'il y a une arête du sommet i au sommet j.
Exemple de matrice d'adjacence
L'image ci-dessous montre un graphique et sa matrice de contiguïté équivalente.
Matrice d'adjacence à partir d'un graphique
Dans le cas de graphes non orientés, la matrice est symétrique par rapport à la diagonale à cause de chaque arête (i,j), il y a aussi une arête (j,i).
Avantages de la matrice de contiguïté
Les opérations de base comme l'ajout d'une arête, la suppression d'une arête et la vérification de l'existence d'une arête entre le sommet i et le sommet j sont des opérations à temps constant extrêmement efficaces en temps.
Si le graphe est dense et que le nombre d'arêtes est grand, la matrice de contiguïté doit être le premier choix. Même si le graphe et la matrice de contiguïté sont clairsemés, nous pouvons le représenter en utilisant des structures de données pour des matrices clairsemées.
Le plus gros avantage vient cependant de l'utilisation de matrices. Les progrès récents du matériel nous permettent d'effectuer des opérations matricielles même coûteuses sur le GPU.
En effectuant des opérations sur la matrice adjacente, nous pouvons obtenir des informations importantes sur la nature du graphe et la relation entre ses sommets.
Inconvénients de la matrice de contiguïté
L' VxVespace requis de la matrice de contiguïté en fait un bourreau de mémoire. Les graphiques à l'état sauvage n'ont généralement pas trop de connexions et c'est la principale raison pour laquelle les listes de contiguïté sont le meilleur choix pour la plupart des tâches.
Alors que les opérations de base sont faciles, les opérations comme inEdgeset outEdgessont coûteuses lors de l'utilisation de la représentation de matrice d'adjacence.
Exemples Python, Java et C / C ++
Si vous savez créer des tableaux à deux dimensions, vous savez également comment créer une matrice de contiguïté.
Python Java C C + # Adjacency Matrix representation in Python class Graph(object): # Initialize the matrix def __init__(self, size): self.adjMatrix = () for i in range(size): self.adjMatrix.append((0 for i in range(size))) self.size = size # Add edges def add_edge(self, v1, v2): if v1 == v2: print("Same vertex %d and %d" % (v1, v2)) self.adjMatrix(v1)(v2) = 1 self.adjMatrix(v2)(v1) = 1 # Remove edges def remove_edge(self, v1, v2): if self.adjMatrix(v1)(v2) == 0: print("No edge between %d and %d" % (v1, v2)) return self.adjMatrix(v1)(v2) = 0 self.adjMatrix(v2)(v1) = 0 def __len__(self): return self.size # Print the matrix def print_matrix(self): for row in self.adjMatrix: for val in row: print('(:4)'.format(val)), print def main(): g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.print_matrix() if __name__ == '__main__': main()
// Adjacency Matrix representation in Java public class Graph ( private boolean adjMatrix()(); private int numVertices; // Initialize the matrix public Graph(int numVertices) ( this.numVertices = numVertices; adjMatrix = new boolean(numVertices)(numVertices); ) // Add edges public void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges public void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the matrix public String toString() ( StringBuilder s = new StringBuilder(); for (int i = 0; i < numVertices; i++) ( s.append(i + ": "); for (boolean j : adjMatrix(i)) ( s.append((j ? 1 : 0) + " "); ) s.append(""); ) return s.toString(); ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); System.out.print(g.toString()); ) )
// Adjacency Matrix representation in C #include #define V 4 // Initialize the matrix to zero void init(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) for (j = 0; j < V; j++) arr(i)(j) = 0; ) // Add edges void addEdge(int arr()(V), int i, int j) ( arr(i)(j) = 1; arr(j)(i) = 1; ) // Print the matrix void printAdjMatrix(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) ( printf("%d: ", i); for (j = 0; j < V; j++) ( printf("%d ", arr(i)(j)); ) printf(""); ) ) int main() ( int adjMatrix(V)(V); init(adjMatrix); addEdge(adjMatrix, 0, 1); addEdge(adjMatrix, 0, 2); addEdge(adjMatrix, 1, 2); addEdge(adjMatrix, 2, 0); addEdge(adjMatrix, 2, 3); printAdjMatrix(adjMatrix); return 0; )
// Adjacency Matrix representation in C++ #include using namespace std; class Graph ( private: bool** adjMatrix; int numVertices; public: // Initialize the matrix to zero Graph(int numVertices) ( this->numVertices = numVertices; adjMatrix = new bool*(numVertices); for (int i = 0; i < numVertices; i++) ( adjMatrix(i) = new bool(numVertices); for (int j = 0; j < numVertices; j++) adjMatrix(i)(j) = false; ) ) // Add edges void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the martix void toString() ( for (int i = 0; i < numVertices; i++) ( cout << i << " : "; for (int j = 0; j < numVertices; j++) cout << adjMatrix(i)(j) << " "; cout << ""; ) ) ~Graph() ( for (int i = 0; i < numVertices; i++) delete() adjMatrix(i); delete() adjMatrix; ) ); int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.toString(); )
Applications de la matrice d'adjacence
- Créer une table de routage dans les réseaux
- Tâches de navigation
