Graph Basics: Your Friend Network in Code! 🌐

Welcome to the world of graphs! If you’ve ever looked at a map of roads connecting cities, or thought about how your friends are connected to each other on social media, then you’ve already been thinking about graphs! In this lesson, we’ll learn the fundamental concepts of graphs and how to represent these connections in code using Go.

What is a Graph? 🤝

Imagine you’re planning a big party and you want to invite all your friends. But your friends also have friends, and those friends have friends too! A graph is like a big web of connections between people (or things).

Real Life Example: Think of Facebook or Instagram. Each person is a “node” (or vertex), and each friendship is a “connection” (or edge). You’re connected to your best friend, who is connected to their coworkers, who are connected to their family, and so on!

// A simple graph showing friendships
// You (0) --friend-- Alice (1) --friend-- Bob (2)
//   |                           |
//   --friend-- Charlie (3) --friend--

Graph Terminology 📚

Node/Vertex: A person, place, or thing in your graph
Edge: A connection between two nodes
Degree: How many connections a node has
Path: A sequence of nodes connected by edges
Cycle: A path that starts and ends at the same node

Building Your First Graph 🏗️

Let’s start by creating a graph to represent friendships. We’ll use a simple approach where each person has a number, and we keep track of who is friends with whom.

package main

import "fmt"

// Our first graph - just a list of friends for each person
type FriendGraph struct {
    people    int           // How many people in our network
    friendships [][]int     // For each person, list of their friends
}

func NewFriendGraph(numPeople int) *FriendGraph {
    return &FriendGraph{
        people:       numPeople,
        friendships:  make([][]int, numPeople), // Create empty friend lists
    }
}

func (fg *FriendGraph) AddFriendship(person1, person2 int) {
    // Add person2 as friend of person1
    fg.friendships[person1] = append(fg.friendships[person1], person2)
    // Add person1 as friend of person2 (friendship works both ways!)
    fg.friendships[person2] = append(fg.friendships[person2], person1)
}

func (fg *FriendGraph) GetFriends(person int) []int {
    return fg.friendships[person]
}

func (fg *FriendGraph) GetDegree(person int) int {
    return len(fg.friendships[person])
}

func main() {
    // Create a graph with 4 people (0, 1, 2, 3)
    socialNetwork := NewFriendGraph(4)

    // Add friendships
    socialNetwork.AddFriendship(0, 1) // You and Alice are friends
    socialNetwork.AddFriendship(1, 2) // Alice and Bob are friends
    socialNetwork.AddFriendship(0, 3) // You and Charlie are friends
    socialNetwork.AddFriendship(3, 2) // Charlie and Bob are friends

    // Check your friends
    yourFriends := socialNetwork.GetFriends(0)
    fmt.Println("Your friends:", yourFriends) // [1, 3] - Alice and Charlie

    // Check Alice's friends
    aliceFriends := socialNetwork.GetFriends(1)
    fmt.Println("Alice's friends:", aliceFriends) // [0, 2] - You and Bob

    // Check degrees (number of friends)
    fmt.Println("Your degree:", socialNetwork.GetDegree(0)) // 2
    fmt.Println("Alice's degree:", socialNetwork.GetDegree(1)) // 2
}

What just happened?

We created a FriendGraph that keeps track of friendships
Each person gets a number (0, 1, 2, 3)
friendships[person] is a list of all that person’s friends
When we add a friendship, it goes both ways (because friendship is mutual!)
We can check how many friends each person has (their degree)

Types of Graphs 📊

Undirected Graphs (Like Facebook Friendships)

Connections work both ways - if you’re friends with someone, they’re friends with you.

Directed Graphs (Like Twitter Follows)

Connections can be one-way - you can follow someone who doesn’t follow you back.

// Directed graph example - following on social media
type FollowGraph struct {
    people   int
    following [][]int // Who each person follows
}

func (fg *FollowGraph) Follow(follower, followed int) {
    fg.following[follower] = append(fg.following[follower], followed)
    // Note: We don't automatically add the reverse!
}

func (fg *FollowGraph) GetFollowing(person int) []int {
    return fg.following[person]
}

Weighted Graphs (Like Flight Costs)

Connections have values - like how much it costs to fly between cities.

// Weighted graph example - flight costs
type FlightGraph struct {
    cities int
    flights map[string]int // "NYC-LAX" -> 500 (cost in dollars)
}

func (fg *FlightGraph) AddFlight(from, to string, cost int) {
    key := from + "-" + to
    fg.flights[key] = cost
}

func (fg *FlightGraph) GetCost(from, to string) int {
    key := from + "-" + to
    return fg.flights[key]
}

Graph Properties 🔍

Connected vs Disconnected

Connected Graph: You can reach any node from any other node
Disconnected Graph: Some nodes are isolated from others

Cyclic vs Acyclic

Cyclic Graph: Contains cycles (loops)
Acyclic Graph: No cycles (like a tree)

Real-World Graph Examples 🌍

Social Networks: People connected by friendships
Maps: Cities connected by roads
Internet: Web pages connected by links
Course Prerequisites: Courses connected by requirements
Family Trees: People connected by relationships
Computer Networks: Computers connected by cables

Practice Problems 🎯

Friend Degrees: In a social network, find the person with the most friends
Connection Check: Check if two people are connected through friends
Graph Size: Count how many people and friendships are in your network
Isolated People: Find people who have no friends

What’s Next? 🚀

Now that you understand the basics of graphs, in the next lesson we’ll explore different ways to store and represent graphs in memory. We’ll look at adjacency matrices, adjacency lists, and when to use each approach!

Graphs are powerful tools for modeling connections in the real world. Keep practicing with these basic concepts, and you’ll be ready to tackle more complex graph algorithms! 🌟

Popular Topics

Categories