I hope you all are doing well. We have covered Strings, Arrays, Linked List, Trees, HashMap, Hashing, Searching and Sorting etc… till now in this series of 30 Days DSA.
In this segment, I will be covering the basic concepts of ‘Graphs’.
A Graph is a data structure that consists of the following two components:
- A finite set of vertices also called nodes.
- A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is not the same as (v, u) in case of a directed graph(digraph). The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.
Types of Graphs:
- Directed Graphs: The Directed graphs are such graphs in which edges are directed in a single direction.
- Undirected Graphs: Undirected graphs are such graphs in which the edges are directionless or in other words bi-directional. That is, if there is an edge between vertices u and v then it means we can use the edge to go from both u to v and v to u.
Use the following link to learn more about graphs and its representation.
The following link has clearly explained the basic and important concepts of graphs. You can refer it in series to learn more about basics of graphs:
Graph Representation Tutorials & Notes | Algorithms | HackerEarth
Graphs are mathematical structures that represent pairwise relationships between objects. A graph is a flow structure…
Important topics to be covered:
- Breadth-First Search
- Depth-First Search
- Detecting cycle in a graph
- Dijkstra’s algorithm for shortest path in weighted graph
- Minimum spanning tree
The concept of graphs and problems related to it can be a bit tricky but I suggest you not to leave the topic, rather consistently keep on learning and after solving few problems.. you will be well-versed with the concepts.
I’ll be sharing important questions along with personal notes and other sources for the topic in the next segment. Stay tuned!!!!