Graphs Definitions

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:

  1. Vertex (Node): A fundamental unit of a graph, representing a data point or an entity. In some contexts, vertices can hold additional information.
  2. 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).
  3. 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.
  4. 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.
  5. 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.
  6. 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).
  7. Adjacent: Two vertices are said to be adjacent if there is an edge connecting them.
  8. 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.
  9. Cycle: A path that starts and ends at the same vertex, without traversing any edge more than once.
  10. Connected Graph: A graph in which there is a path between every pair of vertices.
  11. Disconnected Graph: A graph that is not connected, meaning there are at least two vertices that do not have a path between them.
  12. Subgraph: A graph formed by a subset of the vertices and edges of another graph.
  13. Spanning Tree: A subgraph of a graph that includes all the vertices of the original graph and forms a tree (no cycles).
  14. Tree: A connected acyclic graph. In a tree, there is exactly one path between any two vertices.
  15. Forest: A disjoint set of trees or a collection of trees.
  16. Bipartite Graph: A graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.
  17. 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).
  18. 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.
  19. 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.
error: You can only copy the programs code and output from this website. You are not allowed to copy anything else.