Directed Graph

Why do you need to have 3 states (“Visited, &… Anonymous - Aug 4, 2016Why do you need to have 3 states (“Visited, “Unvisited”, and “Visiting”)? It seems like we do the same thing - adding the node to the queue - if it’s unvisited, but there is no functional distinction between visited and visiting (in either state we skip it - we won’t enqueue it and we won’t check against it). [Read More]

Problem : Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. Solution We have already seen solution to connectivity in undirected graph via bfs. Now lets see it on directed graph. BFS to check the connectivity public enum State { Unvisited, Visited, Visiting; } public static boolean search(Graph g, Node start, Node end) { LinkedList<Node> q = new LinkedList<Node>(); // operates as Stack for (Node u : g. [Read More]

Graphs consist of 2 ingredients : Vertices (V) , also called nodes and can be pictured as dots Edges (E) , the line connecting the nodes. Types of Graphs Depending on the edges, there two types of graphs: Undirected Graphs - A graph that entail edges with ordered pair of vertices, however it does not have direction define. Example of such a graph is the ‘Family tree of the Greek gods’ **Directed Graphs (**aka Arcs) - Directed Graph: A graph that entail edges with ordered pair of vertices and has direction indicated with an arrow. [Read More]

There are two possible traversal methods for a graph: i. Breadth-First Traversal ii. Depth-First Traversal i. Breadth-First Traversal: Traverse all the vertices starting from a given ‘start vertex’. Hence, such a traversal follows the ‘neighbour-first’ principle by considering the following: - No vertex is visited more than once - Only those vertices that can be reached are visited Importantly here, we make use of the Queue data structure. In effect, we house the vertices in the queue that are to be visited soon in the order which they are added to this queue i. [Read More]