Should I iterate over a directed graph using Iterative deepening depth-first search (IDDFS)?

Example: I have 20 persons as object, and every person knows 0-n others. The direction of the link matters! A person A might know B, but B might not know A. It's a directed graph.

Edit: For simplification, my node objects (in this case Person objects) are able to store arbitrary information. I know this is not the best design but for now that would be fine.

So in the worst case everyone is connected with everyone else, everyone knows everyone else. This is no real use case but I want to write a test for this to learn and play around. In a productive environment the number of objects would be limited to about 20, but the ways in which those objects are connected to eachother are unlimited.

This illustrates the problem in a simplified way:

thanks to source

Given a specific person as starting point, I want to walk through the whole graph and examine every possible path exactly once without getting stuck in an infinite loop.

Let's imagine person A knows B, who knows C, and who knows A. The output might be:

A knows B knows C knows A (ok but we don't want to end in an infinite loop so we stop here) A knows C knows A A knows T knows R knows V

This would be stupid and mu开发者_如何学运维st be eliminated: A knows B knows C knows A knows C knows A knows T knows R knows V ...

I do have a couple of crazy ideas how to tackle this problem. But...

Question) Must I do that with an Iterative deepening depth-first search (IDDFS)?

---

Jon was so kind to point out DFS on Wikipedia

I'm stuck with this part in the article:

a depth-first search starting at A, assuming that the left edges in the shown graph are chosen before right edges, and assuming the search remembers previously-visited nodes and will not repeat them (since this is a small graph), will visit the nodes in the following order: A, B, D, F, E, C, G. The edges traversed in this search form a Trémaux tree, a structure with important applications in graph theory.

specifically this note:

"(since this is a small graph)"

OK so what if this is a huge graph?

---

Edit: I should mention the authors title and question has changed so much, some of the information in this answer may not be 100% relevant.

As Jon has already mentioned, this is indeed, a graph. A directed graph in fact.

I suggest you look at Adjacency matrices, they will provide you with direct insight as to how you can reach a solution. I imagine your original lazy solution was probably something akin to an Adjacency list; which is fine, but isn't as easy to implement, and also may be harder to traverse. There is two main differences between the two.

Adjacency lists will take up more space, but may be nicer in larger networks in minimizing computation over unconnected nodes; whereas adjacency matrices are are little more friendly, but store data for every edge, regardless of whether it exists (connected) or not.

The primary concern I found when using adjacency lists, was not their theoretical space, but in C++, I was storing each connected node as a pointer in a vector inside each node; this could get way out of hand as soon as the network got bigger, and was very unfriendly to visualize as well as managing new nodes and deleting nodes. In comparison with adjacency matrices, which have a single reference for all nodes (can be stored in a single vector of nodes) and can be easily modified.

---

If your question is truly about traversal, then if your graph is implemented as an adjacency matrix, as a vector of vectors, traversal is simple. See below pseudocode:

To read (for each neuron) all neurons a neuron's axon is connected to (ie neuron outputs)

for (size_t i = 0; i < n; ++i) { // adjacency matrix is n * n
    Neuron& neuron = nodes[i];
    for (size_t j = 0; i < n; ++i) {
        Axon_connection& connection = edges[j][i];
        if (connection.exists()) {
            ...
        }
    }
}

To read all (for each neuron) neurons a neuron's dendrites are connected to (ie neuron inputs)

for (size_t i = 0; i < n; ++i) { // adjacency matrix is n * n
    Neuron& neuron = nodes[i];
    for (size_t j = 0; i < n; ++i) {
        Dendrite& dendrite = edges[j][i];
        if (dendrite.exists()) {
            ...
        }
    }
}

Note this second method may not be cache friendly for big networks, depending on your implementation. The exists method simply ensures the adjacency matrix bit is set to true, you can then implement other data such as strengths in these edges.

---

My friend, you have posted many very similar questions over the last day or two. I suggest you take a little bit of time out and read an introductory textbook on graph theory, or find some lectures on the subject.

Then you will at least know how to recognize and classify the standard problems. All you are going to get on SO are links back to such resources - it's not worth anyone's time writing out a fresh exposition. When you have a specific question, or are stuck understanding a particular issue, then ask and we will be happy to help, but you need to meet us half-way.

To answer your question, you can perform depth first search and breadth first search on an arbitrary graph as you have previously done on a tree - you just need to keep track of which nodes you have visited. Look out for this in any code/pseudocode you encounter. You don't have to keep track of visited notes on a tree (as in your other questions), as a tree is a special instance of a graph (a connected acyclic graph) which cannot be "wildly interconnected".

---

In answer to your original question, it is definitely theoretically possible to solve. However if you are after the shortest path then this looks suspiciously like the travelling salesman problem which is NP-hard.

In any case, there are many different graph traversal algorithms (DFS, IDDFS, BFS, etc) which could be of use.

---

Your data structure is indeed a graph.

I hate to provide such a bare answer, but the question is so basic that Graph Traversal on Wikipedia is more than adequate. The two basic approaches are explained and there is also pseudocode.

---

One way (and not, necessarily, the best way) to do this is to modify the graph.

For example, say that the graph initially encodes A-->B-->C. If the edge A-->C does not exist, add the edge A-->C.

You can do this for each node in your graph to explicitly state which nodes know each other.