Graphs and Graph Theory

A non-linear data structure that represents connections between elements called vertices (nodes) using links called edges (arcs).

A single element in a graph, representing a data point or location.

A connection between two vertices in a graph, representing a relationship or link.

An edge that allows travel in both directions between two vertices.

An edge that allows travel in only one direction between two vertices.

An edge that has an associated value or cost associated with traversing it.

A graph consisting entirely of undirected edges.

A graph consisting entirely of directed edges.

In a complete graph, every vertex is directly connected to every other vertex.

A graph where every vertex has the same number of connections (degree).

A graph that forms a closed loop. It starts and ends at the same vertex and all vertices in between are unique.

A graph without any cycles. It has no closed loops.

A graph where each edge has a numerical value, representing a distance, weight, or cost.

An edge pointing away from a vertex. In a directed graph, it indicates the direction of flow.

An edge pointing towards a vertex. In a directed graph, it indicates the direction of flow.

The total number of edges connected to a vertex.

A closed walk in which no vertex (except the initial and final vertex) appears more than once.

A graph S is a subgraph of a graph G if all vertices and edges of S are in G, and each edge in S has the same endpoints as in G.

A graph is connected if there is at least one path between every pair of vertices. Otherwise, it's disconnected.

The number of edges connected to a node in an undirected graph.

The number of edges connecting to a node in a directed graph.

The number of edges going outside from a node in a directed graph.

A way to represent a graph using a matrix where rows and columns represent vertices. A '1' indicates an edge exists, '0' indicates no edge.

A way to represent a graph using a list where each vertex points to its connected neighbors.

Matrix representation where each element A[i][j] indicates whether there's an edge between vertices i and j. For directed graphs, A[i][j] = 1 if there's an edge from i to j, else 0.

Similar to adjacency list but each edge (u, v) is represented twice: once in u's list and once in v's list. This allows marking an edge as visited easily by modifying the edge node.

Representing weighted edges in adjacency matrices: the A[i][j] element holds the weight if there's an edge from i to j, else 0 or infinity.

Representing weighted edges in adjacency lists: each node in the list has an extra field for storing the weight of the corresponding edge.

A weighted graph is often called a network. It represents various real-world scenarios like road maps, communication networks, etc.

An algorithm that explores a graph by traversing as deeply as possible along a path before backtracking to explore other paths.

A data structure that follows the Last-In, First-Out (LIFO) principle. Elements are added and removed from the top.

A connected subgraph of a graph that includes all the vertices of the original graph.

The process of systematically visiting and marking vertices in a graph, starting from a given vertex, and following edges to discover new vertices.

Moving back to a previously visited vertex in a depth-first search to explore alternative paths.

The time required to complete a specific algorithm or operation. It is expressed using Big O notation.

A graph traversal algorithm that starts at a specified vertex, visits all its unvisited neighbors, then their neighbors, and so on, following a breadth-first approach.

A data structure used in BFS to store vertices that need to be visited, maintaining a FIFO (First-In, First-Out) order.

The time complexity of BFS is O(n^2) when using an adjacency matrix representation of the graph, where n is the number of vertices.

The time complexity of BFS is O(e) when using adjacency lists to represent the graph, where e is the number of edges.