题目内容
(请给出正确答案)
[主观题]
表示图的另一种方法是使用关联矩阵INC[n][e].其中,一行对应于一个顶点,一列对应于一条边,n是
图中顶点数,c是边数。因此,如果边j依附于顶点i,则INC[i][j]=1。图8-16(b)就是图8-16(a)所示图的关联矩阵。注意,在使用关联矩阵时应把图8-16(a)中所有的边从上到下、从左到右顺序编号。
(1)如果ADJ是图G=(V,E)的邻接矩阵,INC是关联矩阵,试说明在什么条件下将有ADJ=lNC×INCT-I,其中,INC是矩阵INC的转置矩阵,I是单位矩阵。两个nxn的矩阵的乘积C=A×B定义为公式中的“∪”定义为按位加,“∩”定义为按位乘。
(2)设用邻接矩阵表示的图的定义如下。
试仿照上述定义,建立用关联矩阵表示的图的结构。
(3)以关联矩阵为存储结构,实现图的DFS的递归算法。
提问人:网友13***002
发布时间:2022-01-07