Minimum Spanning Tree (MST) and Breadth-First Search (BFS) tree constructions are classical problems in distributed computing, typically studied in the message-passing model, where static nodes communicate via messages. This paper examines these problems in an agent-based network, where computational devices are modelled as mobile agents that explore a graph and perform computations. Each node serves as a container for agents, and communication occurs when agents meet at the same node. We consider the setting where n agents are dispersed (one per node) on an anonymous, arbitrary n-node, m-edge graph G. The goal is to construct tree structures such that each tree edge is recognized by at least one of its endpoint agents, minimizing both time and memory. We work in the synchronous model, measuring time in rounds, and assume agents have no prior knowledge of graph parameters such as \(n, m, D, \varDelta \) . A known solution constructs a BFS tree in \(O(D\varDelta )\) rounds with \(O(\log n)\) memory per agent, assuming the root is known. We present a deterministic algorithm that constructs a BFS tree in \(O(\min (D\varDelta , m\log n)+n\log n+\varDelta \log ^2 n)\) rounds with \(O(\log n)\) bits per agent, without any prior root knowledge. In discovering the root, we solve leader election and MST. Our leader election and MST algorithms run in \(O(n\log n+\varDelta \log ^2 n)\) rounds using \(O(\log n)\) memory. Previous results require O(m) rounds and \(O(\log ^2 n)\) memory for leader election, and \(O(m+n\log n)\) rounds and \(O(\max (\varDelta , \log n)\log n)\) memory for MST. Our results improve over this prior work. We assume each agent knows \(\lambda \) , the maximum identifier, bounded by a polynomial in n (i.e., \(\lambda \le n^c\) for some constant \(c \ge 1\) ).