【基础知识题】

　1．已知如右图所示的有向图，请给出该图的
　(1) 每个顶点的入/出度；
　(2) 邻接矩阵；
　(3) 邻接表；
　(4) 逆邻接表；
　(5) 强连通分量。
　		  
【基础知识题】
　　 		 
 

　2．画出右图所示的无向图的邻接多重表，使得其中每个无向边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。列出深度优先和广度优先搜索遍历该图所得顶点序列和边的序列。
　

  　　　  
  　3．试对右侧所示的无向图，画出其广度优先生成森林。
　 		  　　  
 

　4．已知以二维数组表示的图的邻接矩阵如右图所示。试分别画出自顶点出发进行遍历所得的深度优先生成树和广度优先生成树。
　

  　　  
 

　5．请对右边的无向带权图，
　(1) 写出它的邻接矩阵，并按普里姆算法求其最小生成树；
　(2) 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。
　

  　　  
  　6．试列出右图中全部可能的拓扑有序序列。
　 		  　　  
  　7．对于右图所示的 AOE 网络，计算各活动弧的 e(ai) 和 l(aj) 函数值，各时间(顶点)的 ve(vi) 和 vl(vj) 函数值；列出各条关键路径。
　 		  　  
  　8．试利用 Dijkstra 算法求右图中从顶点 a 到其它各顶点间的最短路径，写出执行算法过程中各步的状态。
　 		  　　　  
  　9．试利用 Floyd 算法求右图所示有向图中各对顶点之间的最短路径。