Outline an algorithm in pseudocode which takes a weighted, directed graph (that

Question

Outline an algorithm in pseudocode which takes a weighted, directed graph (that represents debt between people) as input and outputs the amount of money a person needs to pay as well as to whom this person is in debt to. Specify the data structures you use in this algorithm and state and explain the total runtime complexity of the algorithm in terms of the amount of nodes (people) in the graph. For the sake of the problem, assume that each person has a constant (O(1)) number of debts such that the number of edges (debts) in the graph is O(n).

Explanation / Answer

Here the data structure we use to represent the directed graph is adjacency list, Where For each vertex, a list of adjacent vertices is maintained using a
linked list. It creates a separate linked list for each vertex Vi in
the graph G = (V, E). Therefor each person is depicted as a vertex and the node in the attached linked list to that vertex represents as the dept a person has to received from the other peoples.

The selection of this data structure is based on the point given in question that the constant number of edges are there for each vertex so this would be momory efficient.

The number of people to find the total dept a person will receive is same as the in degree of the of a node and given by length of the corresponding linked list.

To represent a node here

typedef struct node
{
struct node *next;
int vertex;
int weight;
}node;

Algorithm to get the total debt a person has to receive and from whom:

Ajacency list node represent as:
struct AdjListNode
{
int debt; // amount of debt received by the person
struct AdjListNode* node;
}

Adjacency List can be represent as:
struct AdjList{
struct AdjListNode *head; //pointer to the head member of list
}

So Graph would be an array of adjacency lists.
struct Graph
{
int V; // number of vertex (People)
struct AdjList* array;
}

So to get the total received debt for a person we need to perform following two activity.

1) While crearting the graph if we sum the amount of debt a person has to give while adjacency list node to an index of adjacency list array
the array node will be having a total amount after creatin of graph which will show the amount of debt this person is going to receive. This can be get in O(1) constant time.

2) And to get the By whom list, we have to traverse to adjacency list of the respecive person(vertex) and get the list node as the persons list by whom debt has to come. This can be done in MAX O(n) where n is number of verices.

Total Complexity: O(n) (By excluding creation of the graph)

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.