用邻接矩阵存储一个有向图，写一算法计算出度为0的顶点个数。

假定图G=(V，E)是有向图，V={1，2，…，N}，N≥1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A是一个二维数组，如果i到j有边，则A[i，j]=1，否则A[i，j]=0，请给出一个算法思想，该算法能判断G是否是非循环图(即G中是否存在回路)，要求算法的时间复杂性为O(n×n)。

后写出对G进行宽度优先搜索的算法。

想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为O的邻接到的顶点进行递归。 (1)给出完成上述功能的图的邻接表定义。 (2)定义在算法中使用的全局辅助数组。 (3)写出在遍历图的同时进行拓扑排序的算法。

历图的同时进行拓扑排序的算法。

图

实验目的：

(1)掌握图的两种存储结构的实现方法。

(2)掌握遍历图的递归和非递归算法。

(3)掌握和理解本实验中出现的一些基本的C语言语句。

(4)体会算法在程序设计中的重要性。

实验内容：

(1)设计算法，构造无向图的邻接链表，并递归地实现基于邻接链表的图的深度优先搜索遍历。

(2)设计算法，构造无向图的邻接矩阵，并递归地实现基于邻接矩阵的图的深度优先搜索遍历。

度的方法是________。

图中顶点数，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的递归算法。