Consider this situation: (undirected graph) we dont have number of nodes but have the edges like 1<->3 , 6<->7, 3<->7. So how do we declare a graph using this?

Generally we have n that is no. of node and e edges but in this case we only have e edges and that too not continuous i.e. instead of 1,2,3,4(or zero indexed) we have 1,3,6,7. I know we should use a map to convert these 1,3,6,7 values to 1,2,3,4 but how?

how we generally declare a graph

vector<int> adj[100000];
for(int i=0;i<e;i  )
{
  int u,v;
  cin>>u>>v;
  //need some mapping technique here to make this continuous
  adj[u].push_back(v);
  adj[v].push_back(u);
}

//iterate according to situation

CodePudding user response：

I recommend not relying on the input to specify the number of nodes. Often the input is generated by a human being, and human beings are just terrible at counting. That's why computers were invented.

Ignore the specified number of nodes and write code to count the nodes as you encounter them in the edge list.

For the same reason, take the "numbers" that identify the nodes that an edge connects in the input with suspicion. They should be regarded as node labels, and you should maintain and assign a node index whenever a new label is encountered in the input.

Looking at your example, the input code should generate a data structure ( of whatever kind you prefer: adjacency matrix, neighbor list, maps, vectors ... there are several choices each with its pros and cons ) that captures this

with edges represented as

CodePudding user response：

Just don't use the matrix representation of a graph in this case -- especially if the vertex indices are very sparse.

Use adjacency lists. Since node indices are not necessarily contiguous, use some kind of map, either a map or a unordered map, to associate indices with their adjacency lists. (Also don't actually use "lists" which are inefficient on modern hardware. Use resizable arrays, in C std::vector<T>'s)

Code below, along with a depth-first traversal.

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <span>

class graph {
    std::unordered_map<int, std::vector<int>> impl_;
public:
    void insert_edge(int u, int v) {
        impl_[u].push_back(v);
        impl_[v].push_back(u);
    }

    std::span<const int> neighbors(int u) const {
        auto iter = impl_.find(u);
        if (iter != impl_.end()) {
            return iter->second;
        } else {
            return {};
        }
    }
};

void dfs(const graph& g, int u, std::unordered_set<int>& visited) {
    if (visited.find(u) != visited.end()) {
        return;
    }
    visited.insert(u);

    std::cout << u << "\n";

    for (auto v : g.neighbors(u)) {
        dfs(g, v, visited);
    }
}

int main() {

    graph g;
    g.insert_edge(1, 3);
    g.insert_edge(6, 7);
    g.insert_edge(3, 7);
    g.insert_edge(3, 42);

    std::unordered_set<int> visited;
    dfs(g, 1, visited);

    return 0;
}