Блог пользователя hrod-land

Автор hrod-land, история, 7 лет назад, По-английски

I am a novice in competitive programming and I do not know how I can implement an optimal graph in c++ ?. Use a code of geekforgeeks but I do not know how to modify it correctly (it throws me segmentation fault). So far I have not found a site in which to learn how to implement them :(

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

A graph is given as a collection of nodes and vertices. So let us assume you have n nodes and m vertices.

You can take a vector vector<int> v[n]. You can think of this like an array of vectors where each index behaves as a node and then the vector at that index will describe the edges.

In order to make an edge use v[parent_node].push_back(destination_node). If you have a directed graph then obviously this is sufficient. If this is a undirected graph then you also have to add one more entry v[destination_node].push_back(parent_node).

You can run a loop to create a complete graph. (I am considering undirected here).

for(int i=0;i<m;i++){
 int a,b;
 cin >> a >> b;
 v[a].push_back(b);
 v[b].push_back(a);
}

Now if you have to see all the vertices adjacent to a node you can do this

for(int i=0;i<v[node].size();i++){
   cout << "A neighbor of node " << node << " is " << v[node][i] << endl;
}

Note:- Keep in mind the nature of indexing. If the indexing is 1-based you will either have to convert it into 0-based indexing by subtracting 1 from each vertex or declare a vector of size n+1 vector<int> v[n+1]

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Some time ago I also struggled with a nice graph implementation that was both intuitive and not messy. The idea behind the code that I'll post is to have a nice representation of a single node that we can then place on a vector and with that make an adjacency list (which is the kind of implementation you want for speed).

Let's think (assuming it's an undirected graph): A node has adjacent nodes, which are connected with the "Current" node we're in with these lines called vertices, right? We can represent this relation from node A to B as A->B && A<-B, and we can store these adjacent nodes with a vector. We also need to know if the node we're currently in has been visited or not; we just need a boolean value to represent that, therefore we could make a struct of name Node that represents this idea.

struct Node {
    vector<int> adj;
    bool isVisited = false;
    int identifier; //added for demonstration
    //Another parameter you may need, like degree or a special property that the problem gives.
};

It's a simple implementation that doesn't require much effort, and it's a natural representation of a Node. To make a graph, we just need a vector with nodes of size n. This is how I read the input using this implementation:

int main() {
    int n; cin >> n;
    vector<Node> Graph(n);
    int vertices; cin >> vertices;
    for(int i = 0; i < vertices; i++) {
        int a,b;
        cin >> a >> b;
        //--a,--b necessary if the problem is using one based indexing
        Graph[a].adj.push_back(b);
        Graph[b].adj.push_back(a);
        Graph[a].identifier = a;
        Graph[b].identifier = b;
    }
	dfs(Graph,Graph[0]); //call dfs function explained below
}

An example of DFS with this implementation is as follows:

void dfs(vector<Node>& Nodes, Node& Current) {
    Current.isVisited = true;
    for(auto id : Current.adj) {
        Node& v = Nodes[id];
        if (!v.isVisited) {
            cout << "going from " << Current.identifier << " to " << v.identifier << endl;
            dfs(Nodes,v); 
        }
    }
} 
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    To be honest, I don't think that implementing something like this is actually useful in a contest environment where you have limited time. Sure this code is cleaner and more readable but it's way harder to write and modify and thus more error-prone. Personally I prefer and use the method horcrux2301 suggested.