[go: up one dir, main page]
Scribd
Upload
21 views2 pages

Graph Basics

A graph is a data structure consisting of vertices (nodes) and edges connecting them, defined as G = (V, E). Key terminology includes concepts like adjacency, degree, paths, cycles, and types of graphs such as directed, undirected, weighted, and unweighted. Graphs can be represented using adjacency matrices, adjacency lists, or edge lists, each with its own advantages and disadvantages.

Uploaded by

Rahamatulla Firdous
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views2 pages

Graph Basics

A graph is a data structure consisting of vertices (nodes) and edges connecting them, defined as G = (V, E). Key terminology includes concepts like adjacency, degree, paths, cycles, and types of graphs such as directed, undirected, weighted, and unweighted. Graphs can be represented using adjacency matrices, adjacency lists, or edge lists, each with its own advantages and disadvantages.

Uploaded by

Rahamatulla Firdous
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Graph: Basic Terminology and Representation

Definition of a Graph

A graph is a data structure used to model pairwise relations between objects. A graph G is defined as:
G = (V, E)

• V: A set of vertices or nodes.


• E: A set of edges connecting pairs of vertices.

Basic Terminology

Term Description

Vertex (Node) A fundamental unit represented as a dot or circle in a graph.

Edge (Link) A connection between two vertices. Can be directed or undirected.

Adjacency Two vertices are adjacent if they are connected by an edge.

Number of edges incident to a vertex.


Degree of a Vertex - In-degree: Incoming edges (for directed graphs).
- Out-degree: Outgoing edges.

Path A sequence of vertices where each adjacent pair is connected by an edge.

Cycle A path where the starting and ending vertices are the same.

Connected Graph A graph is connected if there is a path between every pair of vertices.

Disconnected Graph A graph with at least two vertices with no path connecting them.

Weighted Graph A graph where each edge has a weight or cost.

Unweighted Graph All edges are assumed to have equal weight (or no weights).

Directed Graph (Digraph) Edges have a direction, going from one vertex to another.

Undirected Graph Edges have no direction.

Loop An edge that connects a vertex to itself.

Multigraph A graph with multiple edges between the same pair of vertices.

Graph Representation

1. Adjacency Matrix
o A 2D array of size V x V.
o If there is an edge from vertex i to vertex j, then matrix[i][j] = 1 (or weight).
o Pros: Easy to implement and check if an edge exists.
o Cons: Requires O(V²) space.
2. Adjacency List
o An array of lists.
o Each vertex has a list of all vertices it is adjacent to.
o Pros: Space efficient for sparse graphs (O(V + E)).
o Cons: Slightly more complex to implement.
3. Edge List
o A list of all edges represented as pairs/triplets (u, v) or (u, v, w).
o Useful for algorithms like Kruskal’s.

Types of Graphs

• Simple Graph: No loops or multiple edges.


• Complete Graph: Every pair of distinct vertices is connected by a unique edge.
• Sparse Graph: Few edges compared to the number of vertices.
• Dense Graph: Number of edges is close to the maximum possible.

Example

Let G = (V, E) where


V = {A, B, C, D},
E = {(A, B), (A, C), (B, D)}

Adjacency List:

A→B→C
B→D
C→
D→

Adjacency Matrix:

ABCD
A[0110]
B[0001]
C[0000]
D[0000]

You might also like