| |

VerySource

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

Ask a graph theory algorithm

[Copy link]

1

Threads

3

Posts

4

Credits

Newbie

Rank: 1

Credits
4

 China

Post time: 2020-3-4 19:00:01
| Show all posts |Read mode
In an undirected graph, given two points u and v, and there are no edges between u and v, find the number of simple paths that do not intersect between these two points?
Reply

Use magic Report

0

Threads

2

Posts

3

Credits

Newbie

Rank: 1

Credits
3

 China

Post time: 2020-5-21 00:15:01
| Show all posts
Network streaming
Reply

Use magic Report

0

Threads

9

Posts

6

Credits

Newbie

Rank: 1

Credits
6

 China

Post time: 2020-5-21 12:15:01
| Show all posts
I think it ’s easy to use breadth search
Reply

Use magic Report

1

Threads

3

Posts

4

Credits

Newbie

Rank: 1

Credits
4

 China

 Author| Post time: 2020-5-21 16:30:01
| Show all posts
菜鸟级高手: I have also considered breadth search, but there is no better way to solve the two constraints of "disjoint" and optimization? Can you say something specific?
Reply

Use magic Report

0

Threads

9

Posts

6

Credits

Newbie

Rank: 1

Credits
6

 China

Post time: 2020-5-24 15:30:01
| Show all posts
Each time an element is traversed, a mark is added. It is no longer accessed before the mark is cleared, which can avoid "intersection"
 What do you mean by optimization?
Reply

Use magic Report

1

Threads

3

Posts

4

Credits

Newbie

Rank: 1

Credits
4

 China

 Author| Post time: 2020-5-27 19:30:01
| Show all posts
Optimization refers to that the number of the last disjoint paths is the largest.

If you follow your method, the complexity of the algorithm is very high
Reply

Use magic Report

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

Points Rules

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

Quick Reply To Top Return to the list