Messages in a graph structure
Suppose we have a graph, with unknown number of nodes and edges. It is required to implement a simple broadcast algorithm, where
-One node, as the initiator, sends one message to its neighbors.
-Each neighbour, sends the message received to its neighbors, but not the node it initially got it from
- If a node receives two messages, it will only forward the first copy to its neighbors, and ignore the 2nd message.
I am trying to find an exact formula for
Number of messages exchanged = function of number of nodes and edges.
#### Note: I have heard that the no of msg might be equal to (2*Edges) - n + 1. Not sure if this is right, still trying to figure out a way to prove it.... If you think it is right, please let me know how to prove it ....
Could someone help me please?
Re: Messages in a graph structure
A related question which might help me find the answer .... Does anyone know how to compute the exact number of steps required to traverse a tree in BFS or DFS? Is it 2(nodes-1)?