387
个编辑
更改
跳到导航
跳到搜索
第98行：
第98行： − + +
→基于邻接矩阵判断有向图有没有环
<math>B</math>的''k''次方记为<math>B^k=(b_{ij}^k)_{d*d}</math>，其中
<math>B</math>的''k''次方记为<math>B^k=(b_{ij}^k)_{d*d}</math>，其中
:<math>b_{ij}^k=\sum _{h=1}^m a_{ih}^{k-1}a_{hj}</math>
:<math>b_{ij}^k=\sum _{h=1}^m a_{ih}^{k-1}a_{hj}</math>
<math>a_{ih}*a_{hj}\neq 0</math>当且仅当<math>a_{ih}\neq 0</math>和<math>a_{hj}\neq 0</math>，即从节点<math>v_i</math>到<math>v_h</math>和从<math>v_h</math>到<math>v_j</math>都有路径相通，所以<math>b_ij^2</math>
<math>a_{ih}*a_{hj}\neq 0</math>当且仅当<math>a_{ih}\neq 0</math>和<math>a_{hj}\neq 0</math>，即从节点<math>v_i</math>到<math>v_h</math>和从<math>v_h</math>到<math>v_j</math>都有路径相通，所以<math>b_{ij}^2</math>的值表示从<math>v_i</math>出发两步到达<math>v_j</math>的路径数量。同理可知，<math>b_{ij}^k</math>表示从
<math>v_i</math>出发经<math>k</math>步到达<math>v_j</math>的路径数量。<math>b_{ij}^k=0</math>表示不存在这样的路径。
===拓扑排序和识别===
===拓扑排序和识别===