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.
Solution 1: DFS
public static boolean pathExistedDFS(DirectedGraph g, int src, int dest) { boolean[] visited = new boolean[g.V]; return dfsUtil(g, visited, src, dest); } private static boolean dfsUtil(DirectedGraph g, boolean[] visited, int src, int dest) { if(src == dest) return true; visited[src] = true; for(int u : g.adj[src]) { if(!visited[u] && dfsUtil(g, visited, u, dest)) { return true; } } return false; }
Solution 2: BFS
public static boolean pathExistedBFS(DirectedGraph g, int src, int dest) { if(src == dest) return true; boolean[] visited = new boolean[g.V]; Queue<Integer> queue = new LinkedList<>(); queue.offer(src); visited[src] = true; while(!queue.isEmpty()) { int v = queue.poll(); for(int u:g.adj[v]) { if(u == dest) return true; if(!visited[u]) { visited[u] = true; queue.offer(u); } } } return false; } public static void main(String[] args) { DirectedGraph g = new DirectedGraph(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 = 0, v = 2; if(pathExistedBFS(g, u, v)) { System.out.println("path exists from " + u + " to " + v); } else { System.out.println("path does not exist from " + u + " to " + v); } }
Reference:
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) ...
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...
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 ...
Spark GraphX源码分析: 在大数据时代背景下,图计算成为了一个重要的研究领域,而Apache Spark的GraphX库是处理大规模图数据的关键工具之一。GraphX在Spark的基础上实现了图并行计算,并提供了丰富的图操作接口。...
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. 包含源码
- **Traversal Order:** DFS visits vertices in a depthward motion and uses a stack to remember to get back to visited vertices. ### 2. Implementation of DFS in C++ **Data Structures Used:** - **...
此外,Prim 算法也可以用于解决其他问题,例如 finding the shortest path between two vertices in a weighted graph 等。 图的最小生成树算法是一种重要的算法,在计算机科学和信息技术领域中有广泛的应用。
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-...
### 统计力学在复杂网络中的应用 #### 引言 复杂网络的研究是现代网络科学的一个重要分支,它关注的是由大量相互连接的节点组成的系统的行为。这些系统可以包括社交网络、生物网络、互联网等。...
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 +...
GraphX的核心概念是`Graph`,它由顶点集合(Vertices)和边集合(Edges)组成。 #### 二、GraphX的基本概念 1. **Graph对象**:在GraphX中,一个图被表示为`Graph`类的对象,该对象包含两个主要组成部分: - **...
2. ** Directed vs Undirected**: GraphX支持有向和无向图,有向图的边有方向,而无向图的边没有方向。 3. **Properties**: 顶点和边都可以有属性,这些属性可以是任何类型的数据,如整数、字符串或更复杂的数据结构...