They are fundamental data structures, used to model a set of connections. They consist of vertices (also called nodes) and edges that connect these vertices. Graphs can be used to represent networks such as social connections, roads between cities, or pathways in algorithms.
Undirected: edges have no direction, if vertex A is connected to B, B is also connected to A.
Directed: edges have a direction, if vertex A points to B, it doesn’t mean a directed path from B to A also exists, unless specified.
Weighted: edges have weights associated with them, that can represent distance, cost, etc.
Unweighted: edges do not hold any weights.
Adjacency Matrix: represents graph as a 2D array where each row and column represents a vertex/node. If there is an edge between node i and node j then the element at [i][j] will have a value that indicates that there is an edge like 1 or actual weight of the edge. If there is no edge, value will be 0 or infinity.
Adjacency List: represents graph as a list where each index represents a vertex/node and their element at each index are lists that contain nodes connected to that node.
Graph Traversal refers to the process of visiting every vertex in a graph in a systematic way. Traversal methods can be used for various applications impacting performance depending on the graph’s structure.