En el Conjunto 1 , se analiza el gráfico no ponderado. En esta publicación, se analiza la representación gráfica ponderada utilizando STL. La implementación es para la representación de listas de adyacencia de gráficos ponderados.
Gráfico ponderado no dirigido
Usamos dos contenedores STL para representar el gráfico:
- vector : Un contenedor de secuencias. Aquí lo usamos para almacenar listas de adyacencia de todos los vértices. Usamos el número de vértice como índice en este vector.
- par: Un contenedor simple para almacenar un par de elementos. Aquí lo usamos para almacenar el número de vértice adyacente y el peso del borde que se conecta al adyacente.
La idea es utilizar un vector de pares de vectores. El siguiente código implementa lo mismo.
C++
// C++ program to represent undirected and weighted graph
// using STL. The program basically prints adjacency list
// representation of graph
#include <bits/stdc++.h>
using namespace std;
// To add an edge
void addEdge(vector <pair<int, int> > adj[], int u,
int v, int wt)
{
adj[u].push_back(make_pair(v, wt));
adj[v].push_back(make_pair(u, wt));
}
// Print adjacency list representation of graph
void printGraph(vector<pair<int,int> > adj[], int V)
{
int v, w;
for (int u = 0; u < V; u++)
{
cout << "Node " << u << " makes an edge with \n";
for (auto it = adj[u].begin(); it!=adj[u].end(); it++)
{
v = it->first;
w = it->second;
cout << "\tNode " << v << " with edge weight ="
<< w << "\n";
}
cout << "\n";
}
}
// Driver code
int main()
{
int V = 5;
vector<pair<int, int> > adj[V];
addEdge(adj, 0, 1, 10);
addEdge(adj, 0, 4, 20);
addEdge(adj, 1, 2, 30);
addEdge(adj, 1, 3, 40);
addEdge(adj, 1, 4, 50);
addEdge(adj, 2, 3, 60);
addEdge(adj, 3, 4, 70);
printGraph(adj, V);
return 0;
}
Python3
# Python3 program to represent undirected
# and weighted graph. The program basically
# prints adjacency list representation of graph
# To add an edge
def addEdge(adj, u, v, wt):
adj[u].append([v, wt])
adj[v].append([u, wt])
return adj
# Print adjacency list representation of graph
def printGraph(adj, V):
v, w = 0, 0
for u in range(V):
print("Node", u, "makes an edge with")
for it in adj[u]:
v = it[0]
w = it[1]
print("\tNode", v, "with edge weight =", w)
print()
# Driver code
if __name__ == '__main__':
V = 5
adj = [[] for i in range(V)]
adj = addEdge(adj, 0, 1, 10)
adj = addEdge(adj, 0, 4, 20)
adj = addEdge(adj, 1, 2, 30)
adj = addEdge(adj, 1, 3, 40)
adj = addEdge(adj, 1, 4, 50)
adj = addEdge(adj, 2, 3, 60)
adj = addEdge(adj, 3, 4, 70)
printGraph(adj, V)
# This code is contributed by mohit kumar 29
Javascript
<script>
// Javascript program to represent undirected and weighted graph
// using STL. The program basically prints adjacency list
// representation of graph
// To add an edge
function addEdge(adj,u,v,wt)
{
adj[u].push([v,wt]);
adj[v].push([u,wt]);
return adj;
}
//Print adjacency list representation of graph
function printGraph(adj, V)
{
let v=0,w=0;
for(let u=0;u<V;u++)
{
document.write("Node "+u+ " makes an edge with<br>");
for(let it=0;it<adj[u].length;it++)
{
v=adj[u][it][0];
w=adj[u][it][1];
document.write(" Node "+ v+ " with edge weight ="+ w+"<br>")
}
}
}
// Driver code
let V = 5;
// The below line may not work on all
// compilers. If it does not work on
// your compiler, please replace it with
// following
// vector<int> *adj = new vector<int>[V];
let adj=new Array(V);
for(let i=0;i<V;i++)
{
adj[i]=[];
}
// Vertex numbers should be from 0 to 4.
adj = addEdge(adj, 0, 1, 10)
adj = addEdge(adj, 0, 4, 20)
adj = addEdge(adj, 1, 2, 30)
adj = addEdge(adj, 1, 3, 40)
adj = addEdge(adj, 1, 4, 50)
adj = addEdge(adj, 2, 3, 60)
adj = addEdge(adj, 3, 4, 70)
printGraph(adj, V);
// This code is contributed by unknown2108
</script>
Java
import java.util.*;
// Creation of Adjacency List
// The adjacency List consist of an ArrayList within an
// ArrayList. The inner ArrayList holds the HashMap of
// (vertices,weight)
public class Weighted_Graph {
int v;
ArrayList<ArrayList<HashMap<Integer, Integer> > > adj;
Weighted_Graph(int v)
{
this.v = v;
this.adj = new ArrayList<>();
for (int i = 0; i < v; i++) {
this.adj.add(new ArrayList<>());
}
}
// Function to add an Edge
void addEdge(int u, int v, int weight)
{
this.adj.get(u).add(new HashMap<>());
this.adj.get(u)
.get(this.adj.get(u).size() - 1)
.put(v, weight);
this.adj.get(v).add(new HashMap<>());
this.adj.get(v)
.get(this.adj.get(v).size() - 1)
.put(u, weight);
}
// Function for printing the whole graph
// Stream API has been used
// to easily access the HashMap elements
// This code may not work in versions
// prior to java 8
void printGraph()
{
for (int i = 0; i < this.v; i++) {
System.out.println("\nNode " + i
+ " makes an edge with ");
for (HashMap<Integer, Integer> j :
this.adj.get(i)) {
j.entrySet().forEach(
e
-> System.out.println(
"\tNode " + e.getKey()
+ " with edge weight "
+ e.getValue() + " "));
}
}
}
// Main method
public static void main(String[] args)
{
int v = 5;
Weighted_Graph obj = new Weighted_Graph(v);
obj.addEdge(0, 1, 10);
obj.addEdge(0, 4, 20);
obj.addEdge(1, 2, 30);
obj.addEdge(1, 3, 40);
obj.addEdge(1, 4, 50);
obj.addEdge(2, 3, 60);
obj.addEdge(3, 4, 70);
obj.printGraph();
}
}
// This code is submitted by Abhishek_Manna_HETC
Producción:
Node 0 makes an edge with
Node 1 with edge weight =10
Node 4 with edge weight =20
Node 1 makes an edge with
Node 0 with edge weight =10
Node 2 with edge weight =30
Node 3 with edge weight =40
Node 4 with edge weight =50
Node 2 makes an edge with
Node 1 with edge weight =30
Node 3 with edge weight =60
Node 3 makes an edge with
Node 1 with edge weight =40
Node 2 with edge weight =60
Node 4 with edge weight =70
Node 4 makes an edge with
Node 0 with edge weight =20
Node 1 with edge weight =50
Node 3 with edge weight =70
Este artículo es una contribución de Sahil Chhabra . y mejorado por Kunal Verma 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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