In data structures, graphs are a fundamental concept used to represent networks of interconnected nodes or vertices. They consist of two main components: vertices (nodes) and edges. Here are some key definitions related to graphs:
- Vertex (Node): A fundamental unit of a graph, representing a data point or an entity. In some contexts, vertices can hold additional information.
- Edge: A connection between two vertices, indicating a relationship or interaction. Edges can be directed (meaning they have a specific direction) or undirected (meaning they don’t have a specific direction).
- Directed Graph (DiGraph): A graph in which edges have a specific direction from one vertex to another. This means that there is a clear source and target for each edge.
- Undirected Graph: A graph in which edges have no specific direction. If there is an edge between vertex A and vertex B, it implies that there is also an edge between B and A.
- Weighted Graph: A graph in which each edge has an associated numerical value or weight. These weights can represent things like distances, costs, or any other relevant metric.
- Degree: For a given vertex, the degree is the number of edges connected to it. In directed graphs, there are two types of degrees: in-degree (number of incoming edges) and out-degree (number of outgoing edges).
- Adjacent: Two vertices are said to be adjacent if there is an edge connecting them.
- Path: A sequence of vertices in which each adjacent pair is connected by an edge. The length of a path is the number of edges it contains.
- Cycle: A path that starts and ends at the same vertex, without traversing any edge more than once.
- Connected Graph: A graph in which there is a path between every pair of vertices.
- Disconnected Graph: A graph that is not connected, meaning there are at least two vertices that do not have a path between them.
- Subgraph: A graph formed by a subset of the vertices and edges of another graph.
- Spanning Tree: A subgraph of a graph that includes all the vertices of the original graph and forms a tree (no cycles).
- Tree: A connected acyclic graph. In a tree, there is exactly one path between any two vertices.
- Forest: A disjoint set of trees or a collection of trees.
- Bipartite Graph: A graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.
- Graph Traversal: The process of visiting all the vertices and edges of a graph in a systematic way. Common traversal algorithms include depth-first search (DFS) and breadth-first search (BFS).
- Topological Sort: An ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge from vertex A to vertex B, A comes before B in the ordering.
- Regular Graph: A regular graph is a type of undirected graph where each vertex has the same degree, meaning that every vertex in the graph has an equal number of adjacent edges.
Formally, a graph G is said to be k-regular if every vertex in G has degree k. In other words, every vertex is connected to exactly k other vertices.