0
$\begingroup$

Below is a question based on CLRS, about using an algorithm to reach a balance between a group of friends. I figured the best way to do this, is through the use of a DFS algorithm. Below the question is some psuedocode I wrote using the formal algorithm of a DFS search. My question is, how do I get the algorithm to balance out the debt between every student?

The input for your algorithm consists of two lists $owing$ and $friendship$. The length of the list $owing$ is the total number of students; $owing[i]$ is the amount that student $i$ is owing $(0 \leq i \leq len(owing)-1)$, and it is an integer than can be positive (owing money), negative (owed money) or zero. The list $friendship$ is a list of pairs that represent the remaining friendships, i.e., a pair $(i, j)$ means student $i$ and student $j$ are still friends and can still talk and give money to each other. Devise an efficient algorithm which, given the two input lists, returns whether or not it is possible for everyone to get even.

The algorithm uses three colors (white/grey/black) to measure not visited/visited/cleared. What I want to happen is, it goes through a single cluster of friends, then checks to see if the balance of that friends group is equal to 0 (everyone can pay each other back). If not, returns failure. The issue is, let's say it does pass through that circle of friends- what if needs to go to another friends group? How will it balance out when that friends group might have a different adjacency list. Any advice on how to make sure everyone can pay each other and return 0?

Owing = false
Owed = false
pathTotal = 0

DFS(owing, friendship):
    for student in owing:
        student.color = white
        student.pred = null
        student.area = null

    for student in friendship:
        if student.color == white:
            DFS_VISIT(student, owing, friendship)

DFS_VISIT(student, owing, friendship)
    // Get all students current student is friends with
    for x in friendship:
        if x pair student:
            student.adj = student.adj + x

    // Check if adjacent members have not been visited
    for i in student.adj:
        if i.color != white:
            if owing[i] > 0:
                Owing = true
            else if owing[i] < 0:
                Owed = true

    // If it hasn't been visited 
    if student.color == white:
        Owing = false
        Owed = false

        if student.pred == null:
            if owing[student] != 0:
                return "Failure"

        else:
            pathTotal = pathTotal + owing[student]

        // Calculated debt
        student.color = grey

    // Recursively go through the rest of the list
    for t in student.adj:
        if t.colot == white:
            t.pred = student
            DFS_VISIT(t, owing, friendship)

    // All neighbors visited
    student.color = black;
$\endgroup$
  • $\begingroup$ Where did that algorithm/pseudocode come from? Where did you get that algorithm from? Can you edit the question to credit the source? Was it something you designed yourself? If so, I'm puzzled about the fact that you designed an algorithm yourself, and now you're asking how it works and what it will do in a certain situation (if you designed it; wouldn't you know better than anyone?). Anyway, if you're not sure what it does in some particular situation, pick some small examples and run it by hand on those small examples and see what happens. $\endgroup$ – D.W. Mar 26 '17 at 22:35
  • $\begingroup$ cs.stackexchange.com/q/71911/755 $\endgroup$ – D.W. Mar 26 '17 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.