Una lista de adyacencia se utiliza para representar gráficos. Aquí, para cada vértice en el gráfico, tenemos una lista de todos los otros vértices a los que el vértice en particular tiene una arista.
Problema: Dada la lista de adyacencia y el número de vértices y aristas de un gráfico, la tarea es representar la lista de adyacencia para un gráfico dirigido.
Ejemplos:
Entrada: V = 3, bordes[][]= {{0, 1}, {1, 2} {2, 0}}
Salida: 0 -> 1
1 -> 2
2 -> 0
Explicación:
La salida representa la lista de adyacencia para el gráfico dado.Entrada: V = 4, aristas[][] = {{0, 1}, {1, 2}, {1, 3}, {2, 3}, {3, 0}}
Salida: 0 -> 1
1 -> 2 3
2 -> 3
3 -> 0
Explicación:
La salida representa la lista de adyacencia para el gráfico dado.
Enfoque (usando STL ): la idea principal es representar el gráfico como una array de vectores de modo que cada vector represente la lista de adyacencia de un solo vértice. Usando STL, el código se vuelve más simple y más fácil de entender.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to add edges void addEdge(vector<int> adj[], int u, int v) { adj[u].push_back(v); } // Function to print adjacency list void adjacencylist(vector<int> adj[], int V) { for (int i = 0; i < V; i++) { cout << i << "->"; for (int& x : adj[i]) { cout << x << " "; } cout << endl; } } // Function to initialize the adjacency list // of the given graph void initGraph(int V, int edges[3][2], int noOfEdges) { // To represent graph as adjacency list vector<int> adj[V]; // Traverse edges array and make edges for (int i = 0; i < noOfEdges; i++) { // Function call to make an edge addEdge(adj, edges[i][0], edges[i][1]); } // Function Call to print adjacency list adjacencylist(adj, V); } // Driver Code int main() { // Given vertices int V = 3; // Given edges int edges[3][2] = { { 0, 1 }, { 1, 2 }, { 2, 0 } }; int noOfEdges = 3; // Function Call initGraph(V, edges, noOfEdges); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { // Function to add edges static void addEdge(Vector<Integer> adj[], int u, int v) { adj[u].add(v); } // Function to print adjacency list static void adjacencylist(Vector<Integer> adj[], int V) { for (int i = 0; i < V; i++) { System.out.print(i+ "->"); for (int x : adj[i]) { System.out.print(x+ " "); } System.out.println(); } } // Function to initialize the adjacency list // of the given graph static void initGraph(int V, int edges[][], int noOfEdges) { // To represent graph as adjacency list @SuppressWarnings("unchecked") Vector<Integer> adj[] = new Vector[3]; for(int i =0;i<adj.length;i++) { adj[i] = new Vector<>(); } // Traverse edges array and make edges for (int i = 0; i < noOfEdges; i++) { // Function call to make an edge addEdge(adj, edges[i][0], edges[i][1]); } // Function Call to print adjacency list adjacencylist(adj, V); } // Driver Code public static void main(String[] args) { // Given vertices int V = 3; // Given edges int edges[][] = { { 0, 1 }, { 1, 2 }, { 2, 0 } }; int noOfEdges = 3; // Function Call initGraph(V, edges, noOfEdges); } } // This code is contributed by gauravrajput1
Python3
# Python program for the above approach # Function to add edges def addEdge(adj, u, v): adj[u].append(v) # Function to print adjacency list def adjacencylist(adj, V): for i in range (0, V): print(i, "->", end="") for x in adj[i]: print(x , " ", end="") print() # Function to initialize the adjacency list # of the given graph def initGraph(V, edges, noOfEdges): adj = [0]* 3 for i in range(0, len(adj)): adj[i] = [] # Traverse edges array and make edges for i in range(0, noOfEdges) : # Function call to make an edge addEdge(adj, edges[i][0], edges[i][1]) # Function Call to print adjacency list adjacencylist(adj, V) # Driver Code # Given vertices V = 3 # Given edges edges = [[0, 1 ], [1, 2 ], [2, 0 ]] noOfEdges = 3; # Function Call initGraph(V, edges, noOfEdges) # This code is contributed by AR_Gaurav
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to add edges static void addEdge(List<int> []adj, int u, int v) { adj[u].Add(v); } // Function to print adjacency list static void adjacencylist(List<int> []adj, int V) { for (int i = 0; i < V; i++) { Console.Write(i+ "->"); foreach (int x in adj[i]) { Console.Write(x+ " "); } Console.WriteLine(); } } // Function to initialize the adjacency list // of the given graph static void initGraph(int V, int [,]edges, int noOfEdges) { // To represent graph as adjacency list List<int> []adj = new List<int>[3]; for(int i = 0; i < adj.Length; i++) { adj[i] = new List<int>(); } // Traverse edges array and make edges for (int i = 0; i < noOfEdges; i++) { // Function call to make an edge addEdge(adj, edges[i,0], edges[i,1]); } // Function Call to print adjacency list adjacencylist(adj, V); } // Driver Code public static void Main(String[] args) { // Given vertices int V = 3; // Given edges int [,]edges = { { 0, 1 }, { 1, 2 }, { 2, 0 } }; int noOfEdges = 3; // Function Call initGraph(V, edges, noOfEdges); } } // This code is contributed by Amit Katiyar
Javascript
<script> // javascript program for the above approach // Function to add edges function addEdge( adj , u , v) { adj[u].push(v); } // Function to print adjacency list function adjacencylist(adj , V) { for (var i = 0; i < V; i++) { document.write(i + "->"); for (var x of adj[i]) { document.write(x + " "); } document.write("<br/>"); } } // Function to initialize the adjacency list // of the given graph function initGraph(V , edges , noOfEdges) { // To represent graph as adjacency list var adj = Array(3); for (var i = 0; i < adj.length; i++) { adj[i] = Array(); } // Traverse edges array and make edges for (i = 0; i < noOfEdges; i++) { // Function call to make an edge addEdge(adj, edges[i][0], edges[i][1]); } // Function Call to print adjacency list adjacencylist(adj, V); } // Driver Code // Given vertices var V = 3; // Given edges var edges = [ [ 0, 1 ], [ 1, 2 ], [ 2, 0 ]]; var noOfEdges = 3; // Function Call initGraph(V, edges, noOfEdges); // This code is contributed by gauravrajput1 </script>
0->1 1->2 2->0
Publicación traducida automáticamente
Artículo escrito por maitreyeepaliwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA