📌Data Structures the Fun Way - 15. Graphs
Graphs are structures where multiple objects (nodes) are connected to each other through relationships (edges)
🔖 5.1 What is a Graph?
Graph Concept
Graphs consist of nodes (vertices) and edges.
Unlike other data structures, graphs weren't created to optimize specific operations, but to directly represent relationships or flows in the real world.
Characteristics of Graphs
Edges can have directionality or not
If directed: flow is determined like A → B
If undirected: bidirectional connection like A - B
Edges can have weights (costs)
e.g., time or distance to go from A to B
Complex relationships can be expressed by combining directionality and weights.
Methods to Represent Graphs in Memory
Adjacency Matrix: Represented as 2D array. Efficient when there are few nodes and many edges
Adjacency List: Each node manages connected nodes as a list. Suitable for sparse graphs with few edges
Both methods can be flexibly used depending on whether they have direction and weights.
🔖 5.2. Dijkstra's Algorithm - Finding Shortest Path
What Kind of Algorithm?
An algorithm that finds shortest distances from one node to all other nodes.
Works on weighted graphs and doesn't allow negative weights.
How It Works
Create an array to store distances from start node to each node, setting all distances to infinity
Set start node distance to 0 and manage a set of unvisited nodes
Select and visit the node with shortest distance among unvisited nodes
Update distance information of neighboring nodes connected to that node as current distance + edge weight
Repeat the above process until all nodes are visited
Summary
Continues updating shortest distance information found so far.
Can be efficiently implemented using priority queues (heaps)
🔖 5.3. Prim's Algorithm - Finding Minimum Spanning Tree
What is a Minimum Spanning Tree?
Refers to a tree structure that connects all nodes while minimizing the sum of all edge weights.
No cycles and all nodes are connected.
What is Prim's Algorithm?
A representative algorithm for finding minimum spanning trees
Looks similar to Dijkstra's algorithm but aims for minimum cost connections rather than shortest distances.
How It Works
Start from any node.
Select the edge with smallest weight that can connect to the current tree and add nodes one by one.
Find the cheapest edge based on the newly added node and connect it.
Repeat until all nodes are included in the tree.
Summary
Method of adding nodes that can be connected most cheaply to the existing tree one by one.
🔖 5.4. Kahn's Algorithm - Topological Sorting
What is Topological Sorting?
Used when processing tasks where order is important.
e.g., when one task must finish before the next task starts.
To express this, a directed acyclic graph (DAG) without cycles is needed.
What is Kahn's Algorithm?
An algorithm that performs topological sorting in directed graphs.
Determines task order considering dependency relationships between nodes.
How It Works
Count in-degree (number of incoming edges) for all nodes.
Put nodes with in-degree 0 into a queue.
Take nodes out of the queue one by one while reducing in-degrees of connected nodes.
Put newly zero in-degree nodes into the queue.
The order in which all nodes are taken out once becomes the topological sorting result.
🔖 5.5. Why Graphs are Important
Graphs are structures that can naturally express complex relationships or flows in the real world.
Various problems like roads between cities, SNS friend relationships, compilation order, task scheduling, etc. can be modeled as graphs.
Graph algorithms are directly applied to solve real problems like shortest paths, minimum cost connections, dependency sorting, etc.
Last updated