Page 84 - Data Structures Handout_Neat

4. Repeat until all vertices are connected.

Kruskal’s algorithm is efficient for sparse graphs because it focuses on edges rather

than vertices.
Comparison of Prim’s and Kruskal’s Algorithms

• Prim’s Algorithm: Works well for dense graphs, focuses on vertices, uses a priority

queue.

• Kruskal’s Algorithm: Works well for sparse graphs, focuses on edges, uses Union-

Find.
• Both guarantee the minimum spanning tree but differ in approach.

8.6 Applications of Graphs

Graphs are not just theoretical constructs; they are deeply embedded in real-world

systems. Their ability to represent complex relationships makes them indispensable in fields

ranging from social networking and computer science to transportation and logistics. In this

section, we will explore several major applications of graphs, highlighting how graph theory

provides efficient solutions to practical problems.

8.6.1 Social Networks

Social networks such as Facebook, Twitter, and LinkedIn can be modeled as graphs

where vertices represent users and edges represent connections (friendships, follows, or

professional links). These graphs are often massive, containing millions of vertices and billions
of edges. Graph algorithms help analyze these networks to find communities, influencers, and

shortest paths between users.

For example, finding the shortest path between two users can reveal how closely
connected they are (the famous “six degrees of separation” problem). Detecting communities

involves identifying clusters of users who are more connected to each other than to the rest

of the network.

Example: Modeling a Social Network in C++

84