图实现 C++

Graph implementation C++

提问by The GiG

I was wondering about a quick to write implementation of a graph in c++. I need the data structure to be easy to manipulate and use graph algorithms(such as BFS,DFS, Kruskal, Dijkstra...). I need this implementation for an algorithms Olympiad, so the easier to write the data structure the better.

我想知道在 C++ 中快速编写图形的实现。我需要数据结构易于操作和使用图算法（例如 BFS、DFS、Kruskal、Dijkstra...）。我需要这个算法奥林匹克的实现，所以编写数据结构越容易越好。

Can you suggest such DS(main structs or classes and what will be in them). I know that an Adjacency list and Adjacency matrix are the main possibilities, but I mean a more detailed codesample.

你能推荐这样的 DS（主要结构或类以及它们中的内容）。我知道邻接列表和邻接矩阵是主要的可能性，但我的意思是更详细的代码示例。

For example I thought about this DS last time I had to implement a graph for DFS:

例如，我上次不得不为 DFS 实现图形时想到了这个 DS：

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

and then used a array of size n containing in its i'th place the Edge List(struct Edge) representing the edges starting in the i'th node.

然后使用大小为 n 的数组，在其第 i 个位置中包含表示从第 i 个节点开始的边的 Edge List(struct Edge)。

but when trying to DFS on this graph I had to write a 50 line code with about 10 while loops.

但是当试图在这个图上进行 DFS 时，我不得不编写一个 50 行的代码，其中包含大约 10 个 while 循环。

What 'good' implementations are there?

有哪些“好的”实现？

采纳答案by 6502

It really depends on what algorithms you need to implement, there is no silver bullet (and that's shouldn't be a surprise... the general rule about programming is that there's no general rule ;-) ).

这真的取决于你需要实现什么算法，没有灵丹妙药（这并不奇怪......编程的一般规则是没有一般规则;-)）。

I often end up representing directed multigraphs using node/edge structures with pointers... more specifically:

我经常最终使用带有指针的节点/边结构来表示有向多重图……更具体地说：

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

In other words each node has a doubly-linked list of incoming links and a doubly-linked list of outgoing links. Each link knows fromand tonodes and is at the same time in two different doubly-linked lists: the list of all links coming out from the same fromnode and the list of all links arriving at the same tonode.

换句话说，每个节点都有一个传入链接的双向链表和一个传出链接的双向链表。每个链接都知道from和to节点，并且同时在两个不同的双向链表中：来自同一from节点的所有链接的列表和到达同一to节点的所有链接的列表。

The pointers prev_same_fromand next_same_fromare used when following the chain of all the links coming out fromthe same node; the pointers prev_same_toand next_same_toare instead used when managing the chain of all the links pointing tothe same node.

指针prev_same_from和next_same_from用于跟踪来自同一节点的所有链接的链；指针prev_same_to和next_same_to管理所有指向的链接的链时代替被使用于相同的节点。

It's a lot of pointer twiddling (so unless you love pointers just forget about this) but query and update operations are efficient; for example adding a node or a link is O(1), removing a link is O(1) and removing a node x is O(deg(x)).

这是大量的指针操作（所以除非你喜欢指针，否则就忘记这一点）但是查询和更新操作是有效的；例如，添加一个节点或一个链接是 O(1)，删除一个链接是 O(1)，删除一个节点 x 是 O(deg(x))。

Of course depending on the problem, payload size, graph size, graph density this approach can be way overkilling or too much demanding for memory (in addition to payload you've 4 pointers per node and 6 pointers per link).

当然，根据问题、有效负载大小、图形大小、图形密度，这种方法可能会过度杀伤或对内存的要求过高（除了有效负载之外，每个节点有 4 个指针，每个链接有 6 个指针）。

A similar structure full implementation can be found here.

可以在此处找到类似结构的完整实现。

回答by user2063050

Below is a implementation of Graph Data Structure in C++ as Adjacency List.

下面是在 C++ 中作为邻接表的图数据结构的实现。

I have used STL vector for representation of vertices and STL pair for denoting edge and destination vertex.

我使用 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);
}

回答by Clearer

This question is ancient but for some reason I can't seem to get it out of my mind.

这个问题很古老，但出于某种原因，我似乎无法摆脱它。

While all of the solutions do provide an implementation of graphs, they are also all very verbose. They are simply not elegant.

虽然所有解决方案都提供了图的实现，但它们也都非常冗长。他们根本不优雅。

Instead of inventing your own graph class all you reallyneed is a way to tell that one point is connected to another -- for that, std::mapand std::unordered_mapwork perfectly fine. Simply, define a graph as a map between nodes and lists of edges. If you don't need extra data on the edge, a list of end nodes will do just fine.

与其发明你自己的图形类，你真正需要的是一种方法来告诉一个点与另一个点相连——为此，std::map并且std::unordered_map工作得非常好。简单地说，将图定义为节点和边列表之间的映射。如果您不需要边缘上的额外数据，端节点列表就可以了。

Thus a succinct graph in C++, could be implemented like so:

因此，C++ 中的简洁图可以像这样实现：

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

Or, if you need additional data,

或者，如果您需要其他数据，

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

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

Now your graph structure will plug nicely into the rest of the language and you don't have to remember any new clunky interface -- the old clunky interface will do just fine.

现在您的图形结构将很好地插入语言的其余部分，您不必记住任何新的笨拙界面——旧的笨拙界面就可以了。

No benchmarks, but I have a feeling this will also outperform the other suggestions here.

没有基准测试，但我觉得这也会胜过这里的其他建议。

NB: the ints are not indices -- they are identifiers.

注意：ints 不是索引——它们是标识符。

回答by thkala

The most common representations are probably these two:

最常见的表示可能是这两种：

• Adjacency list

• Adjacency matrix

• 邻接表

• 邻接矩阵

Of these two the adjacency matrixis the simplest, as long as you don't mind having a (possibly huge) n * narray, where nis the number of vertices. Depending on the base type of the array, you can even store edge weights for use in e.g. shortest path discovery algorithms.

在这两个矩阵中，邻接矩阵是最简单的，只要您不介意有一个（可能很大的）n * n数组，n顶点数在哪里。根据数组的基本类型，您甚至可以存储边缘权重以用于例如最短路径发现算法。

回答by Govinda Keshavdas

I prefer using an adjacency list of Indices ( not pointers )

我更喜欢使用索引的邻接列表（不是指针）

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

回答by anish singh

There can be an even simpler representation assuming that one has to only test graph algorithms not use them(graph) else where. This can be as a map from vertices to their adjacency lists as shown below :-

假设人们只需要测试图形算法而不在其他地方使用它们（图形），可以有一个更简单的表示。这可以作为从顶点到它们的邻接列表的映射，如下所示：-

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

回答by Vikalp Veer

Here is a basic implementation of a graph. Note: I use vertex which is chained to next vertex. And each vertex has a list pointing to adjacent nodes.

这是图的基本实现。注意：我使用链接到下一个顶点的顶点。每个顶点都有一个指向相邻节点的列表。

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

}

With the above code, you can expand to do DFS/BFS etc.

有了上面的代码，你可以扩展做DFS/BFS等。