图实现 C++

Question

我想知道如何用 C++ 快速编写图的实现。我需要数据结构易于操作和使用图算法（例如 BFS、DFS、Kruskal、Dijkstra...）。 我需要这个实现来参加算法奥林匹克竞赛，因此编写数据结构越容易越好。

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

例如，我上次考虑过这个DS，我必须为DFS实现一个图：

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

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

但是当尝试在此图上进行 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< 的所有链接的列表/code> 节点以及到达同一 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等。