Question

1.邻接表表示法 "Link_Graph.h"

#include <iostream>
using namespace std;

#define N 100

struct Vertex;
struct Edge
{
  int start;
  int end;
  int value;
  Edge *next;
  Edge(int s, int e, int v):start(s),end(e),value(v),next(NULL){}
};
struct Vertex
{
  Edge *head;
  Vertex():head(NULL){};
};
class Link_Graph
{
public:
  int n;
  Vertex *V;
  Link_Graph(int num):n(num)
  {
    V = new Vertex[n+1];
  }
  ~Link_Graph(){delete []V;}
  void AddSingleEdge(int start, int end, int value = 1)
  {
    Edge *NewEdge = new Edge(start, end, value);
    if(V[start].head == NULL || V[start].head->end > end)
    {
      NewEdge->next = V[start].head;
      V[start].head = NewEdge;
    }
    else
    {
      Edge *e = V[start].head, *pre = e;
      while(e != NULL && e->end < end)
      {
        pre = e;
        e = e->next;
      }
      if(e && e->end == end)
      {
        delete NewEdge;
        return;
      }
      NewEdge->next = e;
      pre->next = NewEdge;
    }
  }
  void AddDoubleEdge(int a, int b, int value = 1)
  {
    AddSingleEdge(a, b, value);
    AddSingleEdge(b, a, value);
  }
  void DeleteSingleEdge(int start, int end)
  {
    Edge *e = V[start].head, *pre = e;
    while(e && e->end < end)
    {
      pre = e;
      e = e->next;
    }
    if(e == NULL || e->end > end) return;
    if(e == V[start].head)
      V[start].head = e->next;
    else
      pre->next = e->next;
    delete e;
  }
  void DeleteDoubleEdge(int a, int b)
  {
    DeleteSingleEdge(a, b);
    DeleteSingleEdge(b, a);
  }
  //22.1-1
  void OutDegree();
  void InDegree();
  //22.1-2
  void Print();
  //22.1-3
  Link_Graph* Reverse();
  //22.1-5
  Link_Graph* Square();
};

void Link_Graph::OutDegree()
{
  int i, cnt = 0;
  Edge *e;
  for(i = 1; i <= n; i++)
  {
    cnt = 0;
    e = V[i].head;
    while(e)
    {
      cnt++;
      e = e->next;
    }
    cout<<"顶点"<<i<<"的出度为"<<cnt<<endl;
  }
}

void Link_Graph::InDegree()
{
  int ret[N+1] = {0}, i;
  Edge *e;
  for(i = 1; i <= n; i++)
  {
    e = V[i].head;
    while(e)
    {
      ret[e->end]++;
      e = e->next;
    }
  }
  for(i = 1; i <= n; i++)
    cout<<"顶点"<<i<<"的入度为"<<ret[i]<<endl;
}

void Link_Graph::Print()
{
  int i;
  Edge *e;
  for(i = 1; i <= n; i++)
  {
    cout<<i;
    e = V[i].head;
    while(e)
    {
      cout<<"->"<<e->end;
      e = e->next;
    }
    cout<<endl;
  }
}

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; 
}

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;
}

2.邻接矩阵表示法

#include <iostream>
using namespace std;

#define N 100

class Mat_Graph
{
public:
  int n;
  int Map[N+1][N+1];

  Mat_Graph(int num):n(num)
  {
    memset(Map, 0, sizeof(Map));
  }
  void AddDoubleEdge(int a, int b, int value = 1)
  {
    AddSingleEdge(a, b, value);
    AddSingleEdge(b, a, value);
  }
  void AddSingleEdge(int start, int end, int value = 1)
  {
    Map[start][end] = value;
  }
  void DeleteDoubleEdge(int a, int b)
  {
    DeleteSingleEdge(a, b);
    DeleteSingleEdge(b, a);
  }
  void DeleteSingleEdge(int start, int end)
  {
    Map[start][end] = 0;
  }
  //22.1-2
  void Print();
  //22.1-3
  Mat_Graph* Reverse();
  //22.1-5
  Mat_Graph* Square();
  //22.1-6
  bool Universal_Sink();
};

void Mat_Graph::Print()
{
  int i, j;
  for(i = 1; i <= n; i++)
  {
    for(j = 1; j <= n; j++)
      cout<<Map[i][j]<<' ';
    cout<<endl;
  }
}

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;
}

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;
}

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;  
  }  
}

 

3.main.cpp

#include <iostream>
using namespace std;

#include "Link_Graph.h"
#include "Mat_Graph.h"

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;
}
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;
}
void Test3()
{
  cout<<"Test3"<<endl;
  int n, a, b;
  cin>>n;
  Link_Graph *LG = new Link_Graph(n);
  Mat_Graph *MG = new Mat_Graph(n);
  while(cin>>a>>b && a && b)//输入 00 时结束
  {
    LG->AddSingleEdge(a, b);
    MG->AddSingleEdge(a, b);
  }
  Link_Graph *NewLG = LG->Reverse();
  NewLG->Print();
  Mat_Graph *NewMG = MG->Reverse();
  NewMG->Print();
  delete LG;
  delete MG;
  delete NewLG;
  delete NewMG;
}
void Test5()
{
  cout<<"Test5"<<endl;
  int n, a, b;
  cin>>n;
  Link_Graph *LG = new Link_Graph(n);
  Mat_Graph *MG = new Mat_Graph(n);
  while(cin>>a>>b && a && b)//输入 00 时结束
  {
    LG->AddSingleEdge(a, b);
    MG->AddSingleEdge(a, b);
  }
  Link_Graph *NewLG = LG->Square();
  NewLG->Print();
  Mat_Graph *NewMG = MG->Square();
  NewMG->Print();
  delete LG;
  delete MG;
  delete NewLG;
  delete NewMG;
}

void Test6()
{
  cout<<"Test6"<<endl;
  int n, a, b;
  cin>>n;
  Mat_Graph *MG = new Mat_Graph(n);
  while(cin>>a>>b && a && b)//输入 00 时结束
    MG->AddSingleEdge(a, b);
  if(MG->Universal_Sink())
    cout<<"包含通用的汇"<<endl;
  else
    cout<<"不包含通用的汇"<<endl;
  delete MG;
}
/*
6
1 2
1 4
4 2
2 5
5 4
3 5
3 6
6 6
0 0
*/
int main()
{
  Test1();
  Test2();
  Test3();
  Test5();
  Test6();
  return 0;
}