Dado un gráfico no dirigido de N vértices 1 a N y M aristas en forma de array 2D arr[][] cuya fila consta de dos números X e Y que denota que hay una arista entre X e Y, la tarea es escribir Programa en C para crear la array de adyacencia del gráfico dado .
Ejemplos:
Entrada: N = 5, M = 4, arr[][] = { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 1, 5 } } Salida: 0 1 0 0
1
1
0 1 0 0
0 1
0 0 0 0 0 0 0
1 1 0 0 1 0Entrada: N = 3, M = 4, arr[][] = { { 1, 2 }, { 2, 3 }, { 3, 1 }, { 2, 2 } } Salida: 0 1 1
1
1
1
1 1 0
Enfoque: La idea es usar una Array cuadrada de tamaño NxN para crear una Array de Adyacencia. A continuación se muestran los pasos:
- Cree una array 2D (digamos Adj[N+1][N+1] ) de tamaño NxN e inicialice todos los valores de esta array a cero.
- Para cada borde en arr[][](por ejemplo, X e Y ), Actualizar valor en Adj[X][Y] y Adj[Y][X] a 1, indica que hay un borde entre X e Y.
- Muestre la array de adyacencia después de la operación anterior para todos los pares en arr[][] .
A continuación se muestra la implementación del enfoque anterior:
// C program for the above approach #include <stdio.h> // N vertices and M Edges int N, M; // Function to create Adjacency Matrix void createAdjMatrix(int Adj[][N + 1], int arr[][2]) { // Initialise all value to this // Adjacency list to zero for (int i = 0; i < N + 1; i++) { for (int j = 0; j < N + 1; j++) { Adj[i][j] = 0; } } // Traverse the array of Edges for (int i = 0; i < M; i++) { // Find X and Y of Edges int x = arr[i][0]; int y = arr[i][1]; // Update value to 1 Adj[x][y] = 1; Adj[y][x] = 1; } } // Function to print the created // Adjacency Matrix void printAdjMatrix(int Adj[][N + 1]) { // Traverse the Adj[][] for (int i = 1; i < N + 1; i++) { for (int j = 1; j < N + 1; j++) { // Print the value at Adj[i][j] printf("%d ", Adj[i][j]); } printf("\n"); } } // Driver Code int main() { // Number of vertices N = 5; // Given Edges int arr[][2] = { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 1, 5 } }; // Number of Edges M = sizeof(arr) / sizeof(arr[0]); // For Adjacency Matrix int Adj[N + 1][N + 1]; // Function call to create // Adjacency Matrix createAdjMatrix(Adj, arr); // Print Adjacency Matrix printAdjMatrix(Adj); return 0; }
0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0
Complejidad temporal: O(N 2 ) , donde N es el número de vértices de un gráfico.
Publicación traducida automáticamente
Artículo escrito por alokesh985 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA