Abstract. The paper considers the problem of exploration of finite undirected graphs by a collective of agents. Two agents-researchers simultaneously move on the graph, read and change marks of graph elements, transfer necessary information to the agent-experimenter (it constructs the representation of the explored graph). An algorithm is proposed for a linear (with respect to the number of nodes) time complexity and quadratic space complexity. An optimization procedure is developed for graph partition for exploring by different agents. Two agents (that move on the graph) need two different colors (three colors in total) for graph exploration. The algorithm is based on depth-first traversal method.

Keywords: exploration of graphs, collective of agents, graph traversal.