Programa en C para implementar la Array de Adyacencia de un Gráfico dado

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 0

Entrada: 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:

  1. Cree una array 2D (digamos Adj[N+1][N+1] ) de tamaño NxN e inicialice todos los valores de esta array a cero.
  2. 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.
  3. 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;
}
Producción:

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *