Since　the　realization　of　algorithms　is　quite　complex　and　time-consuming,　the　certification　path　construction　of　cross　domain　has　low　efficiency.　To　solve　the　problem,　the　adjacency　matrix　construction　algorithm　is　proposed　based　on　the　graph　theory.　The　algorithm　constructs　two　CAs　certification　path　by　Am　and　F,　F2,　,　Ft.　Compared　with　certification　path　table,　the　best　merit　of　the　new　algorithm　is　that　its　time　complexity　reduces　one　order　of　magnitude,　which　enhances　obviously　the　efficiency　of　certification　path　construction　of　cross　domain.