CODEWITHSUNDEEP
algorithmgraph-theory
user195872
user195872

Reputation: 1

Algorithm of bidirectional graph

I've got a graph (or unrooted tree) of N nodes and N-1 connections. Each connection has a distance of 1.

How can i find a node v that has the maximum distance between v and a set of nodes E{}, when v can be a node in E?

Constraints:

Upvotes: 0

Views: 553

Answers (3)

ronalchn
ronalchn

Reputation: 12335

Here is a simple algorithm to compute the distance of every node from each vertex of E.

The graph is a tree, and initially un-rooted.

  1. Arbitrarily pick a node as the root

  2. Traverse the tree, and compute for each node, the number of vertices in its subtree that are in E (we can call this function e(node)).

    • For example, if your tree is as follows (where the brackets show the vertices in E={C,D,I}), you will compute the numbers as shown:

      vertices in the graph:              e(v)

          A                          3
         / \                        / \
        B  (C)                     1   2
       / \   \                    / \   \
     (D)  F   G                  1   0   1
     /         \                /         \
    H          (I)             0           1
  3. Also calculate the distance of the root node from the set E (call this function d(v)). We see d(A)=6, and is easily calculated while traversing the tree in step 2.

  4. Then, traverse the tree again, to compute the distance function of each node, where the formula is d(v) = d(parent(v)) + size(E) - 2*e(v). This will take O(n) time for all nodes, because it is constant time for each node.

    The formula is derived by considering that when you move from a parent to a child, the distance from the set of nodes in E changes by:

    • an increase in distance by 1 for each nodes in E not in the subtree of the child
    • a decrease in distance by 1 for each node in E which is also in the subtree of the child

    Examples:

    • d(B) = d(A) + size(E) - 2*e(B) = 6 + 3 - 2 = 7,
    • d(D) = d(B) + size(E) - 2*e(D) = 7 + 3 - 2 = 8,
    • d(H) = d(D) + size(E) - 2*e(H) = 8 + 3 - 0 = 11,
    • d(F) = d(B) + size(E) - 2*e(F) = 7 + 3 - 0 = 10
  5. Then just search the node v which has the highest d(v), you can do this by traversing the tree again. You can also do this at the same time that you traverse the tree in the step 4.

This algorithm requires only 2 distinct traversals of the tree, each taking O(n) time. Thus, the overall algorithmic complexity is O(n).

Note that the reason this algorithm can be so efficient is that the graph is a tree. Most shortest path algorithms are for general graphs. A tree is much simpler in that there is only one unique path between any pair of vertices. Thus, there is no need for the tactics generally required in shortest path algorithms.

Upvotes: 0

Keith Randall
Keith Randall

Reputation: 23265

I would use breadth first search starting with the node set E. v will then be the last node you visit.

Edit:

1-2-3-4    E={1,4,5}
    |
    5

Ok, now I understand your metric. You want to compute, for each edge, the total sum of distances from that edge to the elements of E on either side of that edge. You can do that by computing the values up from the leaves to the root (handwaving a bit).

Then you can compute for each node the sum of those values on each incoming edge. Pick the node with the biggest sum.

Upvotes: 1

igillis
igillis

Reputation: 141

If the graph is acyclic you can make the edge weights -1 and run Floyd-Warshall. This will give you all-pairs longest path. Then for each node in the graph take the average distance to the nodes in E.

Otherwise I believe looking at an NP-Complete problem of trying to find the longest path in an arbitrary graph.

Upvotes: 0

Related Questions