Graph
Whenever I want to study or talk about Graph, I think, I am doing the hardest thing in the world, however, we should always remember that Graph is one of the interesting algorithms which variety of sciences involved with it(such as: Opte Project and … .), Lets have short look on initial explanations of Graph.
Why study graph algorithms?
- Thousands of practical applications.
- Hundreds of graph algorithms known.
- Interesting and broadly useful abstraction.
- Challenging branch of computer science and discrete math.
In simply put, Graph is a set of vertices connected pairwise by edges, So, What is Vertices?
Interconnected objects in a graph are called vertices and also, known as nodes.
And what is Edges? Edges are the links that connect the vertices.
We have two critical approaches for traversing on the graph which names are, DFS(Depth-Frist Search) and BFS(Breadth-First Search). Systematically we follow two ways for search through a graph and the big different between these two ways is:
Depth-first Search, Put unvisited vertices on a Stack.
Breadth-first Search, Put unvisited vertices on a Queue
Some question that we should think about them in the Graph is:
- Is there a path between vertices?
- What is the shortest path between vertices?
- Is there a cycle in the graph?
- Is there a way to connect all of the vertices?
- …
Let me look at the basic model of DFS and BFS. first, we need to define a vertices(node) model, So, look at bottom code.
and for make graph look at bottom code:
In bottom code, DFS starts a graph’s traversal by visiting an arbitrary vertex(node) and marking is as visited in a “visited” variable. On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the on it are currently in. in the end, the traversing continues until a vertex doesn't have unvisited adjacent vertices and finally print vertices.
In the bottom code, we visit the same operation of above code, But because we want to use BFS, we implement with Queue, so, we traversing by visiting an arbitrary vertex(node) and marking is as visited in a “visited” variable and next we push the vertex on Queue(Enqueue) and checking to the condition that our Queue is not empty, call Dequeue method and after that, we are writing in the console and next, On each iteration, the algorithm proceeds to an unvisited vertex and add to Queue until we don't have an unvisited adjacent vertex.
To access to the completed source, please check Room Project on this link, also you can find different challenges approach of HackerRank in the mentioned Link.
Resources: Algorithms Robert Sedgewick
