The invention discloses a contact graph routing algorithm based on random linear network coding in deep space communication. The contact graph routing algorithm comprises the following steps: a sourcenode processes a data packet to be sent by adopting random linear network coding; the source node selects a plurality of link disjoint paths according to the predicted contact graph and transmits theencoded packets on the plurality of paths. the received data packet is directly forwarded at the intermediate node and re-encoded before forwarding; the destination node receives the data packets anddecodes them, and feeds back the packets which cannot be decoded successfully to the last hop node set, the last hop node set sends the encoded packets which are helpful to the destination node decoding, so that the destination node can decode the packets quickly and reduce the transmission delay. The invention adopts random linear network coding to send the original data, and controls the redundant data packets in the network through the link state to ensure that the destination node can be decoded while reducing the waste of network resources and reducing the decoding waiting time delay ofthe node.