| |

VerySource

 Forgot password?
 Register
Search
View: 766|Reply: 5

Algorithmic questions about trees

[Copy link]

1

Threads

2

Posts

3.00

Credits

Newbie

Rank: 1

Credits
3.00

 China

Post time: 2020-1-24 14:40:01
| Show all posts |Read mode
Given a tree


(0,1)
(0,7)
(0,12)
(0,13)
(0,15)
(1,2)
(1,4)
(1,6)
(1,7)
(2,3)
(2,5)
(2,6)
(3,4)
(3,5)
(7,8)
(8,9)
(8,10)
(8,11)
(9,10)
(9,11)
(12,13)
(13,14)
(13,15)


0 represents the root node, and each array represents whether there are directed edges between the two nodes. How do I tell if a node is the ancestor of another node? Thank you
Reply

Use magic Report

0

Threads

14

Posts

9.00

Credits

Newbie

Rank: 1

Credits
9.00

 Invalid IP Address

Post time: 2020-2-11 19:45:01
| Show all posts
Consider these questions:
1, How do you represent a single Node in the Graph?
2, How do you represent a single edge in the Graph?
3, How do you build the Graph from your input?

If there is a path from Node A to Node B, then A is a ancestor of B.
Reply

Use magic Report

1

Threads

2

Posts

3.00

Credits

Newbie

Rank: 1

Credits
3.00

 China

 Author| Post time: 2020-2-12 06:15:01
| Show all posts
However, in my algorithm book, in a tree rooted at r, if the vertex v is on a unique path T from vertex w to r, v is the ancestor of w

The key here is the only path I don't know how to deal with, thank you!
Reply

Use magic Report

0

Threads

14

Posts

9.00

Credits

Newbie

Rank: 1

Credits
9.00

 Invalid IP Address

Post time: 2020-2-15 22:30:02
| Show all posts
If it is a tree, the path should be unique. If it is a graph, the path is not necessarily unique.

If each of your nodes knows their dad, then start from w, go to w dad, then w grandpa, ..., until r. If you meet v in the middle, then v is the ancestor of w.
Reply

Use magic Report

0

Threads

3

Posts

4.00

Credits

Newbie

Rank: 1

Credits
4.00

 Asia/Pacific Region

Post time: 2020-3-7 22:00:01
| Show all posts
1. Deep search
2. Minimal transitive closure algorithm
3. Find the shortest path between two points, true if it is not infinite
Reply

Use magic Report

0

Threads

3

Posts

4.00

Credits

Newbie

Rank: 1

Credits
4.00

 China

Post time: 2020-7-17 14:45:01
| Show all posts
// record the input pairs.

boolean isAncestor(int a,int b){
  // judge if a is ancestor of b.
  // travel from b to 0
  // return if a is visted
}
Reply

Use magic Report

You have to log in before you can reply Login | Register

Points Rules

Contact us|Archive|Mobile|CopyRight © 2008-2023|verysource.com ( 京ICP备17048824号-1 )

Quick Reply To Top Return to the list