本章主要讲解了图的两种表示方法：邻接链表和邻接矩阵。
课后题：
1.给定有向图的邻接链表，多少时间才能算出每个结点的出度和入度？
计算出度：
①为了计算一个结点的出度，我们需要枚举v结点所有的边，O(出度(v))。
②然后遍历每个结点计算出度，耗费时间为O（|E| + |V|），这里的|V|是必须有的（假设一个图没有边，还是要把所有的点遍历1遍）。
③如果在邻接链表中加入每个结点的边的个数，可以减少到O(|V|)。
计算入度：
计算入度只能遍历整个邻接链表，因此时间复杂度为O(|V)+|E|)。
2.给定一个七个结点的完全二叉树的邻接链表，请写出等价的邻接矩阵表示，这里假设结点的编号为从1~7。
邻接链表：
1 →2→3
2→4→5
3→6→7
4→2
5→2
6→3
7→3
邻接矩阵
（0 1 1 0 0 0 0
1 0 0 1 1 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 1 0 0 0 0
）
3. 要求对于邻接矩阵和邻接链表给出从G到的算法，并计算其复杂度。
对于邻接矩阵问题十分简单，直接求矩阵的转置即可，意味着把行换成列，把列换成行，对每行操作为O(|V|)，需要对|V|行操作，时间复杂度为O（|V|^2）。
对于邻接链表，很明显要遍历链表的所有结点来看：如果对于u结点其指向的结点中有v,则在新的链表中，创建一条从v的链表指向u的路径，因此需要遍历所有的链表元素，因此时间复杂度为O（|V|+|E|）。
3. 给出一个多图（多图为包含重复边和自循环边的图）去除冗余边的复杂度为O(V+E)的算法。
遍历邻接链表的所有结点，对于结点u，如果其链表中还有u，则去除所有的u；如果还有重复的v，则去除除了第一个v以外的v结点（这里的标记方法有很多种，可以用个数组）。这样的复杂度应该在O(V+E)。
4. 求解平方图的问题
算法如下：遍历G的邻接矩阵，对于结点u，如果存在u到v的路径，则在G^2的邻接矩阵u中加入v,然后再遍历v结点的链表，如果存在v到w，则将w也加入到G^2的邻接矩阵u中。
时间复杂度：这样，再遍历u的时候，如果遍历到了u→v这条边，那就在看v的链表，而v的链表里最多有|V|个结点，因此总的复杂度为O（|V|+|V|·|E|）。
6. 邻接矩阵求通用汇点（入度为|V|-1但是出度为0）的算法
算法如下：从（1，1）开始扫描邻接矩阵，如果（i,j）是0，则下一个扫描（i,j+1）;如果（i，j）是1，则下一个扫描（i+1，j）,当i或者j任一方到达|V|时停止。
这样，在最坏的情况下，扫描一行加一列或者一列加一行的结点，一共有2*|V|-1时间复杂度，因此为O(V)。
7. 关联矩阵，说明BB^T每个元素是什么意思。
其中bij = -1 （如果边j从结点i发出）
1（如果边j进入i结点）
0（其他）
此处需要分类讨论：要明白B^T中i行相当于B中第i列。
①BB^T对角线上的元素，（i，i）= ，这样如果存在一条由i发出或者进入i的边，都会在（i，i）中加一（因为就算是-1平方之后也是1），因此（i，i）就是代表由多少条边从i发出或者进入。
②BB^T非对角线元素，（i，j）= ,由公式或者读者自己画矩阵图可以得出，如果k边从i发出从j进入，或者反过来，bik*bjk就等于-1，否则就为0。原因是i,j不可能位于k边的同一侧，所有必然一正一负。如果k不通过i或者不通过j，则其中一个为0，而结果为0。因此（i,j）可以表示存在多少i,j之间的边，但是加了一个负号。
8. Adj[u]每个项不是链表而是散列表，包含（u，v）这条边在图中存在的结点v。判断一条边是否在图中存在的期望时间是多少？
期望的时间是O(1)，但是最差情况下要扫描所有结点，因此是O(V)。运用二叉树搜索可以将最坏的时间降低为O(lgV)，但是期望时间变坏，因为没有散列表的概率了。