8-4 用邻接矩阵表示图，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？


形成的邻接矩阵有10^6个元素；如果是有向图则拥有1000个非零元素，若是无向图则有1000×2=2000个非零元素；是稀疏矩阵。


8-5 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？

矩阵元素的个数与顶点个数相关。非零元素与边的条数相关。


8-6 有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。

n个顶点连通，如果将n个顶点排成一直线，则很容易知道，至少需要n-1条边才能把它连通。
还是和刚才一样，只不过多一条边，将首尾连起来，使得从每个定点开始都可以回到该顶点。
例子已举。


8-7 对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？

图中的边数等于邻接矩阵中非零元素的一半；查看矩阵中E[i][j]或者E[j][i]是否等于零，零的话不联通，反之连通；假设要观察顶点i的度，只要查看i行有多少个非零元素，即为i的度（如果查看i列也一样，因为无向图的邻接矩阵是行列对称的）。


8-9 试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女——右兄弟链表。算法的首部为
Void Graph::DFS(const int v, int visited[], TreeNode< int > *t)
其中，指针t指向生成森林上具有图顶点v信息的根结点。

答案建立生成森林的主函数里的q，定义很奇怪。还是老老实实按照书中DFS的定义来写。
声明：不写模板了。可以直接修改TreeNode的指针.

void Graph::DFS(){   //主过程
  int* visited=new int[n];   //n为图中顶点的个数 
  for(int i=0;i< n;i++)visited[i]=0;  //初始化辅助数组 
  Tree< int > &T;        //这里要不要写成 Tree T？ 还是迷糊 
  DFS(0,visited,T.root);  //从顶点0开始构建生成森林
  delete[] visited;
}

void Graph::DFS(const int v, int visited[], TreeNode< int > *t){
  t.SetData(GetValue(v));     //访问该顶点，拷贝值到相应森林结点。
  visited[v]=1;               //修改为已访问
  int w=GetFirstNeighbor(v);  //找到顶点v的第一个邻接顶点w
  t=t->FirstChild;            //t指向t的左子女
  while(w!=1){                //有邻接顶点
    if(!visited[w])           //如果没有访问过
      DFS(w,visited,t);       //从该顶点开始建立生成森林
    w=GetNextNeighbor(v,w);   //找到v的下一个邻接顶点
    t=t->NextSibling;         //同时把t指向t的右兄弟
  }
}

8-10 用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价是O(n*e)?还是O(n+e)?或者是O(max(n,e))?

必须要顺邻接表的顶点表挨个检查，并且沿着每条边向下遍历，所以时间代价为O(n+e)。


8-16 试证明在一个有n个顶点的完全图中，生成树的数目至少有2^(n-1)-1

这题有如下疑问
首先生成树的根固定么？如果不固定的话，就相当于将这n个顶点得到一个排序序列，就是生成树了。p（n）显然是答案，当然p(n)永远都大于2^(n-1)-1.这样的解答貌似太简单了。
然后我们假设必须从某个顶点开始，作为生成树的根，那么问题就变成剩下的n-1个顶点，做一个排序序列，那么显然就是比较p(n-1)与2^(n-1)-1。而这个显然必须在n>=5时才能成立，好像又不对。
迷惑中。


8-18 利用Dijkstra算法的思想，设计一个求最小生成树的算法。

计算连通网络的最小生成树的dijkstra算法可描述如下：将连通网络中所有的边以方便的次序逐步加入到初始为空的生成树的边集合T中。每次选择并加入一条边后，需要判断它是否会与先前加入T的边构成回路。如果构成了回路，则从这个回路中将权值最大的边退选。

具体的实现，答案的程序看不太懂。并且从这里开始暂时不把数据结构的答案放到网上了。因为迷糊的东西太多了。