1
$\begingroup$

Imagine i have a graph called G.

G has some parts. In one part, every node describes a person. I have another part in G which contains interests as nodes. ( Imagine that person A likes music. So, there is an edge between A and M )

I have some other parts in my graph like cities. What i want is not a simple DFS or something like Dijkstra's shortest path algorithm. I want to implement an special kind of search.

For example, i want to know, how two persons are connected to each other. Imagine A likes Music. B likes Football. A & B are in the same school. So, if A wants to learn how to play Football, he should go to school, then he see B and after that, he can learn playing Football from B.
Another Example, Maybe i want to search in the graph without an specific node. I mean maybe somehow i don't want a node in my shortest path.

Note : My question is somehow general but i want to know if there exists some kind of algorithm or a way to implement these searches in a good order.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

If your graph is bipartite, such that persons are only connected to places/things you can simply use BFS to find the closest person who likes football by first going at least 2 steps to find all indirectly connected persons and then continuing from there to hopefully find football in the third step (or another uneven number of steps). \

If there is a specific node you do not want to use you can depending on the implementation just remove it beforhand or check everytime you get to a node whether it is specaial and ignore it. If your algorithm is recursive and using classes you can set a flag in the specific vertex such that the method returns "I do not exist" for this vertex.

It is usally best to adapt existing algorithms to fit your problem instead of inventing new ones. Other programmers understand them better and they are usally very flexible and easy to implement.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.