graficos en borland c++

Implementación de gráficos C++

Question

Me preguntaba acerca de cómo escribir rápidamente la implementación de un gráfico en c ++. Necesito que la estructura de datos sea fácil de manipular y utilice algoritmos de gráficos (como BFS, DFS, Kruskal, Dijkstra ...). Necesito esta implementación para una Olimpiada de algoritmos, por lo que cuanto más fácil sea escribir la estructura de datos, mejor.

¿Puede sugerir tales DS (estructuras principales o clases y qué habrá en ellas)? Sé que una lista de adyacencia y una matriz de adyacencia son las principales posibilidades, pero me refiero a una muestra de código más detallada.

Por ejemplo, pensé en este DS la última vez que tuve que implementar un gráfico para DFS:

struct Edge {
  int start;
  int end;
  struct Edge* nextEdge;
}

y luego usó una matriz de tamaño n que contiene en su lugar i la Lista de bordes (struct Edge) que representa los bordes que comienzan en el i-ésimo nodo.

pero al intentar hacer DFS en este gráfico, tuve que escribir un código de 50 líneas con aproximadamente 10 bucles while.

¿Qué ''buenas'' implementaciones hay?

Answer 1

A continuación se muestra una implementación de Graph Data Structure en C ++ como Lista de adyacencia.

He usado el vector STL para la representación de vértices y el par STL para denotar el vértice de borde y el de destino.

#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

struct vertex {
    typedef pair<int, vertex*> ve;
    vector<ve> adj; //cost of edge, destination vertex
    string name;
    vertex(string s) : name(s) {}
};

class graph
{
public:
    typedef map<string, vertex *> vmap;
    vmap work;
    void addvertex(const string&);
    void addedge(const string& from, const string& to, double cost);
};

void graph::addvertex(const string &name)
{
    vmap::iterator itr = work.find(name);
    if (itr == work.end())
    {
        vertex *v;
        v = new vertex(name);
        work[name] = v;
        return;
    }
    cout << "/nVertex already exists!";
}

void graph::addedge(const string& from, const string& to, double cost)
{
    vertex *f = (work.find(from)->second);
    vertex *t = (work.find(to)->second);
    pair<int, vertex *> edge = make_pair(cost, t);
    f->adj.push_back(edge);
}

Answer 2

Aquí hay una implementación básica de un gráfico. Nota: uso el vértice que está encadenado al siguiente vértice. Y cada vértice tiene una lista que apunta a los nodos adyacentes.

#include <iostream>
using namespace std;


// 1 ->2 
// 1->4
// 2 ->3
// 4->3
// 4 -> 5
// Adjacency list
// 1->2->3-null
// 2->3->null
//4->5->null;

// Structure of a vertex
struct vertex {
   int i;
   struct node *list;
   struct vertex *next;
};
typedef struct vertex * VPTR;

// Struct of adjacency list
struct node {
    struct vertex * n;
    struct node *next;
};

typedef struct node * NODEPTR;

class Graph {
    public:
        // list of nodes chained together
        VPTR V;
        Graph() {
            V = NULL;
        }
        void addEdge(int, int);
        VPTR  addVertex(int);
        VPTR existVertex(int i);
        void listVertex();
};

// If vertex exist, it returns its pointer else returns NULL
VPTR Graph::existVertex(int i) {
    VPTR temp  = V;
    while(temp != NULL) {
        if(temp->i == i) {
            return temp;
        }
        temp = temp->next;
    }
   return NULL;
}
// Add a new vertex to the end of the vertex list
VPTR Graph::addVertex(int i) {
    VPTR temp = new(struct vertex);
    temp->list = NULL;
    temp->i = i;
    temp->next = NULL;

    VPTR *curr = &V;
    while(*curr) {
        curr = &(*curr)->next;
    }
    *curr = temp;
    return temp;
}

// Add a node from vertex i to j. 
// first check if i and j exists. If not first add the vertex
// and then add entry of j into adjacency list of i
void Graph::addEdge(int i, int j) {

    VPTR v_i = existVertex(i);   
    VPTR v_j = existVertex(j);   
    if(v_i == NULL) {
        v_i = addVertex(i);
    }
    if(v_j == NULL) {
        v_j = addVertex(j);
    }

    NODEPTR *temp = &(v_i->list);
    while(*temp) {
        temp = &(*temp)->next;
    }
    *temp = new(struct node);
    (*temp)->n = v_j;
    (*temp)->next = NULL;
}
// List all the vertex.
void Graph::listVertex() {
    VPTR temp = V;
    while(temp) {
        cout <<temp->i <<" ";
        temp = temp->next;
    }
    cout <<"/n";

}

// Client program
int main() {
    Graph G;
    G.addEdge(1, 2);
    G.listVertex();

}

Con el código anterior, puede expandir para hacer DFS / BFS, etc.

Answer 3

Esta pregunta es antigua, pero por alguna razón parece que no puedo sacarla de mi mente.

Si bien todas las soluciones proporcionan una implementación de gráficos, también son todas muy detalladas. Simplemente no son elegantes.

En lugar de inventar tu propia clase de gráficos, todo lo que realmente necesitas es una forma de decir que un punto está conectado a otro; para eso, std::map y std::unordered_map funcionan perfectamente bien. Simplemente, defina un gráfico como un mapa entre un nodo y una lista de vértices. Si no necesita datos adicionales en los vértices, una lista de nodos finales funcionará bien.

Por lo tanto, un gráfico sucinto en C ++ podría implementarse así:

using graph = std::map<int, std::vector<int>>;

O, si necesita datos adicionales,

struct vertex {
    int nodes[2];
    float cost; // add more if you need it
};

using graph = std::map<int, std::vector<vertex>>;

Ahora la estructura de su gráfico se conectará muy bien con el resto del idioma y no tendrá que recordar ninguna nueva interfaz torpe: la vieja interfaz torpe funcionará perfectamente.

No hay puntos de referencia, pero tengo la sensación de que esto también superará a las otras sugerencias aquí.

NB: los int s no son índices, son identificadores.

Answer 4

Las representaciones más comunes son probablemente estas dos:

• Lista de adyacencia

• Matriz de adyacencia

De estos dos, la matriz de adyacencia es la más simple, siempre y cuando no te importe tener una matriz (posiblemente enorme) n * n , donde n es el número de vértices. Dependiendo del tipo de base de la matriz, incluso puede almacenar pesos de borde para usar, por ejemplo, algoritmos de descubrimiento de ruta más cortos.

Answer 5

Prefiero usar una lista de adyacencia de Índices (no punteros)

typedef std::vector< Vertex > Vertices;
typedef std::set <int> Neighbours;


struct Vertex {
private:
   int data;
public:
   Neighbours neighbours;

   Vertex( int d ): data(d) {}
   Vertex( ): data(-1) {}

   bool operator<( const Vertex& ref ) const {
      return ( ref.data < data );
   }
   bool operator==( const Vertex& ref ) const {
      return ( ref.data == data );
   }
};

class Graph
{
private :
   Vertices vertices;
}

void Graph::addEdgeIndices ( int index1, int index2 ) {
  vertices[ index1 ].neighbours.insert( index2 );
}


Vertices::iterator Graph::findVertexIndex( int val, bool& res )
{
   std::vector<Vertex>::iterator it;
   Vertex v(val);
   it = std::find( vertices.begin(), vertices.end(), v );
   if (it != vertices.end()){
        res = true;
       return it;
   } else {
       res = false;
       return vertices.end();
   }
}

void Graph::addEdge ( int n1, int n2 ) {

   bool foundNet1 = false, foundNet2 = false;
   Vertices::iterator vit1 = findVertexIndex( n1, foundNet1 );
   int node1Index = -1, node2Index = -1;
   if ( !foundNet1 ) {
      Vertex v1( n1 );
      vertices.push_back( v1 );
      node1Index = vertices.size() - 1;
   } else {
      node1Index = vit1 - vertices.begin();
   }
   Vertices::iterator vit2 = findVertexIndex( n2, foundNet2);
   if ( !foundNet2 ) {
      Vertex v2( n2 );
      vertices.push_back( v2 );
      node2Index = vertices.size() - 1;
   } else {
      node2Index = vit2 - vertices.begin();
   }

   assert( ( node1Index > -1 ) && ( node1Index <  vertices.size()));
   assert( ( node2Index > -1 ) && ( node2Index <  vertices.size()));

   addEdgeIndices( node1Index, node2Index );
}

Answer 6

Puede haber una representación aún más simple, suponiendo que uno solo debe probar los algoritmos de gráfico y no usarlos (gráfico) en otro lugar. Esto puede ser como un mapa de vértices a sus listas de adyacencia como se muestra a continuación:

#include<bits/stdc++.h>
using namespace std;

/* implement the graph as a map from the integer index as a key to the   adjacency list
 * of the graph implemented as a vector being the value of each individual key. The
 * program will be given a matrix of numbers, the first element of each row will
 * represent the head of the adjacency list and the rest of the elements will be the
 * list of that element in the graph.
*/

typedef map<int, vector<int> > graphType;

int main(){

graphType graph;
int vertices = 0;

cout << "Please enter the number of vertices in the graph :- " << endl;
cin >> vertices;
if(vertices <= 0){
    cout << "The number of vertices in the graph can''t be less than or equal to 0." << endl;
    exit(0);
}

cout << "Please enter the elements of the graph, as an adjacency list, one row after another. " << endl;
for(int i = 0; i <= vertices; i++){

    vector<int> adjList;                    //the vector corresponding to the adjacency list of each vertex

    int key = -1, listValue = -1;
    string listString;
    getline(cin, listString);
    if(i != 0){
        istringstream iss(listString);
        iss >> key;
        iss >> listValue;
        if(listValue != -1){
            adjList.push_back(listValue);
            for(; iss >> listValue; ){
                adjList.push_back(listValue);
            }
            graph.insert(graphType::value_type(key, adjList));
        }
        else
            graph.insert(graphType::value_type(key, adjList));
    }
}

//print the elements of the graph
cout << "The graph that you entered :- " << endl;
for(graphType::const_iterator iterator = graph.begin(); iterator != graph.end(); ++iterator){
    cout << "Key : " << iterator->first << ", values : ";

    vector<int>::const_iterator vectBegIter = iterator->second.begin();
    vector<int>::const_iterator vectEndIter = iterator->second.end();
    for(; vectBegIter != vectEndIter; ++vectBegIter){
        cout << *(vectBegIter) << ", ";
    }
    cout << endl;
}
}

Answer 7

Realmente depende de qué algoritmos necesites implementar, no hay una solución mágica (y eso no debería ser una sorpresa ... la regla general sobre programación es que no hay una regla general ;-)).

A menudo termino representando multigrafos dirigidos usando estructuras de nodo / borde con punteros ... más específicamente:

struct Node
{
    ... payload ...
    Link *first_in, *last_in, *first_out, *last_out;
};

struct Link
{
    ... payload ...
    Node *from, *to;
    Link *prev_same_from, *next_same_from,
         *prev_same_to, *next_same_to;
};

En otras palabras, cada nodo tiene una lista doblemente enlazada de enlaces entrantes y una lista doblemente enlazada de enlaces salientes. Cada enlace conoce from y to nodos y, al mismo tiempo, está en dos listas diferentes doblemente vinculadas: la lista de todos los enlaces que salen de la misma from nodo y la lista de todos los enlaces que llegan al mismo nodo.

Los punteros prev_same_from y next_same_from se usan al seguir la cadena de todos los enlaces que salen del mismo nodo; los punteros prev_same_to y next_same_to se usan en su lugar cuando se gestiona la cadena de todos los enlaces que apuntan al mismo nodo.

Son muchos juegos de punteros (así que a menos que te gusten los indicadores simplemente olvídate de esto) pero las operaciones de consulta y actualización son eficientes; por ejemplo, agregar un nodo o un enlace es O (1), eliminar un enlace es O (1) y eliminar un nodo x es O (deg (x)).

Por supuesto, dependiendo del problema, el tamaño de la carga, el tamaño del gráfico, la densidad del gráfico, este enfoque puede ser excesivo o demasiado exigente para la memoria (además de la carga útil, tiene 4 punteros por nodo y 6 punteros por enlace).