Hemos introducido la implementación de Graph usando una array de vectores en la implementación de Graph usando STL para programación competitiva | conjunto 1 . En esta publicación, se usa una implementación diferente que se puede usar para implementar gráficos usando conjuntos . La implementación es para la representación de la lista de adyacencia del gráfico .
Un conjunto se diferencia de un vector en dos aspectos: almacena elementos ordenados y no se permiten elementos duplicados. Por lo tanto, este enfoque no se puede utilizar para gráficos que contienen bordes paralelos. Dado que los conjuntos se implementan internamente como árboles de búsqueda binarios, se puede buscar un borde entre dos vértices en tiempo O (logV) , donde V es el número de vértices en el gráfico. Los conjuntos en python están desordenados y no están indexados. Por lo tanto, para python usaremos un diccionario que tendrá un vértice de origen como clave y su lista de adyacencia se almacenará en un formato establecido como valor para esa clave.
El siguiente es un ejemplo de un gráfico no dirigido y no ponderado con 5 vértices.
A continuación se muestra la representación de la lista de adyacencia de este gráfico utilizando una array de conjuntos .
A continuación se muestra el código para la representación de la lista de adyacencia de un gráfico no dirigido usando conjuntos:
C++
// A C++ program to demonstrate adjacency list
// representation of graphs using sets
#include <bits/stdc++.h>
using namespace std;
struct Graph {
int V;
set<int, greater<int> >* adjList;
};
// A utility function that creates a graph of V vertices
Graph* createGraph(int V)
{
Graph* graph = new Graph;
graph->V = V;
// Create an array of sets representing
// adjacency lists. Size of the array will be V
graph->adjList = new set<int, greater<int> >[V];
return graph;
}
// Adds an edge to an undirected graph
void addEdge(Graph* graph, int src, int dest)
{
// Add an edge from src to dest. A new
// element is inserted to the adjacent
// list of src.
graph->adjList[src].insert(dest);
// Since graph is undirected, add an edge
// from dest to src also
graph->adjList[dest].insert(src);
}
// A utility function to print the adjacency
// list representation of graph
void printGraph(Graph* graph)
{
for (int i = 0; i < graph->V; ++i) {
set<int, greater<int> > lst = graph->adjList[i];
cout << endl << "Adjacency list of vertex "
<< i << endl;
for (auto itr = lst.begin(); itr != lst.end(); ++itr)
cout << *itr << " ";
cout << endl;
}
}
// Searches for a given edge in the graph
void searchEdge(Graph* graph, int src, int dest)
{
auto itr = graph->adjList[src].find(dest);
if (itr == graph->adjList[src].end())
cout << endl << "Edge from " << src
<< " to " << dest << " not found."
<< endl;
else
cout << endl << "Edge from " << src
<< " to " << dest << " found."
<< endl;
}
// Driver code
int main()
{
// Create the graph given in the above figure
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
// Print the adjacency list representation of
// the above graph
printGraph(graph);
// Search the given edge in the graph
searchEdge(graph, 2, 1);
searchEdge(graph, 0, 3);
return 0;
}
Java
// A Java program to demonstrate adjacency
// list using HashMap and TreeSet
// representation of graphs using sets
import java.util.*;
class Graph{
// TreeSet is used to get clear
// understand of graph.
HashMap<Integer, TreeSet<Integer>> graph;
static int v;
// Graph Constructor
public Graph()
{
graph = new HashMap<>();
for(int i = 0; i < v; i++)
{
graph.put(i, new TreeSet<>());
}
}
// Adds an edge to an undirected graph
public void addEdge(int src, int dest)
{
// Add an edge from src to dest into the set
graph.get(src).add(dest);
// Since graph is undirected, add an edge
// from dest to src into the set
graph.get(dest).add(src);
}
// A utility function to print the graph
public void printGraph()
{
for(int i = 0; i < v; i++)
{
System.out.println("Adjacency list of vertex " + i);
Iterator set = graph.get(i).iterator();
while (set.hasNext())
System.out.print(set.next() + " ");
System.out.println();
System.out.println();
}
}
// Searches for a given edge in the graph
public void searchEdge(int src, int dest)
{
Iterator set = graph.get(src).iterator();
if (graph.get(src).contains(dest))
System.out.println("Edge from " + src + " to " +
dest + " found");
else
System.out.println("Edge from " + src + " to " +
dest + " not found");
System.out.println();
}
// Driver code
public static void main(String[] args)
{
// Create the graph given in the above figure
v = 5;
Graph graph = new Graph();
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
// Print the adjacency list representation of
// the above graph
graph.printGraph();
// Search the given edge in the graph
graph.searchEdge(2, 1);
graph.searchEdge(0, 3);
}
}
// This code is contributed by rexj8
Python3
# Python3 program to represent adjacency
# list using dictionary
from collections import defaultdict
class graph(object):
def __init__(self, v):
self.v = v
self.graph = defaultdict(set)
# Adds an edge to undirected graph
def addEdge(self, source, destination):
# Add an edge from source to destination.
# If source is not present in dict add source to dict
self.graph.add(destination)
# Add an dge from destination to source.
# If destination is not present in dict add destination to dict
self.graph[destination].add(source)
# A utility function to print the adjacency
# list representation of graph
def print(self):
for i, adjlist in sorted(self.graph.items()):
print("Adjacency list of vertex ", i)
for j in sorted(adjlist, reverse = True):
print(j, end = " ")
print('\n')
# Search for a given edge in graph
def searchEdge(self,source,destination):
if source in self.graph:
if destination in self.graph:
if destination in self.graph:
if source in self.graph[destination]:
print("Edge from {0} to {1} found.\n".format(source, destination))
return
else:
print("Edge from {0} to {1} not found.\n".format(source, destination))
return
else:
print("Edge from {0} to {1} not found.\n".format(source, destination))
return
else:
print("Destination vertex {} is not present in graph.\n".format(destination))
return
else:
print("Source vertex {} is not present in graph.\n".format(source))
# Driver code
if __name__=="__main__":
g = graph(5)
g.addEdge(0, 1)
g.addEdge(0, 4)
g.addEdge(1, 2)
g.addEdge(1, 3)
g.addEdge(1, 4)
g.addEdge(2, 3)
g.addEdge(3, 4)
# Print adjacenecy list
# representation of graph
g.print()
# Search the given edge in a graph
g.searchEdge(2, 1)
g.searchEdge(0, 3)
#This code is contributed by Yalavarthi Supriya
Javascript
<script>
// A Javascript program to demonstrate adjacency list
// representation of graphs using sets
class Graph {
constructor()
{
this.V = 0;
this.adjList = new Set();
}
};
// A utility function that creates a graph of V vertices
function createGraph(V)
{
var graph = new Graph();
graph.V = V;
// Create an array of sets representing
// adjacency lists. Size of the array will be V
graph.adjList = Array.from(Array(V), ()=>new Set());
return graph;
}
// Adds an edge to an undirected graph
function addEdge(graph, src, dest)
{
// Add an edge from src to dest. A new
// element is inserted to the adjacent
// list of src.
graph.adjList[src].add(dest);
// Since graph is undirected, add an edge
// from dest to src also
graph.adjList[dest].add(src);
}
// A utility function to print the adjacency
// list representation of graph
function printGraph(graph)
{
for (var i = 0; i < graph.V; ++i) {
var lst = graph.adjList[i];
document.write( "<br>" + "Adjacency list of vertex "
+ i + "<br>");
for(var item of [...lst].reverse())
document.write( item + " ");
document.write("<br>");
}
}
// Searches for a given edge in the graph
function searchEdge(graph, src, dest)
{
if (!graph.adjList[src].has(dest))
document.write( "Edge from " + src
+ " to " + dest + " not found.<br>");
else
document.write( "<br> Edge from " + src
+ " to " + dest + " found." + "<br><br>");
}
// Driver code
// Create the graph given in the above figure
var V = 5;
var graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
// Print the adjacency list representation of
// the above graph
printGraph(graph);
// Search the given edge in the graph
searchEdge(graph, 2, 1);
searchEdge(graph, 0, 3);
// This code is contributed by rutvik_56.
</script>
Adjacency list of vertex 0 4 1 Adjacency list of vertex 1 4 3 2 0 Adjacency list of vertex 2 3 1 Adjacency list of vertex 3 4 2 1 Adjacency list of vertex 4 3 1 0 Edge from 2 to 1 found. Edge from 0 to 3 not found.
Pros : las consultas como si hay un borde desde el vértice u hasta el vértice v se pueden realizar en O (log V).
Contras :
- Agregar un borde toma O (log V), a diferencia de O (1) en la implementación de vectores.
- Los gráficos que contienen aristas paralelas no se pueden implementar mediante este método.
Optimización adicional de la operación de búsqueda perimetral mediante unordered_set (o hash): la operación de búsqueda perimetral se puede optimizar aún más a O(1) mediante unordered_set , que utiliza hash internamente.
Implementación:
C++
// A C++ program to demonstrate adjacency list
// representation of graphs using sets
#include <bits/stdc++.h>
using namespace std;
struct Graph {
int V;
unordered_set<int>* adjList;
};
// A utility function that creates a graph of
// V vertices
Graph* createGraph(int V)
{
Graph* graph = new Graph;
graph->V = V;
// Create an array of sets representing
// adjacency lists. Size of the array will be V
graph->adjList = new unordered_set<int>[V];
return graph;
}
// Adds an edge to an undirected graph
void addEdge(Graph* graph, int src, int dest)
{
// Add an edge from src to dest. A new
// element is inserted to the adjacent
// list of src.
graph->adjList[src].insert(dest);
// Since graph is undirected, add an edge
// from dest to src also
graph->adjList[dest].insert(src);
}
// A utility function to print the adjacency
// list representation of graph
void printGraph(Graph* graph)
{
for (int i = 0; i < graph->V; ++i) {
unordered_set<int> lst = graph->adjList[i];
cout << endl << "Adjacency list of vertex "
<< i << endl;
for (auto itr = lst.begin(); itr != lst.end(); ++itr)
cout << *itr << " ";
cout << endl;
}
}
// Searches for a given edge in the graph
void searchEdge(Graph* graph, int src, int dest)
{
auto itr = graph->adjList[src].find(dest);
if (itr == graph->adjList[src].end())
cout << endl << "Edge from " << src
<< " to " << dest << " not found."
<< endl;
else
cout << endl << "Edge from " << src
<< " to " << dest << " found."
<< endl;
}
// Driver code
int main()
{
// Create the graph given in the above figure
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
// Print the adjacency list representation of
// the above graph
printGraph(graph);
// Search the given edge in the graph
searchEdge(graph, 2, 1);
searchEdge(graph, 0, 3);
return 0;
}
Adjacency list of vertex 0 4 1 Adjacency list of vertex 1 4 3 0 2 Adjacency list of vertex 2 3 1 Adjacency list of vertex 3 4 1 2 Adjacency list of vertex 4 3 0 1 Edge from 2 to 1 found. Edge from 0 to 3 not found.
Ventajas :
- Consultas como si hay una arista desde el vértice u hasta el vértice v se pueden realizar en O(1).
- Agregar un borde toma O (1).
Contras :
- Los gráficos que contienen aristas paralelas no se pueden implementar mediante este método.
- Los bordes se almacenan en cualquier orden.
Nota: la representación de la array de adyacencia es la más optimizada para la búsqueda de bordes, pero los requisitos de espacio de la array de adyacencia son comparativamente altos para gráficos dispersos grandes. Además, la array de adyacencia tiene otras desventajas, como que BFS y DFS se vuelven costosos, ya que no podemos obtener rápidamente todos los Nodes adyacentes.
Este artículo es una contribución de vaibhav29498 . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA