What is the Graphs in DSA?
Graphs in DSA are used for model pairwise relationship between objects. They consists of vertices (also called between objects. They consists of vertices (also called nodes) and edges (connection between vertices). Graphs can represent a variety of system in the real world, such as social networks, transportation network, and computer network.
Key Components of Graphs
- Vertices (Nodes)
- The Fundamental units of a graph.
- Represents entities in the graph, such as people, cities, or computer .
- Edges
- Connect pairs of vertices.
- Represents relationship or connections between the entities.
- Can be directed (one-way) or undirected (two-way).
- Degree
- The degree of a vertex is the number of edges connected to it.
- In directed graphs, there are in-degree (number of incoming edges) and out-degrees (number of out going edges.
Graphs Representation
- Adjacency Matrix
- A 2D array where each cell (i, j) indicates the presence ( and possibly the weight) of an edge between vertex i and j.
- Efficient for dense graphs (graphs with many edges).
- Adjacency List
- An array of list. Each list corresponds to a vertex and contains all adjacent vertices.
- Efficient spare graphs (graph with fewer edges).