Question

22.1-1

计算出度的时间：E

计算入度的时间：E

void Test1()
{
  cout<<"Test1"<<endl;
  int n, a, b;
  cin>>n;
  Link_Graph *LG = new Link_Graph(n);
  while(cin>>a>>b && a && b)//输入 00 时结束
    LG->AddSingleEdge(a, b);
  LG->OutDegree();
  LG->InDegree();
  delete LG;
}

22.1-2

void Test2()
{
  cout<<"Test2"<<endl;
  Link_Graph *LG = new Link_Graph(6);
  Mat_Graph *MG = new Mat_Graph(6);
  int edge[6][2] = {{1,2},{1,3},{2,4},{2,5},{3,6},{3,6}};
  int i = 0;
  for(i = 0; i < 6; i++)
  {
    LG->AddSingleEdge(edge[i][0], edge[i][1]);
    MG->AddSingleEdge(edge[i][0], edge[i][1]);
  }
  LG->Print();
  MG->Print();
  delete LG;
  delete MG;
}

邻接表表示：

1->2->3

2->4->5

3->6->7

4

5

6

7

矩阵表示：

0110000

0001100

0000011

0000000

0000000

0000000

0000000

22.1-3

邻接表表示的有向图的转置

Link_Graph* Link_Graph::Reverse()
{
  Link_Graph *ret = new Link_Graph(n);  
  int i;  
  //遍历图 G 中的每一条边，以终点为起点，以起点为终点，加入到新图 RET 中  
  for(i = 1; i <= n; i++)  
  {  
    Edge *e = V[i].head;  
    while(e)  
    {  
      ret->AddSingleEdge(e->end, e->start);  
      e = e->next;  
    }  
  }  
  return ret; 
}

邻接矩阵表示的有向图的转置

Mat_Graph* Mat_Graph::Reverse()
{
  int i, j;
  Mat_Graph *ret = new Mat_Graph(n);
  for(i = 1; i <= n; i++)
  {
    for(j = 1; j <= n; j++)
      if(Map[i][j])
        ret->AddSingleEdge(j, i);
  }
  return ret;
}

22.1-4

遍历多重图中的每一条边，通过 AddDoubleAdge() 函数把它加入到另一个图中

22.1-5

邻接表表示的有向图的平方图

Link_Graph* Link_Graph::Square()
{
  int i;
  Link_Graph *ret = new Link_Graph(n);  
  //遍历图中每个顶点  
  for(i = 1; i <= n; i++)  
  {  
    //遍历以该顶点为起点的边  
    Edge *e = V[i].head, *e2;  
    while(e)  
    {  
      //把原来有的边加入到新图中  
      ret->AddSingleEdge(e->start, e->end);  
      //把以 E 的终点为起点的边加入新图中  
      e2 = V[e->end].head;  
      while(e2)  
      {  
        ret->AddSingleEdge(e->start, e2->end);  
        e2 = e2->next;  
      }  
      e = e->next;  
    }   
  }  
  return ret;
}

邻接矩阵表示的有向图的平方图

Mat_Graph* Mat_Graph::Square()
{
  int i, j, k;
  Mat_Graph *ret = new Mat_Graph(n);  
  //遍历图中每个顶点  
  for(i = 1; i <= n; i++)  
  {  
    for(j = 1; j <= n; j++)  
    {  
      if(Map[i][j])  
      {  
        //把原来有的边加入到新图中  
        ret->AddSingleEdge(i, j);
        //把以 E 的终点为起点的边加入新图中  
        for(k = 1; k <= n; k++)  
          if(Map[j][k])  
            ret->AddSingleEdge(i, k);  
      }  
    }  
  }  
  return ret;
}

22.1-6

如果 A[i, j] = 1，即(i, j)∈E（1≤i≤|V|，1≤j≤|V|，E 是 G 的边集），那么顶点 i 就不可能是通用汇点，因为它有一条出边。

现在假设 A[i, j] = 0，即(i, j)∉E，且 i≠j。在这种情况下，顶点 j 就不可能是通用汇点，因为它的入度小于|V|-1

因此，这个问题等价于：给定一个有向图Ｇ的|V|×|V|邻接矩阵 A，在 O(|V|) 时间内判断是否存在一个整数 j（1≤j≤|V|），使得对于所有的 i（1≤i≤|V|且 i≠j）都有 A[i, j] = 1，对于所有的 k（1≤k≤|V|）都有 A[j, k] = 0。更形象地说，就是判断 A 里面是否有这样一个“十”字：这“十”字的横全是 0，竖全是 1（除了“十”字的中心）。

bool Mat_Graph::Universal_Sink()
{
  //i 指向有可能是汇的编号最小的点  
  int i = 1, j = 1;  
  while(j <= n)  
  {  
    //map[i][j] = 0,那么 j 没有 i 的入，一定不是汇，i 可能是汇  
    if(Map[i][j] == 0)  
      j++;  
    //若 map[i][j] = 1，则(1)i 有出，i 不是汇(2)map[i][i+1..j-1]=0，i+1..j-1 都不是汇(3)j 及 j 以后的点可能是汇  
    //若 i=j，j 也不是汇，j+1 可能是汇    
    else if(i == j)  
    {  
      i++;  
      j++;  
    }  
    //若 i!=j，j 以前的点都不是汇，j 可能是汇  
    else i = j;  
  }  
  //没有汇  
  if(i > n)  
    return false;  
  //找到有可能是汇的点，但是还是需要验证一下  
  else  
  {  
    //汇的纵向都是 1，除了 map[i][i]  
    for(j = 1; j <= i-1; j++)  
    {  
      if(Map[i][j] == 1)  
        return false;  
    }  
    //汇的横向都是 0  
    for(j = 1; j <= n; j++)  
      if( i != j && Map[j][i] == 0)  
        return false;  
    return true;  
  }  
}

22.1-7

B = -BT

BBT = -B2

22.1-8

类似于邻接表与邻接矩阵的折中策略