Graphs in Data Structures

These flashcards cover fundamental concepts and terminologies related to graphs in data structures.

Graph (in Data Structure)

A non-linear data structure consisting of nodes (vertices) and edges that represent relationships between objects/entities.

Edge

A connection between two nodes in a graph that denotes the relationship between them.

Node (or Vertex)

An individual object or entity within a graph.

Directed Graph

A graph where edges have specific directions.

Undirected Graph

A graph where edges have no specific directions.

Weighted Graph

A graph in which edges have associated numerical values (weights).

Unweighted Graph

A graph where edges do not have associated numerical values or weights.

Cyclic Graph

A graph that contains at least one cycle, which is a path that starts and ends at the same node without revisiting any nodes.

Acyclic Graph

A graph that does not contain any cycles.

Adjacency Matrix

A 2-D array representation of a graph where rows and columns represent nodes, and a value at arr(u,v) indicates the presence of an edge between nodes u and v.

Adjacency List

A representation of a graph where each node has an associated list containing its neighboring nodes.

Breadth First Search (BFS)

A traversal algorithm that explores a graph level-by-level, using a queue.

Depth First Search (DFS)

A traversal algorithm that explores a graph branch-by-branch, using a stack.

Space Complexity of Adjacency Matrix

O(n^2) where n is the number of nodes in the graph.

Space Complexity of Adjacency List

O(V + E) where V is the number of vertices and E is the number of edges.