Graph:
A non-linear data structure consisting of a set of vertices (nodes) and a set of edges.
Vertex (Node):
A fundamental unit in a graph, representing an entity.
Edge:
A connection between two vertices, representing a relationship.
Types of Graphs:
Directed Graph (Digraph):
Edges have a direction, indicating a one-way relationship.
Undirected Graph:
Edges have no direction, 1 indicating a two-way relationship.
Weighted Graph:
Edges have associated values (weights), representing costs, distances, or other quantities.
Unweighted Graph:
Edges have no associated weights.
Cyclic Graph:
A graph that contains one or more cycles. A cycle is a path that starts and ends at the same vertex.
Acyclic Graph:
A graph that contains no cycles.
Connected Graph:
A graph where there is a path between every pair of vertices.
Disconnected Graph:
A graph where some pairs of vertices are not connected by a path.
Edge and Vertex Properties:
Degree:
The number of edges connected to a vertex.
In-degree:
In a directed graph, the number of edges pointing towards a vertex.
Out-degree:
In a directed graph, the number of edges pointing away from a vertex.
Adjacent Vertices:
Two vertices connected by an edge.
Self-loop:
An edge that connects a vertex to itself.
Paths and Cycles:
Path:
A sequence of vertices connected by edges.
Cycle:
A path that starts and ends at the same vertex.
Simple Path:
A path in which no vertex is repeated.
Other Important Terms:
Adjacency Matrix:
A 2D array representation of a graph, indicating the presence or absence of edges between vertices.
Adjacency List:
A representation of a graph where each vertex has a list of its adjacent vertices.
Spanning Tree:
A subgraph that is a tree and connects all vertices of the original graph.
Minimum Spanning Tree (MST):
A spanning tree with the minimum total edge weight.