Grafos são estruturas de dados fundamentais em ciência da computação, usadas para
representar conjuntos de objetos (vértices ou nós) e suas relações (arestas). Em C++, você
pode implementar grafos de várias maneiras dependendo do tipo de grafo e da aplicação,
como matrizes de adjacência, listas de adjacência ou até representações baseadas em
classes e objetos.
Aqui está uma visão geral e exemplos de implementações:
1. Lista de Adjacência
Essa representação é eficiente em termos de memória, especialmente para grafos
esparsos.
#include <iostream>
#include <vector>
using namespace std;
class Grafo {
int V; // Número de vértices
vector<vector<int>> adj; // Lista de adjacência
public:
Grafo(int V) {
this->V = V;
[Link](V);
void adicionarAresta(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // Para grafo não direcionado
}
void mostrarGrafo() {
for (int i = 0; i < V; i++) {
cout << "Vértice " << i << ": ";
for (int v : adj[i]) {
cout << v << " ";
cout << endl;
};
int main() {
Grafo g(5);
[Link](0, 1);
[Link](0, 4);
[Link](1, 2);
[Link](1, 3);
[Link](1, 4);
[Link](3, 4);
[Link]();
return 0;
}
2. Matriz de Adjacência
Essa representação usa mais memória, mas é útil para grafos densos e para verificar
rapidamente a existência de uma aresta.
#include <iostream>
using namespace std;
class Grafo {
int V; // Número de vértices
int **adj; // Matriz de adjacência
public:
Grafo(int V) {
this->V = V;
adj = new int*[V];
for (int i = 0; i < V; i++) {
adj[i] = new int[V];
for (int j = 0; j < V; j++) {
adj[i][j] = 0;
void adicionarAresta(int u, int v) {
adj[u][v] = 1;
adj[v][u] = 1; // Para grafo não direcionado
}
void mostrarGrafo() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
cout << adj[i][j] << " ";
cout << endl;
~Grafo() {
for (int i = 0; i < V; i++) {
delete[] adj[i];
delete[] adj;
};
int main() {
Grafo g(5);
[Link](0, 1);
[Link](0, 4);
[Link](1, 2);
[Link](1, 3);
[Link](1, 4);
[Link](3, 4);
[Link]();
return 0;
3. Grafo com Pesos (Usando Lista de Adjacência)
Se o grafo possui arestas com pesos, você pode usar pares para armazenar o vértice e o
peso da aresta.
#include <iostream>
#include <vector>
using namespace std;
class Grafo {
int V;
vector<vector<pair<int, int>>> adj;
public:
Grafo(int V) {
this->V = V;
[Link](V);
void adicionarAresta(int u, int v, int peso) {
adj[u].emplace_back(v, peso);
adj[v].emplace_back(u, peso); // Para grafo não direcionado
}
void mostrarGrafo() {
for (int i = 0; i < V; i++) {
cout << "Vértice " << i << ": ";
for (auto p : adj[i]) {
cout << "(" << [Link] << ", " << [Link] << ") ";
cout << endl;
};
int main() {
Grafo g(5);
[Link](0, 1, 10);
[Link](0, 4, 20);
[Link](1, 2, 30);
[Link](1, 3, 40);
[Link](1, 4, 50);
[Link](3, 4, 60);
[Link]();
return 0;
Expansões Possíveis
1. Implementar Algoritmos: Adicione algoritmos como BFS, DFS, Dijkstra, Prim, ou
Kruskal.
2. Grafo Direcionado: Adapte os métodos para lidar com grafos direcionados.
3. Grafo Dinâmico: Use estruturas como unordered_map ou map para grafos de
tamanho dinâmico.
🚀
Essas implementações oferecem uma base sólida para trabalhar com grafos em C++. Se
precisar de um exemplo específico ou de mais detalhes, é só perguntar!
Grafos são estruturas de dados fundamentais em ciência da computação, usadas para
representar conjuntos de objetos (vértices ou nós) e suas relações (arestas). Em C++, você
pode implementar grafos de várias maneiras dependendo do tipo de grafo e da aplicação,
como matrizes de adjacência, listas de adjacência ou até representações baseadas em
classes e objetos.
Aqui está uma visão geral e exemplos de implementações:
1. Lista de Adjacência
Essa representação é eficiente em termos de memória, especialmente para grafos
esparsos.
#include <iostream>
#include <vector>
using namespace std;
class Grafo {
int V; // Número de vértices
vector<vector<int>> adj; // Lista de adjacência
public:
Grafo(int V) {
this->V = V;
[Link](V);
}
void adicionarAresta(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // Para grafo não direcionado
void mostrarGrafo() {
for (int i = 0; i < V; i++) {
cout << "Vértice " << i << ": ";
for (int v : adj[i]) {
cout << v << " ";
cout << endl;
};
int main() {
Grafo g(5);
[Link](0, 1);
[Link](0, 4);
[Link](1, 2);
[Link](1, 3);
[Link](1, 4);
[Link](3, 4);
[Link]();
return 0;
2. Matriz de Adjacência
Essa representação usa mais memória, mas é útil para grafos densos e para verificar
rapidamente a existência de uma aresta.
#include <iostream>
using namespace std;
class Grafo {
int V; // Número de vértices
int **adj; // Matriz de adjacência
public:
Grafo(int V) {
this->V = V;
adj = new int*[V];
for (int i = 0; i < V; i++) {
adj[i] = new int[V];
for (int j = 0; j < V; j++) {
adj[i][j] = 0;
void adicionarAresta(int u, int v) {
adj[u][v] = 1;
adj[v][u] = 1; // Para grafo não direcionado
void mostrarGrafo() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
cout << adj[i][j] << " ";
cout << endl;
~Grafo() {
for (int i = 0; i < V; i++) {
delete[] adj[i];
delete[] adj;
};
int main() {
Grafo g(5);
[Link](0, 1);
[Link](0, 4);
[Link](1, 2);
[Link](1, 3);
[Link](1, 4);
[Link](3, 4);
[Link]();
return 0;
3. Grafo com Pesos (Usando Lista de Adjacência)
Se o grafo possui arestas com pesos, você pode usar pares para armazenar o vértice e o
peso da aresta.
#include <iostream>
#include <vector>
using namespace std;
class Grafo {
int V;
vector<vector<pair<int, int>>> adj;
public:
Grafo(int V) {
this->V = V;
[Link](V);
void adicionarAresta(int u, int v, int peso) {
adj[u].emplace_back(v, peso);
adj[v].emplace_back(u, peso); // Para grafo não direcionado
void mostrarGrafo() {
for (int i = 0; i < V; i++) {
cout << "Vértice " << i << ": ";
for (auto p : adj[i]) {
cout << "(" << [Link] << ", " << [Link] << ") ";
cout << endl;
};
int main() {
Grafo g(5);
[Link](0, 1, 10);
[Link](0, 4, 20);
[Link](1, 2, 30);
[Link](1, 3, 40);
[Link](1, 4, 50);
[Link](3, 4, 60);
[Link]();
return 0;
}
Expansões Possíveis
1. Implementar Algoritmos: Adicione algoritmos como BFS, DFS, Dijkstra, Prim, ou
Kruskal.
2. Grafo Direcionado: Adapte os métodos para lidar com grafos direcionados.
3. Grafo Dinâmico: Use estruturas como unordered_map ou map para grafos de
tamanho dinâmico.
🚀
Essas implementações oferecem uma base sólida para trabalhar com grafos em C++. Se
precisar de um exemplo específico ou de mais detalhes, é só perguntar!
