График реализации C ++

Question

Мне было интересно, как быстро написать реализацию графа на с ++. Мне нужна структура данных, чтобы было легко манипулировать и использовать графовые алгоритмы (такие как BFS, DFS, Kruskal, Dijkstra ...). Мне нужна эта реализация для олимпиады по алгоритмам, поэтому, чем проще написать структуру данных, тем лучше.

Можете ли вы предложить такие DS (основные структуры или классы и что будет в них). Я знаю, что список Смежности и матрица Смежности являются основными возможностями, но я имею в виду более подробный код образец.

Например, я думал об этом DS в прошлый раз, когда мне пришлось реализовать график для DFS:

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

, а затем использовал массив размера n, содержащий в своем i-м месте Edge List (struct Edge), представляющий ребра, начинающиеся в i-м узле.

но при попытке DFS на этом графике мне пришлось написать 50-строчный код с примерно 10 циклами while.

Какие есть «хорошие» реализации?

Answer 1

Ниже приведена реализация структуры данных графа в C ++ в виде списка смежности.

Я использовал вектор STL для представления вершин и пару STL для обозначения ребра и вершины назначения.

#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

Это действительно зависит от того, какие алгоритмы вам нужно реализовать, серебряной пули нет (и это не должно удивлять ... общее правило программирования - отсутствие общего правила ;-)).

Я часто заканчиваю тем, что представляю направленные мультиграфы, используя структуры узлов / ребер с указателями ... более конкретно:

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;
};

Другими словами, каждый узел имеет двунаправленный список входящих ссылок и двояко-связанный список исходящих ссылок.Каждая ссылка знает узлы from и to и одновременно находится в двух разных двусвязных списках: список всех ссылок, исходящих из одного узла from, и список всех ссылок, приходящих в один и тот же to узел.

Указатели prev_same_from и next_same_from используются при следовании по цепочке всех ссылок, выходящих из одного и того же узла;указатели prev_same_to и next_same_to вместо этого используются при управлении цепочкой всех ссылок, указывающих на один и тот же узел.

Сильно вертятся указатели (поэтому, если вы не любите указатели, просто забудьте об этом), но операции запроса и обновления эффективны;например, добавление узла или ссылки - это O (1), удаление ссылки - это O (1), а удаление узла x - это O (deg (x)).

Конечно, в зависимости от проблемы, полезная нагрузкаразмер, размер графика, плотность графика. Этот подход может быть слишком излишним или слишком требовательным к памяти (помимо полезной нагрузки у вас есть 4 указателя на узел и 6 указателей на ссылку).

Полная реализация аналогичной структуры можетможно найти здесь .

Answer 3

Этот вопрос древний, но по какой-то причине я, кажется, не могу выбросить его из головы.

Хотя все решения действительно предоставляют реализацию графов, все они также очень многословны.Они просто не изящны.

Вместо того, чтобы придумывать свой собственный класс графов, все, что вам действительно нужно, это способ сказать, что одна точка связана с другой - для этого std::map иstd::unordered_map отлично работает.Просто определите граф как карту между узлами и списками ребер.Если вам не нужны дополнительные данные на границе, список конечных узлов будет работать нормально.

Таким образом, краткий граф в C ++ может быть реализован так:

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

Или, если вам нужны дополнительные данные,

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

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

Теперь ваша структура графа будет хорошо подключаться к остальной части языка, и вам не нужно будет запоминать какой-либо новый неуклюжий интерфейс - подойдет старый неуклюжий интерфейспросто отлично.

Нет тестов, но я чувствую, что это также превзойдет другие предложения здесь.

Примечание: int не являются индексами - они являются идентификаторами.

Answer 4

Наиболее распространенными представлениями, вероятно, являются эти два:

• Список смежностей

• Матрица смежности

Из этих двух матрица смежности является самой простой, если вы не возражаете против наличия (возможно, огромного) массива n * n, гдеn - количество вершин.В зависимости от базового типа массива вы можете даже сохранить вес ребер для использования, например, в алгоритмах обнаружения кратчайшего пути.

Answer 5

Я предпочитаю использовать список смежности Индексы (не указатели)

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

Может быть даже более простое представление, если предположить, что нужно тестировать только алгоритмы графа, а не использовать их (граф) где-либо еще. Это может быть как карта от вершин до их списков смежности, как показано ниже: -

#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

Вот базовая реализация графа.Примечание: я использую вершину, которая связана с следующей вершиной.И у каждой вершины есть список, указывающий на соседние узлы.

#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();

}

С помощью приведенного выше кода, вы можете расширить, чтобы сделать DFS / BFS и т. Д.