Еще вариант — таблица с полями id1, id2, status. id1 — тот, кто предлагает дружбу, id2 — кому предлагают, status — состояние связи. Частично проигрывает вариантам, перечисленным выше, но жизнь у такого тоже есть. Например, если Вам нужно больше типов связей — кроме друга еще, например, родители и т.д.