The majority researches of directional broadcasting in wireless networks put effort to optimize packet delivery ratio and reduce transmission redundancy through relay selection and forwarding probability deduction. However, relay selection and beam pointing calculation were not considered jointly, which may cause inferior beam pointing scheme and increase message relay times. To improve the efficiency of directional broadcasting, a maximum complete subgraph and minimum arborescence based directional broadcasting algorithm (MCSMA) was proposed. The maximum complete subgraph theory was used to calculate the beam direction of the source or relay node to cover the maximum number of neighbor nodes. The minimum arborescence theory was used to select relays to cover all nodes with fewer beams, which can decrease the message relay times. Simulation shows the proposed algorithm can effectively reduce the required beams of the source node and all relays during the broadcasting process, and improve the efficiency of directional broadcasting.