When you first try to build a graph in Rust, you're going to hit a wall. It’s almost a rite of passage. You'll likely start with something that feels intuitive—a Node struct that holds a list of other Nodes—and then the compiler will start screaming at you about ownership and recursive types.

Let's look at a piece of code I see learners write all the time. They realize they need multiple things to "own" a node (because in a graph, many nodes can point to one), so they reach for Rc. But then they realize they actually need to change the graph after it's created.

use std::rc::Rc;

struct Node {
    value: String,
    edges: Vec<Rc<Node>>,
}

fn main() {
    let a = Rc::new(Node { value: "A".into(), edges: vec![] });
    let b = Rc::new(Node { value: "B".into(), edges: vec![] });

    // I want to connect A to B
    a.edges.push(Rc::clone(&b)); // ERROR: cannot borrow `a` as mutable
}

The "Immutable Rc" Wall

If you try to compile that, Rust will stop you cold. Why? Because Rc<T> provides shared ownership, but it only provides immutable access to the data it wraps. Since multiple Rc pointers can point to the same Node, Rust cannot possibly know who "owns" the node enough to safely let them mutate it. If a could mutate the edges vector, it might invalidate pointers being held by other parts of the program.

You might be tempted to use mut a, but that only makes the pointer mutable, not the data inside the Rc. We need a way to cheat the system—legally.

Breaking Through with Interior Mutability

To fix this, we need to wrap the Node inside a RefCell. This is the "Interior Mutability" pattern. By using Rc<RefCell<Node>>, we move the borrow checking from compile-time to runtime. Instead of the compiler proving the code is safe, the RefCell will check at runtime if there are any active borrows and panic if you try to violate the rules (like having two mutable references at once).

Here is how we actually implement this. Notice how we have to call .borrow_mut() to get to the inner Node:

use std::rc::Rc;
use std::cell::RefCell;

struct Node {
    value: String,
    edges: Vec<Rc<RefCell<Node>>>,
}

fn main() {
    let a = Rc::new(RefCell::new(Node { 
        value: "A".into(), 
        edges: vec![] 
    }));
    
    let b = Rc::new(RefCell::new(Node { 
        value: "B".into(), 
        edges: vec![] 
    }));

    // We borrow the interior of 'a' mutably to push 'b' into its edges
    a.borrow_mut().edges.push(Rc::clone(&b));
    
    // Now 'a' points to 'b'. We can do the same for 'b' to 'a' if we want a cyclic graph.
    b.borrow_mut().edges.push(Rc::clone(&a));
    
    println!("Graph connected successfully!");
}

I'll give you a heads-up: this pattern is powerful, but it comes with a cost. Because we're using Rc, we've introduced the possibility of reference cycles. In the example above, a points to b and b points to a. Their reference counts will never hit zero, meaning they'll stay in memory forever (a memory leak). In a real production system, you'd use Weak<T> to break those cycles, but for most graph exercises, Rc<RefCell<T>> is the essential foundation you need to master first.

📋 Practical Task

Exercise: Building a Social Connection Graph

Your task is to implement a basic social network graph where "Users" can be friends with each other. Because friendship is mutual, each user should hold a reference to their friends.

Requirements:

• Create a User struct that contains a name: String and a friends: Vec<Rc<RefCell<User>>>.
• Implement a function add_friend(user1: &Rc<RefCell<User>>, user2: &Rc<RefCell<User>>). This function must add user2 to user1's friends list AND add user1 to user2's friends list.
• In main:
  1. Create three users: "Alice", "Bob", and "Charlie".
  2. Make Alice and Bob friends.
  3. Make Bob and Charlie friends.
  4. Print out Alice's friends' names to verify the connection.

Hint: Remember that you cannot access the friends vector directly through the Rc; you must use .borrow_mut() to modify the list.