387
个编辑
更改
跳到导航
跳到搜索
第93行：
第93行： − ：<math>b_{ij}=\mid e_k \mid,e_k=(v_i,v_j)\in E</math>+ − ：<math>a_{ij}^k=\sum _{}</math>+
→基于邻接矩阵判断有向图有没有环
===基于邻接矩阵判断有向图有没有环===
===基于邻接矩阵判断有向图有没有环===
对于有向图<math>G=（V，E）</math>，构造<math>d=\mid V \mid</math>阶方阵<math>B=（b_{ij}）_{d*d}</math>，其中
对于有向图<math>G=（V，E）</math>，构造<math>d=\mid V \mid</math>阶方阵<math>B=（b_{ij}）_{d*d}</math>，其中
:<math>b_{ij}=\mid e_k \mid,e_k=(v_i,v_j)\in E</math>
称矩阵<math>B</math>为有向图<math>G</math>的节点邻接矩阵。
称矩阵<math>B</math>为有向图<math>G</math>的节点邻接矩阵。
<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 _{}</math>
===拓扑排序和识别===
===拓扑排序和识别===