Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.
Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.
Una de las maneras más fáciles de implementar un grafo es usar una matriz bidimensional. En esta implementación de matriz, cada una de las filas y columnas representa un vértice en el grafo. El valor que se almacena en la celda en la intersección de la fila y la columna indica si hay una arista desde el vértice al vértice . Cuando dos vértices están conectados por una arista, decimos que son adyacentes. La Figura 3 ilustra la matriz de adyacencia para el grafo de la Figura 2. Un valor en una celda representa la ponderación de la arista que une el vértice con el vértice .
Figura 3: Una representación de un grafo mediante una matriz de adyacencia¶
Figura 3: Una representación de un grafo mediante una matriz de adyacencia
La ventaja de la matriz de adyacencia es que es simple, y que para grafos pequeños es fácil ver qué nodos están conectados a otros nodos. Sin embargo, note que la mayoría de las celdas de la matriz están vacías. Dado que la mayoría de las celdas están vacías decimos que esta matriz es “rala”. Una matriz no es una forma muy eficiente de almacenar datos ralos. De hecho, en Python usted debe incluso esforzarse por crear una estructura de matriz como la de la Figura 3.
La matriz de adyacencia es una buena implementación para un grafo cuando el número de aristas es grande. Pero ¿qué entendemos por grande? ¿Cuántas aristas se necesitarían para llenar la matriz? Puesto que hay una fila y una columna para cada vértice en el grafo, el número de aristas requeridas para llenar la matriz es . Una matriz está llena cuando cada vértice está conectado a todos los otros vértices. Hay pocos problemas reales que se aproximan a este tipo de conectividad. Los problemas que veremos en este capítulo se refieren a grafos que están conectados de forma rala.
