Explain adjacency matrix representation of a graph using a two-dimensional array and max int for absent edges, and implement insert, delete, and print with memory management in C++.

Use adjacency list to represent a graph by storing each vertex's neighbors in a list. Edges connect vertices and can be weighted; undirected edges appear in both vertex lists.

Compare list and matrix representations, noting that matrices allocate memory for all possible edges for dense graphs, while lists suit sparse graphs with efficient updates.

Explore breadth-first search by using a queue to discover all vertices reachable from a source, expanding the frontier by distance and labeling nodes with white, gray, or black.

Learn how to implement breadth-first search in C++ using a color state (white, gray, black), distance tracking, and a queue to explore a graph from a source vertex.

Learn depth-first search on graphs by implementing a recursive dfs, marking visited nodes with colors gray and black, exploring adjacent vertices, and backtracking with time proportional to vertices plus edges.

Explore predecessor subgraphs in graph algorithms using C++, learn how a DFS from a vertex yields its predecessor subgraph, identify ancestor and descendant relations, and analyze connectivity.

Classify edges in the predecessor subgraph, identifying ancestor, forward, and cross edges, then detect cycles by a color-based condition in depth-first search.

Explore topological sort for directed graphs and learn how a depth-first search based algorithm yields a topological order by pushing finished vertices to a list. Understand how cycles prevent ordering.

Implement topological sort on a graph by building a process list through the search function, managing an active process flag, and printing the resulting vertex order.

Learn to identify strongly connected components in a graph using topological sort, transpose the graph, and DFS to reveal SCCs.

Implement an algorithm to find strongly connected components in a graph using a transpose, process vertices in reverse order, and reconstruct components in C++.

Explore the shortest path problem in graphs, illustrated by a London road map, focusing on single source shortest path variations. Learn initialization and relaxation, and how negative cycles affect solutions.

Explore the Bellman-Ford algorithm for single-source shortest paths in graphs with negative weights. Learn initialization, V-1 relaxations, and a final negative-cycle check to detect cycles and compute distances.

Bellman-Ford algorithm implementation demonstrates initializing distances, performing V minus one relaxations, updating distances on each edge, and a final cycle check, illustrated on a sample graph.

Discover how to compute the single-source shortest path in dags using topological order, edge relaxations, and runtime analysis.

Dijkstra's algorithm finds shortest paths in weighted graphs, initializes distances from source to infinity, uses a queue-like data structure to extract the minimum-distance vertex, and relaxes edges to update distances.

Learn how to implement Dijkstra's algorithm for the shortest path with a priority queue, evolving from a linked-list approach to a binary-tree structure, with extract-min, relax edges, and distance updates.

Implement Dijkstra's algorithm to find the shortest path with a priority queue, updating vertex distances on a graph in a C++ implementation.

Learn how minimum spanning trees connect all vertices with minimum total edge weight in a weighted graph, using the cut concept and safe edges, and explore Kruskal and Prim algorithms.

Explore how Kruskal's algorithm builds a minimum spanning tree by adding the smallest edges that connect different components and uses a table of sets to avoid cycles.

Explore Kruskal's algorithm for building a minimum spanning tree by sorting edges by weight and using make-set, find, and union on a graph, with a guiding pseudocode example.

Implement Kruskal's algorithm for MST using a priority queue and union operations to build the MST and compute its total weight.

Learn Prim's algorithm for the minimum spanning tree, including cuts and adding edges from a chosen starting vertex, with a C++ pseudocode preview.

Implement Prim's algorithm for generating a minimum spanning tree by maintaining a priority queue of graph edges, relaxing candidates, and performing union operations on disjoint sets.

Explore modeling material flows with flow networks, capacity constraints, and flow conservation, then learn to compute maximum flow using single or multi-source networks via super sources and super sinks.

Explore the max flow min cut theorem, defining cuts as partitions that separate the source and sink and using edge capacities to compute the maximum flow via the minimum cut.