How can I model a problem as an MDP if the agent does not follow the successive order of states?
Your problem fundamentally is that you are confusing what the state and actions are in this setting. Webpages are not your states; your state is the entire priority queue of (website-outlink) pairs + the (new_website-outlink) pairs. Your action is which pair you select.
Now this is a variable sized state-space and variable sized action-space problem setting at the same time. To deal with this lets start by noting that state==observation need not be (in general). So what is your observation? Your observation is a variable-sized batch of either:

(website-outlink) pairs or
next_website (where each next_website is determined by its corresponding pair)

Both of these observations could work just fine, choosing between one or the other is just a matter of whether you want your agent to learn &quot;which links to open before opening them&quot; or &quot;which links are meaningful (after opening them)&quot;.
What your priority queue is essentially doing is just adding a neat trick that:

Saves the computational complexity of keeping the state ordered (remember that your state is not a website, but the list/batch of website-outlink)
Avoids needlessly recomputing the Q-values for each of your actions (remember that an action is not selecting an outlink from new_website, but selecting an outlink from all available choices in the queue)

Note however that to actually have the second saving it is crucial to store the Q-values for each pair!!!
Last important thing to note is that in a scenario where you use a Replay Buffer (which I guess is likely given that you chose a DQN), you can't use the priority queue whilst learning from the RB. To see why (and to see in detail how your learning process actually looks like), start by remembering that your Q-value updates are given by the formula here; your state s_t is a (quasi-ordered1) batch of pairs. Q(s_t, a_t) is just the output of running your DQN regression on just the best website/pair in this batch (you have to add an index to denote the best choice when adding transitions to the RB, in order to be consistent about which action was taken from this state). To compute the estimate of the optimal future value however you will have to recompute the Q-value of every single website/pair in the next state. You CANNOT use the priority queue when training from the RB.
1 You have the priority queue ordered for all websites you had in it whilst looking at the last website, but all the new_website-outlink pairs you are now adding are not ordered yet. You still have to run the agent on them and then you can order them with the rest of the priority queue to generate the next state (which still will not be ordered because you will have new_new_website-outink pairs).