Prerrequisito: Gráfico y sus representaciones
Dada una representación de array de adyacencia de un Gráfico . La tarea es convertir la Array de Adyacencia dada a una representación de Lista de Adyacencia.
Ejemplos:
Entrada: arr[][] = [ [0, 0, 1], [0, 0, 1], [1, 1, 0] ]
Salida: La lista de adyacencia es:
0 -> 2
1 -> 2
2 – > 0 -> 1
Entrada: arr[][] = [ [0, 1, 0, 0, 1], [1, 0, 1, 1, 1], [0, 1, 0, 1, 0], [0, 1, 1, 0, 1], [1, 1, 0, 1, 0] ]
Salida: La lista de adyacencia es:
0 -> 1 -> 4
1 -> 0 -> 2 -> 3 -> 4
2 -> 1 -> 3
3 -> 1 -> 2 -> 4
4 -> 0 -> 1 -> 3
Array de adyacencia : La array de adyacencia es una array 2D de tamaño V x V, donde V es el número de vértices en un gráfico. Sea la array 2D adj[][], una ranura adj[i][j] = 1 indica que hay una arista desde el vértice i hasta el vértice j.
Lista de adyacencia: se utiliza una array de listas. El tamaño de la array es igual al número de vértices. Deje que la array sea array[]. Una array de entrada[i] representa la lista de vértices adyacentes al i-ésimo vértice.
Para convertir una array de adyacencia a la lista de adyacencia. Cree una array de listas y recorra la array de adyacencia. Si para cualquier celda (i, j) en la array » mat[i][j] = 1 «, significa que hay un borde de i a j , entonces inserte j en la lista en i-ésimaposición en la array de listas.
A continuación se muestra la implementación del enfoque anterior:
C++
#include<bits/stdc++.h>
using namespace std;
// CPP program to convert Adjacency matrix
// representation to Adjacency List
// converts from adjacency matrix to adjacency list
vector<vector<int>> convert( vector<vector<int>> a)
{
vector<vector<int>> adjList(a.size());
for (int i = 0; i < a.size(); i++)
{
for (int j = 0; j < a[i].size(); j++)
{
if (a[i][j] == 1)
{
adjList[i].push_back(j);
}
}
}
return adjList;
}
// Driver code
int main()
{
vector<vector<int>> a;
vector<int> p({0, 0, 1});
vector<int> q({0, 0, 1});
vector<int> r({1, 1, 0}); // adjacency matrix
a.push_back(p);
a.push_back(q);
a.push_back(r);
vector<vector<int>> AdjList = convert(a);
cout<<"Adjacency List:"<<endl;
// print the adjacency list
for (int i = 0; i < AdjList.size(); i++)
{
cout << i;
for(int j = 0; j < AdjList[i].size(); j++)
{
if(j == AdjList[i].size() - 1)
{
cout << " -> " << AdjList[i][j] << endl;
break;
}
else
cout << " -> " << AdjList[i][j];
}
}
}
// This code is contributed by Surendra_Gangwar
Java
// Java program to convert adjacency
// matrix representation to
// adjacency list
import java.util.*;
public class GFG {
// Function to convert adjacency
// list to adjacency matrix
static ArrayList<ArrayList<Integer>> convert(int[][] a)
{
// no of vertices
int l = a[0].length;
ArrayList<ArrayList<Integer>> adjListArray
= new ArrayList<ArrayList<Integer>>(l);
// Create a new list for each
// vertex such that adjacent
// nodes can be stored
for (int i = 0; i < l; i++) {
adjListArray.add(new ArrayList<Integer>());
}
int i, j;
for (i = 0; i < a[0].length; i++) {
for (j = 0; j < a.length; j++) {
if (a[i][j] == 1) {
adjListArray.get(i).add(j);
}
}
}
return adjListArray;
}
// Function to print the adjacency list
static void printArrayList(ArrayList<ArrayList<Integer>>
adjListArray)
{
// Print the adjacency list
for (int v = 0; v < adjListArray.size(); v++) {
System.out.print(v);
for (Integer u : adjListArray.get(v)) {
System.out.print(" -> " + u);
}
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
// Given Adjacency Matrix
int[][] a = { { 0, 0, 1 },
{ 0, 0, 1 },
{ 1, 1, 0 } };
// function to convert adjacency
// list to adjacency matrix
ArrayList<ArrayList<Integer>> adjListArray = convert(a);
System.out.println("Adjacency List: ");
printArrayList(adjListArray);
}
}
Python3
# Python 3 program to convert Adjacency matrix
# representation to Adjacency List
from collections import defaultdict
# converts from adjacency matrix to adjacency list
def convert(a):
adjList = defaultdict(list)
for i in range(len(a)):
for j in range(len(a[i])):
if a[i][j]== 1:
adjList[i].append(j)
return adjList
# driver code
a =[[0, 0, 1], [0, 0, 1], [1, 1, 0]] # adjacency matrix
AdjList = convert(a)
print("Adjacency List:")
# print the adjacency list
for i in AdjList:
print(i, end ="")
for j in AdjList[i]:
print(" -> {}".format(j), end ="")
print()
# This code is contributed by Muskan Kalra.
C#
// C# program to convert adjacency
// matrix representation to
// adjacency list
using System;
using System.Collections.Generic;
class GFG
{
// Function to convert adjacency
// list to adjacency matrix
static List<List<int>> convert(int[,] a)
{
// no of vertices
int l = a.GetLength(0);
List<List<int>> adjListArray = new List<List<int>>(l);
int i, j;
// Create a new list for each
// vertex such that adjacent
// nodes can be stored
for (i = 0; i < l; i++)
{
adjListArray.Add(new List<int>());
}
for (i = 0; i < a.GetLength(0); i++)
{
for (j = 0; j < a.GetLength(1); j++)
{
if (a[i,j] == 1)
{
adjListArray[i].Add(j);
}
}
}
return adjListArray;
}
// Function to print the adjacency list
static void printList(List<List<int>> adjListArray)
{
// Print the adjacency list
for (int v = 0; v < adjListArray.Count; v++)
{
Console.Write(v);
foreach (int u in adjListArray[v])
{
Console.Write(" -> " + u);
}
Console.WriteLine();
}
}
// Driver Code
public static void Main(String[] args)
{
// Given Adjacency Matrix
int[,] a = { { 0, 0, 1 }, { 0, 0, 1 }, { 1, 1, 0 } };
// function to convert adjacency
// list to adjacency matrix
List<List<int>> adjListArray = convert(a);
Console.WriteLine("Adjacency List: ");
printList(adjListArray);
}
}
// This code is contributed by 29AjayKumar
Adjacency List: 0 -> 2 1 -> 2 2 -> 0 -> 1
Complejidad temporal: O(N^2).
Espacio Auxiliar : O(N^2).
Publicación traducida automáticamente
Artículo escrito por MuskanKalra1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA