第二十六天(拓扑)

今天完成题目:207,210 207:课程表

• 我的思路:

  • 深度遍历

  • 先建立邻接表(被指向点所含有的所有相邻的指向点)

  • 建立栈或队列(当没有邻接表时候,入栈或入队)

  • 当栈不为空的时候,删除栈顶元素,删除邻接表中与栈顶元素对应的点.

  • 当且仅当所有邻接表都被删除,返回True

• 别人的思路:

  • 广度遍历

  • 建立邻接表和入度表,使用队列保存可以删除的结点

  • 当入度为0时候,加入队列

  • 每次取队首元素,对应的在邻接表中的元素,含有队首元素的入度减1(相当于删除一个前向结点)

    • 当入度小于0时候,表示这个这个元素已经不在

    • 当入度等于0时候,该元素加入队列

  • 每次出队,结点数-1,当剩余结点数为0,说明可以拓扑

210:课程表 二

• 广度遍历

• 建立邻接表和入度表,使用队列保存可以删除的结点

• 当入度为0时候,加入队列

• 每次取队首元素,对应的在邻接表中的元素,含有队首元素的入度减1(相当于删除一个前向结点),记录取出的队首元素为结果

  • 当入度小于0时候,表示这个这个元素已经不在

  • 当入度等于0时候,该元素加入队列

• 每次出队,结点数-1

  • 当剩余结点数为0,说明可以拓扑,返回结果

  • 否则返回[]