Algoritmos y Estructura de Datos

Matrices de Adyacencia

Una matriz de adyacencia es una representación gráfica de un grafo en forma de una matriz cuadrada. Cada fila y columna de la matriz representa un vértice del grafo y cada elemento de la matriz representa la relación entre dos vértices.

Por ejemplo, si el grafo tiene cuatro vértices A, B, C y D, la matriz de adyacencia puede verse de la siguiente manera:

                    A  B  C  D
                A  0  1   1  0
                B   1  0  1  0
                C   1   1  0  1
                D  0  0  1  0
            

En este caso, la matriz de adyacencia indica que hay una arista entre A y B, entre A y C, entre C y D, y entre B y C. Los elementos de la diagonal principal siempre tienen valor 0, ya que un vértice no puede tener una arista consigo mismo.

Una matriz de adyacencia es una forma útil de representar grafos que tienen pocos vértices y pocas aristas, ya que permite una fácil visualización y manipulación de la estructura del grafo. Sin embargo, para grafos más grandes, otras formas de representación, como la lista de adyacencia, pueden ser más eficientes en términos de espacio y tiempo.

A continuacion el codigo para c++:

                #include 
                #include 

                const int MAX_N = 100; // máximo número de vértices

                // Grafo representado como una matriz de adyacencia
                std::vector> adj_matrix(MAX_N, std::vector(MAX_N));

                int main()
                {
                    int n; // número de vértices
                    int m; // número de aristas

                    std::cin >> n >> m;

                    // leer las aristas del grafo
                    for (int i = 0; i < m; i++)
                    {
                        int u, v;
                        std::cin >> u >> v;
                        adj_matrix[u][v] = 1; // agregar arista entre u y v
                    }

                    // imprimir la matriz de adyacencia
                    for (int i = 0; i < n; i++)
                    {
                        for (int j = 0; j < n; j++)
                        {
                            std::cout << adj_matrix[i][j] << " ";
                        }
                        std::cout << std::endl;
                    }

                    return 0;
                }
            

Este código lee el número de vértices y el número de aristas del grafo desde la entrada estándar, luego lee cada una de las aristas y las agrega a la matriz de adyacencia. Finalmente, imprime la matriz de adyacencia completa.

Link de apoyo

Representación de Grafos - Uruguay Educa

IMPLEMENTACION MATRIZ DE ADYACENCIA

APRENDE Y PROGRAMA