Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. 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.
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.
Following is C++ code that uses BFS for finding reachability of second vertex from first vertex.
// 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 representation class Graph { int V; // No. of vertices list<int> *adj; // Pointer to an array containing adjacency lists public: Graph(int V); // Constructor void addEdge(int v, int w); // function to add an edge to graph bool isReachable(int s, int d); // returns true if there is a path from s to 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’s 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); } } } return false; }
From:
http://www.geeksforgeeks.org/find-if-there-is-a-path-between-two-vertices-in-a-given-graph/
相关推荐
A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another; see graph (mathematics) ...
The result is an In Action book that differs a bit from others: it takes a while to get started, with the first five chapters laying the groundwork, and there are a number of interesting examples ...
The basic representation of a graph of n vertices is the adjacency matrix A where A(i,j)=1 if vertex i is linked to vertex j. A graph often comes with a geometric realization in R^d which an (d,n) ...
BC网络上相邻顶点间独立路径的构造算法,程宝雷,樊建席,一一对应连接互连网络是超立方体变型族,包括超立方体、扭立方体、交叉立方体、莫比乌斯立方体及局部扭立方体等。本文研究了n维��
formulation is that it admits a random graph interpretation, showing that spectral clustering may be viewed as maximum likelihood partitioning under the assumption that the data is an instance of a ...
1) Given a set V of vertices and a set E of edges with weights in a multistage undirected graph G=(E,V) like below, please find the shortest path between any two vertices using dynamic programming ...
If any two vertices are connected and a tree, then we call it a spanning tree. If it is a undirected graph with weights, then the spanning tree with the smallest sum of weights is called MST (minimum...
In this paper we present a computational model suitable for this task. Programs are expressed as a sequence of iterations, in each of which a vertex can receive messages sent in the previous iteration...
Frequently it is said, “Graphs can do anything,” or at least, “There are a bunch of different things you can do with graphs.” That says nothing, of course, so in this book we show a number of ...
It mainly through the analysis of SPIG (the shortest path increment), NCC (the number of sub connected components) and VAR (the variance of the vertices in a connected component) to determine the ...
A graph is an l(1)-graph if its vertices can be labeled by binary vectors in such a way that the Hamming distance between the binary addresses is, up to scale, the distance in the graph between the ...
For the next m lines, each line contains two integers ui and vi, which means there is an undirected edge between ui and vi (1≤ui,vi≤n,ui≠vi). The sum of values of n in all test cases doesn't ...
If a path is stored, the file is extracted to the appropriate directory, which must exist. PAQ6 does not create directories. If the file to be extracted already exists, it is not replaced; rather it ...
JanusGraph is a highly scalable graph database optimized for storing and querying large graphs with billions of vertices and edges distributed across a multi-machine cluster. 包含源码
The scale of these graphs – in some cases billions of vertices, trillions of edges – poses challenges to their efficient processing. Apache Spark GraphX API combines the advantages of both data-...
For the two-dimensional object silhouettes, in this study, we present a one-dimensional descriptor which in theory remains absolutely invariant under affine transforms. The proposed descriptor ...
Projective texture mapping is useful in a variety of lighting techniques, including shadow mapping [4]. This document provides some background and describes the steps involved in projective texture ...
Statistical Mechanics of complex networks Statistical Mechanics of complex networks Statistical Mechanics of complex networks
Sum of Degrees of Vertices TheoremTheorem (Sum of Degrees of Vertices Theorem)Suppose a graph has n vertices with degrees d1, d2, d3, . . . , dn. Add together all degrees to get a new number d1 + d2 +...