{"id":26333,"date":"2017-10-26T21:06:37","date_gmt":"2017-10-26T15:36:37","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26333"},"modified":"2017-10-26T21:06:37","modified_gmt":"2017-10-26T15:36:37","slug":"find-path-two-vertices-directed-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/find-path-two-vertices-directed-graph\/","title":{"rendered":"C Programming – Find if there is a path between two vertices in a directed graph"},"content":{"rendered":"

Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. <\/span>For example, in the following graph, there is a path from vertex 1 to 3. As another example, there is no path from 3 to 0.<\/p>\n

We can either use Breadth First Search (BFS) or Depth First Search (DFS) to find path between two vertices. Take the first vertex as source in BFS (or DFS), follow the standard BFS (or DFS). If we see the second vertex in our traversal, then return true. Else return false.<\/p>\n

Following are C++,Java and Python codes that use BFS for finding reachability of second vertex from first vertex.<\/p>\n

C++ Programming<\/p>\n

<\/div> 
\/\/ C++ program to check if there is exist a path between two vertices\/\/ of a graph.#include<iostream>#include <list>using namespace std; \/\/ This class represents a directed graph using adjacency list \/\/ representationclass Graph{    int V;    \/\/ No. of vertices    list<int> *adj;    \/\/ Pointer to an array containing adjacency listspublic:    Graph(int V);  \/\/ Constructor    void addEdge(int v, int w); \/\/ function to add an edge to graph    bool isReachable(int s, int d);  }; Graph::Graph(int V){    this->V = V;    adj = new list<int>[V];} void Graph::addEdge(int v, int w){    adj[v].push_back(w); \/\/ Add w to v\u2019s list.} \/\/ A BFS based function to check whether d is reachable from s.bool Graph::isReachable(int s, int d){    \/\/ Base case    if (s == d)      return true;     \/\/ Mark all the vertices as not visited    bool *visited = new bool[V];    for (int i = 0; i < V; i++)        visited[i] = false;     \/\/ Create a queue for BFS    list<int> queue;     \/\/ Mark the current node as visited and enqueue it    visited[s] = true;    queue.push_back(s);     \/\/ it will be used to get all adjacent vertices of a vertex    list<int>::iterator i;     while (!queue.empty())    {        \/\/ Dequeue a vertex from queue and print it        s = queue.front();        queue.pop_front();         \/\/ Get all adjacent vertices of the dequeued vertex s        \/\/ If a adjacent has not been visited, then mark it visited        \/\/ and enqueue it        for (i = adj[s].begin(); i != adj[s].end(); ++i)        {            \/\/ If this adjacent node is the destination node, then             \/\/ return true            if (*i == d)                return true;             \/\/ Else, continue to do BFS            if (!visited[*i])            {                visited[*i] = true;                queue.push_back(*i);            }        }    }         \/\/ If BFS is complete without visiting d    return false;} \/\/ Driver program to test methods of graph classint main(){    \/\/ Create a graph given in the above diagram    Graph g(4);    g.addEdge(0, 1);    g.addEdge(0, 2);    g.addEdge(1, 2);    g.addEdge(2, 0);    g.addEdge(2, 3);    g.addEdge(3, 3);     int u = 1, v = 3;    if(g.isReachable(u, v))        cout<< "\\n There is a path from " << u << " to " << v;    else        cout<< "\\n There is no path from " << u << " to " << v;     u = 3, v = 1;    if(g.isReachable(u, v))        cout<< "\\n There is a path from " << u << " to " << v;    else        cout<< "\\n There is no path from " << u << " to " << v;     return 0;}<\/code><\/pre> <\/div>\n
Output:<\/p>\n
 There is a path from 1 to 3\r\n There is no path from 3 to 1<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
C Programming – Find if there is a path between two vertices in a directed graph – check whether there is a path from the first given vertex to second. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,82927,1,78385,73906],"tags":[78422,78421,78420,78419,78424,78423,78417,78418],"class_list":["post-26333","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-2","category-coding","category-connectivity","category-graph-algorithms","tag-check-if-path-exists-between-two-nodes","tag-find-all-paths-between-two-nodes-in-a-graph-c","tag-find-all-paths-between-two-nodes-in-a-graph-java","tag-find-all-paths-from-source-to-destination","tag-find-all-paths-from-source-to-destination-java","tag-find-all-paths-in-a-directed-graph","tag-find-all-possible-paths-between-two-vertices-on-a-graph","tag-find-path-between-two-nodes-in-a-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26333","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26333"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26333\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}