A feasible solution determination method based on an adjacency matrix is proposed for neighborhood structures in job shop scheduling problems. First, the path relationships among operations are analyzed from the perspective of disjunctive graphs, and the limitations of existing determination methods are identified. Based on this analysis, an adjacency-matrix-based method is designed to ensure the accurate determination of neighborhood move feasibility while avoiding the omission of feasible solutions, which substantially broadens the valid search space. In addition, to improve the computational efficiency of the adjacency matrix, a dual-directional pruning method for the adjacency matrix is proposed based on segments of topological sorting, accelerating the feasibility checking process. Finally, the proposed method is compared with other determination methods in terms of the number of feasible neighborhoods, and benchmark instances of various scales are solved using a hybrid algorithm to validate its effectiveness. The results confirm the foundational significance and practical value of the proposed method.