【大话数据结构C语言】39 图的存储结构（邻接表）

我的公众号是【CodeAllen】，程序员技术交流①群：736386324,转载请注明出处

上一篇说的临接矩阵是不错的图存储结构，但是对于边数相对顶点较少的图，这种结构是存在对存储空间极大浪费的

因此可以考虑另外一种存储结构：比如把数组和链表结合一起来存储

临接表无向图的处理方法：

1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便

2.图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储

临接表有向图的处理方法：

以把顶点当弧尾建立的临接表，这样很容易可以得到每个顶点的出度

临接表网的处理方法：

对于带权值的网图，可以在边表结点定义中在增加一个数据域来存储权值即可

代码实现：

  

   

    

     

    
    

     

      #define MAXVEX 100
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct EdgeNode         // 边表结点
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          int adjvex;                 // 邻接点域，存储该顶点对应的下标
     
    
   

    

     

    
    

     

          int weight;                 // 用于存储权值，对于非网图可以不需要
     
    
   

    

     

    
    

     

          struct EdgeNode *next;      // 链域，指向下一个邻接点
     
    
   

    

     

    
    

     

      } EdgeNode;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct VertexNode       // 顶点表结点
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          char data;                  // 顶点域，存储顶点信息
     
    
   

    

     

    
    

     

          EdgeNode *firstEdge;        // 边表头指针
     
    
   

    

     

    
    

     

      } VertexNode, AdjList[MAXVEX];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          AdjList adjList;
     
    
   

    

     

    
    

     

          int numVertexes, numEdges;  // 图中当前顶点数和边数
     
    
   

    

     

    
    

     

      } GraphAdjList;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      // 建立图的邻接表结构
     
    
   

    

     

    
    

     

      void CreateALGraph(GraphAdjList *G)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          int i, j, k;
     
    
   

    

     

    
    

     

          EdgeNode *e;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          printf("请输入顶点数和边数：\n");
     
    
   

    

     

    
    

     

          scanf("%d %d", &G->numVertexes, &G->numEdges);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          // 读取顶点信息，建立顶点表
     
    
   

    

     

    
    

     

          for( i=0; i < G->numVertexes; i++ )
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              scanf("%c", &G->adjList[i].data);
     
    
   

    

     

    
    

     

              G->adjList[i].firstEdge = NULL;     // 初始化置为空表
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          for( k=0; k < G->numEdges; k++ )
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              printf("请输入边(Vi,Vj)上的顶点序号：\n");
     
    
   

    

     

    
    

     

              scanf("%d %d", &i, &j);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              e = (EdgeNode *)malloc(sizeof(EdgeNode));
     
    
   

    

     

    
    

     

              e->adjvex = j;                      // 邻接序号为j
     
    
   

    

     

    
    

     

              e->next = G->adjList[i].firstEdge;
     
    
   

    

     

    
    

     

              G->adjList[i].firstEdge = e;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              e = (EdgeNode *)malloc(sizeof(EdgeNode));
     
    
   

    

     

    
    

     

              e->adjvex = i;                      // 邻接序号为i
     
    
   

    

     

    
    

     

              e->next = G->adjList[j].firstEdge;
     
    
   

    

     

    
    

     

              G->adjList[j].firstEdge = e;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。

原文链接：allen5g.blog.csdn.net/article/details/116310626