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

青旅半醒 2022-04-18 00:37 382阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

设图为：

![20130612143644656][]

则图的邻接表为：

![20130612144817000][]

下面，我们看看程序：

#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表示“入指针”，实际上是综合了正邻接表和逆邻接表的用法，故兼有其优点。

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[20130612143644656]: /images/20220418/f24be912da084f0c9d6039d609d12a37.png
[20130612144817000]: /images/20220418/91b25f0d18cf4fd69ae23c069a20f81c.png
[SouthEast]: /images/20220418/2ae410aa87ad464dbf3d3974baae512c.png