4.2 图的存储及基本操作

二、综合应用题

　　1．综合应用题题目部分
　　● 练习1：已知一个有向图G，如图4-2所示。

　　（1）写出其邻接矩阵；
　　（2）写出其邻接表与逆邻接表；
　　（3）写出其强连通分量。
　　● 练习2：设有向图G，如图4-3所示，试画出其十字链表结构。
 

　　● 练习3：写一算法，将图的邻接表表示转换成邻接矩阵表示。
　　● 练习4：已知无向图采用邻接表存储方式，试写出删除边(i,j)的算法。假定(i,j)对应于该边在邻接表中的顶点下标。
　　2．综合应用题答案与分析
　　若无特定说明，本节中涉及的图的邻接表存储结构，其数据结构如下：
　　typedef struct ArcNode{
  　　 int adjvex;
  　　 struct ArcNode  *next;
  　　 InfoType       *info;
　　}ArcNode;

　　typedef struct VNode{
　　   vertexTpye   data;
  　　 ArcNode     *firstarc;
　　} AdjList;
　　习题1分析：
　　（1）其邻接矩阵如下所示。

　　（2）其邻接表如图4-4所示。

　　其逆邻接表如图4-5所示。

　　（3）其强连通分量如图4-6所示。

　　习题2分析：
　　该有向图的十字链表结构如图4-7所示。