Determine whether a vertex is self loop in graph-CodePudding

I am struggling with a problem that I haven't found a solution by searching, I hope someone can help me to unblock me : Given a vertex, I want to check if it form a self loop in a directed graph or not in O(|V|).

Here s a brief implementation of my graph Class :

template <class T>
class Digraph
{
public:
    Digraph();
    ~Digraph();

bool loop(T u) const;

private:
    std::map<T, std::set<T>> graph;
}

CodePudding user response：

You could try searching for topological sorting of directed graphs.

As far as I know, if a directed graph has a cycle, it cannot be topologically sorted, so the topological sorting algorithm can be used to detect whether there is a cycle.

The following is a possible implementation, where adj is an array in the form of an adjacency linked list. adj[i] is a vector that represents all neighbor nodes of node i. s is the current node recSt is a stack.

bool DFSRec(vector<vector<int>> adj, int s, vector<bool> visited, vector<bool>  recSt)
{
  visited[s] = true;
  recSt[s] = true;
  for (int u : adj[s]) {
    if (visited[u] == false && DFSRec(adj, u, visited, recSt) == true)
      return true;
    else if (recSt[u] == true)
      return true;
  }
  recSt[s] = false;
  return false;
}
bool DFS(vector<vector<int>> adj, int V) {
  vector<bool> visited(V, false);
  vector<bool> recSt(V, false);
  for (int i = 0; i < V; i  )
    if (visited[i] == false)
      if (DFSRec(adj, i, visited, recSt) == true)
        return true;
  return false;
}

and there is another one


vector<int>kahns(vector<vector<int>> g) {
  int n = g.size();
  vector<int> inDegree(n);
  for (auto edges : g)
    for (int to : edges)
      inDegree[to]  ;
  queue<int> q;  //q里包含的永远是入度为0的node
  for (int i = 0; i < n; i  )
    if (inDegree[i] == 0)
      q.push(i);
  int index = 0;
  vector<int> order(n);
  while (!q.empty()) {
    int at = q.front(); q.pop();
    order[index  ] = at;
    for (int to : g[at]) {
      inDegree[to]--;
      if (inDegree[to] == 0)
        q.push(to);
    }
  }
  if (index != n)return {}; //has cycle
  return order;
}

Here is a link that might be useful
here is some video that may related
https://www.youtube.com/watch?v=eL-KzMXSXXI
https://www.youtube.com/watch?v=cIBFEhD77b4

CodePudding user response：

Self loop means that vetrex is connected to itself by a single edge. Your graph is represented with adjacency list which means that for each vertex it contains a list (std::set in your case) of connected vertices.

So, we can implement check for a self loop like this:

template <class T>
class Digraph
{
public:
    Digraph();
    ~Digraph();

    bool loop(T u) const {
        const auto it = graph.find(u);
        if (it == graph.end()) {
            return false; // there is no such vertex in the graph at all
        }
        return it->second.find(u) != it->second.end();
    }
private:
    std::map<T, std::set<T>> graph;
}

Out of your question, but I want to mention that usually to implement adjacency list representation of graph, std::unordered_map and std::unordered_set are used as those have faster lookups comparing to std::map and std::set, but keep in mind that your type T should have std::hash implemented in this case. Moreover, I'd suggest to pass u param as const reference const T& u to loop method. So with all the suggestions your class can look like next:

template <class T>
class Digraph
{
public:
    Digraph();
    ~Digraph();

    bool loop(const T& u) const {
        const auto it = graph.find(u);
        if (it == graph.end()) {
            return false; // there is no such vertex in the graph at all
        }
        return it->second.find(u) != it->second.end();
    }
private:
    std::unordered_map<T, std::unordered_set<T>> graph;
}