Graph

A collection of nodes (vertices) connected by edges

Introduction

A Graph is a non-linear data structure used to represent a set of objects (nodes or vertices) and their connections (edges). Graphs are widely used to model relationships in networks, such as social networks, transportation systems, web page links, and more.

Components of Graph

Vertices (Nodes):

  • These are the individual entities in the graph.

  • Represented as points or circles.

Edges (Links):

  • These are the connections between pairs of vertices.

  • Represented as lines connecting the vertices.

Weight:

  • Some graphs assign a value or weight to edges, representing a cost, distance, or strength of the connection.

Types of Graph

Directed Graph

  • Each edge has a direction, going from one vertex to another.

Undirected Graph:

  • Edges have no direction; connections are mutual.

Weighted Graph:

  • Edges have weights representing costs, distances, or other values.

Unweighted Graph:

  • Edges are treated equally, with no weights assigned.

Cyclic Graph:

  • Contains at least one cycle (a path that starts and ends at the same vertex).

Acyclic Graph:

  • Does not contain any cycles.