Graph

A non-linear data structure in which elements are arranged in a network

A node in a graph

A connection between two nodes in a graph

A graph in which every edge has a direction associated with it

A graph in which every edge has no direction associated with it

A graph in which every edge has a weight associated with it

A graph in which every node is connected to every other node

A tree that contains all nodes of a graph and a subset of its edges

O(V+E)

A way to sort the vertices of a directed acyclic graph based on their dependencies.

Note: A topological sort is only possible for a directed acyclic graph (DAG) as there should not be any cycles in it. It provides a linear ordering of the vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

A graph in which every node is connected to at least one other node

A sequence of nodes and edges in a graph

A path that ends where it starts

A graph in which the nodes can be divided into two sets such that every edge connects a node in one set to a node in the other set

To find the shortest path between two nodes in a weighted graph

To find the shortest path between two nodes in a weighted graph (it can also detect negative cycles in the graph)

To find the shortest path between all pairs of nodes in a weighted graph

To find the minimum spanning tree of a graph

To find the minimum spanning tree of a graph

A directed graph has edges with directions, while an undirected graph does not. In a directed graph, each edge has a direction associated with it, indicating that the edge only goes from one node to another. In an undirected graph, edges do not have directions, indicating that the edge goes both ways between two nodes.