图的邻接表表示法及顶点入度 出度的计算方法

    设图为：

      则图的邻接表为：

       下面，我们看看程序：

#include <iostream>#define VERTEX 4using namespace std;// 边表结点typedef struct node{ int index; struct node *next;}Node;// 顶点表结点typedef struct vertex{ int data; Node *first;}VertexNode, AdjList[VERTEX];// 图typedef struct{ int n, e; AdjList adj;}AdjGraph;// 创建图void createAdjGraph(AdjGraph &g){ g.n = VERTEX; g.e = VERTEX + 1; // 下面创建AdjGraph的代码很丑陋，仅供示意 Node *p1, *p2, *p3; p1 = new Node; p2 = new Node; p3 = new Node; p1->index = 1; p2->index = 2; p3->index = 3; g.adj[0].first = p1; p1->next = p2; p2->next = p3; p3->next = NULL; Node *q0, *q2; q0 = new Node; q2 = new Node; q0->index = 0; q2->index = 2; g.adj[1].first = q0; q0->next = q2; q2->next = NULL; Node *r0, *r1, *r3; r0 = new Node; r1 = new Node; r3 = new Node; r0->index = 0; r1->index = 1; r3->index = 3; g.adj[2].first = r0; r0->next = r1; r1->next = r3; r3->next = NULL; Node *s0, *s2; s0 = new Node; s2 = new Node; s0->index = 0; s2->index = 2; g.adj[3].first = s0; s0->next = s2; s2->next = NULL;}// 求图中顶点的入度void inDegree(AdjGraph g){ Node *p; int i, inD; for(i = 0; i < g.n; i++) {  inD = 0;  p = g.adj[i].first;  while(NULL != p)  {   inD++;   p = p->next;  }  cout << "顶点" << i << "的入度为:" << inD << endl;  }}// 求图中顶点的出度void outDegree(AdjGraph g){ Node *p; int i, outD; for(i = 0; i < g.n; i++) {  outD = 0;  p = g.adj[i].first;  while(NULL != p)  {   outD++;   p = p->next;  }  cout << "顶点" << i << "的出度为:" << outD << endl;  }}int main(){ AdjGraph g; createAdjGraph(g); inDegree(g);  // 打印入度 cout << endl; outDegree(g); // 打印出度 return 0;}

      结果为：

顶点0的入度为:3
顶点1的入度为:2
顶点2的入度为:3
顶点3的入度为:2

顶点0的出度为:3
顶点1的出度为:2
顶点2的出度为:3
顶点3的出度为:2


        值得一提的是，对于有向图而言，我们一般采用的邻接表是正邻接表，在这种情况下，求图的各顶点的出度相对较易，而入度则不好直接求。如果用的邻接表为逆邻接表，那么情况则刚好相反。那么，有没有什么好的办法解决这一问题呢？有的！可以采用十字链表，其原理是：用firstOut表示“出指针”，用firstIn表示“入指针”，实际上是综合了正邻接表和逆邻接表的用法，故兼有其优点。