`

Find if there is a path between two vertices in a directed graph

 
阅读更多

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/

分享到:
评论

相关推荐

    An Introduction to Combinatorics and Graph Theory

    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) ...

    Spark Graphx in Action

    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 ...

    Toolbox Graph A toolbox to perform computations on graph.

    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 ...

    Kruskal_MATLAb.zip

    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...

    Top-k Structure Holes Detection Algorithm in Social Network

    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 ...

    l&quot;1-embeddability under the edge-gluing operation on graphs

    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源码分析.pdf

    Spark GraphX源码分析: 在大数据时代背景下,图计算成为了一个重要的研究领域,而Apache Spark的GraphX库是处理大规模图数据的关键工具之一。GraphX在Spark的基础上实现了图并行计算,并提供了丰富的图操作接口。...

    kgb档案压缩console版+源码

    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-full-0.5.2.zip

    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. 包含源码

    C++深度遍历

    - **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:** - **...

    图的最小生成树算法.docx

    此外,Prim 算法也可以用于解决其他问题,例如 finding the shortest path between two vertices in a weighted graph 等。 图的最小生成树算法是一种重要的算法,在计算机科学和信息技术领域中有广泛的应用。

    Apache Spark Graph Processing(PACKT,2015)

    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-...

    Statistical Mechanics of complex networks

    ### 统计力学在复杂网络中的应用 #### 引言 复杂网络的研究是现代网络科学的一个重要分支,它关注的是由大量相互连接的节点组成的系统的行为。这些系统可以包括社交网络、生物网络、互联网等。...

    Sum of Degrees of Vertices Theorem - Slides-计算机科学

    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 基本介绍

    GraphX的核心概念是`Graph`,它由顶点集合(Vertices)和边集合(Edges)组成。 #### 二、GraphX的基本概念 1. **Graph对象**:在GraphX中,一个图被表示为`Graph`类的对象,该对象包含两个主要组成部分: - **...

    spark graphX实战 中英文两版

    2. ** Directed vs Undirected**: GraphX支持有向和无向图,有向图的边有方向,而无向图的边没有方向。 3. **Properties**: 顶点和边都可以有属性,这些属性可以是任何类型的数据,如整数、字符串或更复杂的数据结构...

Global site tag (gtag.js) - Google Analytics