狀態圖是一個帶有標籤的有向圖，幷包含狀態資訊，可用於指示系統中某些路徑只能以特定方式遍歷。狀態圖也稱為問題空間模型（Atallah 1998, p. 36-2）。例如，在上面的左圖中（由 R. 阿伯特創作），一輛汽車必須在遵守所有交通規則且不掉頭的情況下穿過城鎮。最初，汽車位於位置 4，向東行駛，並且可以選擇移動到位置 1，向東行駛，或位置 5，向東行駛。迷宮對應的狀態圖在上面的右圖中示出。
上面展示了由 R. 阿伯特建立的另一個例子。雖然這個迷宮與第一個非常相似，但狀態圖卻不同。因此，這個迷宮說明了系統規則的微小變化會對狀態圖產生重大影響。
個節點的的狀態圖表示。