数据结构深入剖析（12）--图的定义及存储结构

一、      图的定义

图是由顶点集合（Vertex）及顶点间的关系集合组成的一种数据结构：

Graph = （V,E）

V = {x | x 属于某个数据对象}是顶点的有穷非空集合。

E = {（x，y）| x，y 属于V}是顶点之间的关系的有穷集合，也叫边（Edge）集合。

二、      有向图 && 无向图

1.    无向边

若顶点x和y之间的边没有方向，则称该边为无向边（x，y）。

2.    无向图

若图中任意两个顶点之间的边均是无向边，则称该图为无向图。

3.    有向边

若顶点x和y之间的边有方向，则称该边为有向边，y>。

4.    有向图

若图中任意两个顶点之间的边均是有向边，则称该图为有向图。

三、      度的定义

顶点v的度是和v相关联的边的数目，记为TD（v）。

入度：以v为头的边的数目，记为ID（v）。

出度：以v为尾的边的数目，记为OD（v）。

很显然：

TD（v）=ID（v） + OD（v）

E = [TD(v₁) + TD(v₂) + … + TD(v_n)] / 2

E = ID(v₁) + ID(v₂) + … + ID(v_n)

E = OD(v₁) + OD(v₂) + … + OD(v_n)

四、      权的定义

与图的边相关的数字叫做权。

五、      图的操作

创建图

销毁图

清空图

加入边

删除边

获取权值

获取结点的度

获取图的结点数

获取图的边数

六、      小结

图是一种扩展的树结构，每个结点可以指向任意的其他结点。

链表是特殊的树结构，树是特殊的图结构。

图这种数据结构常用于网络规划和路径规划等领域。

七、      图的存储结构

邻接矩阵法

      基本思想：

      用一维数组存储顶点----描述顶点相关的数据

      用二维数组存储边----描述顶点间的边

     

      邻接矩阵法的头结点：

           记录顶点个数

           记录与顶点相关的数据描述

           记录描述边集的二维数组

      实现：

//MGraph.h

#ifndef _MGRAPH_H

#define _MGRAPH_H

 

typedef void MGraph;

typedef void MVertex;

typedef void (MGraph_Printf)(MVertex*);

 

MGraph* MGraph_Create(MVertex** v,int n);

 

void MGraph_Destroy(MGraph* graph);

 

void MGraph_Clear(MGraph* graph);

 

int MGraph_AddEdge(MGraph* graph, int v1, int v2, int w);

 

int MGraph_RemoveEdge(MGraph* graph, int v1, int v2);

 

int MGraph_GetEdge(MGraph* graph, int v1, int v2);

 

int MGraph_TD(MGraph* graph, int v);

 

int MGraph_VertexCount(MGraph* graph);

 

int MGraph_EdgeCount(MGraph* graph);

 

void MGraph_Display(MGraph* graph,MGraph_Printf* pFunc);

#endif

 

//MGraph.c

#include

#include "MGraph.h"

#include

typedef struct _tag_MGraph

{

      int count;

      MVertex** v;

      int** matrix;

}TMGraph;

 

MGraph* MGraph_Create(MVertex** v,int n)

{

      TMGraph* ret = NULL;

      int* p = NULL;

      int i = 0;

     

      if((v != NULL) && (n > 0)){

           ret = (TMGraph*)malloc(sizeof(TMGraph));

           if(ret != NULL){

                 ret->count = n;

                 ret->v = (MVertex**)malloc(sizeof(MVertex*) * n);

                

                 ret->matrix = (int**)malloc((sizeof(int*)) * n);

                 p = (int*)calloc(n * n,sizeof(int));

                 if((ret->matrix != NULL) && (ret->v != NULL) && (p != NULL)){

                      for(i = 0;i < n;i++){

                            ret->v[i] = v[i];

                            ret->matrix[i] = p + i * n;

                      }

                 }else{

                      free(p);

                      free(ret->matrix);

                      free(ret->v);

                      free(ret);

                     

                      ret = NULL;

                 }   

           }

      }

      return ret;

}

 

void MGraph_Destroy(MGraph* graph)

{

      TMGraph* tGraph = (TMGraph*)graph;

      if(tGraph != NULL){

           free(tGraph->v);

           free(tGraph->matrix[0]);

           free(tGraph->matrix);

           free(tGraph);

      }

}

 

void MGraph_Clear(MGraph* graph)

{

      TMGraph* tGraph = (TMGraph*)graph;

      if(tGraph != NULL){

           int i = 0;

           int j = 0;

           for(i = 0;i < tGraph->count;i++){

                 for(j = 0;j < tGraph->count;j++){

                      tGraph->matrix[i][j] = 0;

                 }

           }

          

      }

}

 

int MGraph_AddEdge(MGraph* graph, int v1, int v2, int w)

{

      TMGraph* tGraph = (TMGraph*)graph;

      int ret = (tGraph != NULL);

      ret = ret && (0 <= v1) && (v1 < tGraph->count);

      ret = ret && (0 <= v2) && (v2 < tGraph->count);

      ret = ret && (0 <= w);

     

      if(ret){

           tGraph->matrix[v1][v2] = w;

      }

      return ret;

}

 

int MGraph_RemoveEdge(MGraph* graph, int v1, int v2)

{

      TMGraph* tGraph = (TMGraph*)graph;

      int ret = 0;

      int condition = (tGraph != NULL);

      condition = condition && (0 <= v1) && (v1 < tGraph->count);

      condition = condition && (0 <= v2) && (v2 < tGraph->count);

      if(condition){

           ret = tGraph->matrix[v1][v2];

           tGraph->matrix[v1][v2] = 0;

      }

      return ret;

}

int MGraph_GetEdge(MGraph* graph, int v1, int v2)

{

      TMGraph* tGraph = (TMGraph*)graph;

      int ret = 0;

      int condition = (tGraph != NULL);

     

      condition = condition && (0 <= v1) && (v1 < tGraph->count);

      condition = condition && (0 <= v2) && (v2 < tGraph->count);

      if(condition){

           ret = tGraph->matrix[v1][v2];

      }

      return ret;

}

int MGraph_TD(MGraph* graph, int v)

{

      TMGraph* tGraph = (TMGraph*)graph;

      int ret = 0;

      int condition = (tGraph != NULL);

      condition = condition && (0 <= v) && (v < tGraph->count);

     

      if(condition){

           int i = 0;

           int j = 0;

           for(i = 0;i < tGraph->count;i++){

                 if(tGraph->matrix[v][i] != 0){

                      ret++;

                 }

                 if(tGraph->matrix[i][v] != 0){

                      ret++;

                 }

           }

      }

      return ret;

}

int MGraph_VertexCount(MGraph* graph)

{

      TMGraph* tGraph = (TMGraph*)graph;

      int ret = 0;

      if(tGraph != NULL){

           ret = tGraph->count;

      }

      return ret;

}

int MGraph_EdgeCount(MGraph* graph)

{

      TMGraph* tGraph = (TMGraph*)graph;

      int ret = 0;

      int i = 0;

      int j = 0;

      for(i = 0;i < tGraph->count;i++){

           for(j = 0;j < tGraph->count;j++){

                 if(tGraph->matrix[i][j] != 0){

                      ret++;

                 }

           }

      }

      return ret;

}

void MGraph_Display(MGraph* graph,MGraph_Printf* pFunc)

{

      TMGraph* tGraph = (TMGraph*)graph;

      int ret = 0;

      if((tGraph != NULL) && (pFunc != NULL)){

           int i = 0;

           int j = 0;

           for(i = 0;i < tGraph->count;i++){

                 printf("%d:",i);

                 pFunc(tGraph->v[i]);

                 printf(", ");

           }

           printf("\n");

           for(i = 0;i < tGraph->count;i++){

                 for(j = 0;j < tGraph->count;j++){

                      if(tGraph->matrix[i][j] != 0){

                            printf("<");

                            pFunc(tGraph->v[i]);

                            printf(",");

                            pFunc(tGraph->v[j]);

                            printf(", %d",tGraph->matrix[i][j]);

                            printf(">");

                            printf(" ");

                      }

                 }

           }

           printf("\n");

      }

}

邻接链表法

基本思想：

1.    从同一个顶点出发的边链接在同一个链表中

2.    每一个链表结点代表一条边，结点中保存边的另一个顶点的下标和权值。

链接表法的头结点

1.    记录顶点个数

2.    记录与 顶点相关的数据描述

3.    记录描述边集的链表数组。

实现：

//LGraph.h

#ifndef _LGRAPH_H

#define _LGRAPH_H

 

typedef void LGraph;

typedef void LVertex;

typedef void (LGraph_Printf)(LVertex*);

 

LGraph* LGraph_Create(LVertex** v,int n);

 

void LGraph_Destroy(LGraph* graph);

 

void LGraph_Clear(LGraph* graph);

 

int LGraph_AddEdge(LGraph* graph, int v1, int v2, int w);

 

int LGraph_ReLoveEdge(LGraph* graph, int v1, int v2);

 

int LGraph_GetEdge(LGraph* graph, int v1, int v2);

 

int LGraph_TD(LGraph* graph, int v);

 

int LGraph_VertexCount(LGraph* graph);

 

int LGraph_EdgeCount(LGraph* graph);

 

void LGraph_Display(LGraph* graph,LGraph_Printf* pFunc);

#endif

//LGraph.c

#include

#include "LinkList.h"

#include "LGraph.h"

#include

typedef struct _tag_LGraph

{

int count;

LVertex** v;

LinkList** la;

}TLGraph;

 

typedef struct _tag_ListNode

{

LinkListNode header;

int w;

int v;

}TListNode;

LGraph* LGraph_Create(LVertex** v,int n)

{

TLGraph* ret = NULL;

int* p = NULL;

int i = 0;

int ok = 1;

if((v != NULL) && (n > 0)){

      ret = (TLGraph*)malloc(sizeof(TLGraph));

      if(ret != NULL){

            ret->count = n;

            ret->v = (LVertex**)calloc(n,sizeof(LVertex*));

           

            ret->la = (LinkList**)calloc(n,(sizeof(LinkList*)));

           

            ok = (ret->v != NULL) && (ret->la != NULL);

            if(ok){

                 for(i = 0;i < n;i++){

                       ret->v[i] = v[i];

                 }

                 for(i = 0;(i < n) && ok;i++){

                       ok = ok && ((ret->la[i] = LinkList_Create()) != NULL);

                 }

            }else{

                 if(ret->la != NULL){

                       int i = 0;

                       for(i = 0;i < n;i++){

                             LinkList_Destroy(ret->la[i]);

                       }

                 }

                 free(ret->la);

                 free(ret->v);

                 free(ret);

                

                 ret = NULL;

            }   

      }

}

return ret;

}

 

void LGraph_Destroy(LGraph* graph)

{

TLGraph* tGraph = (TLGraph*)graph;

int i = 0;

if(tGraph != NULL){

      LGraph_Clear(tGraph);

     

      for(i = 0;i < tGraph->count;i++){

            LinkList_Destroy(tGraph->la[i]);

      }

      free(tGraph->la);

      free(tGraph->v);

      free(tGraph);

}

}

 

void LGraph_Clear(LGraph* graph)

{

TLGraph* tGraph = (TLGraph*)graph;

int i = 0;

if(tGraph != NULL){

      for(i = 0;i < tGraph->count;i++){

            while(LinkList_Length(tGraph->la[i]) > 0){

                 //LinkList_Clear(tGraph->la[i]);

                 free(LinkList_Delete(tGraph->la[i],0));

            }

      }

}

}

 

int LGraph_AddEdge(LGraph* graph, int v1, int v2, int w)

{

TLGraph* tGraph = (TLGraph*)graph;

TListNode* node = (TListNode*)malloc(sizeof(TListNode));

int ret = (tGraph != NULL);

ret = ret && (0 <= v1) && (v1 < tGraph->count);

ret = ret && (0 <= v2) && (v2 < tGraph->count);

ret = ret && (0 < w) && (node != NULL);

if(ret){

      node->v = v2;

      node->w = w;

      LinkList_Insert(tGraph->la[v1],(LinkListNode*)node,0);

}

return ret;

}

 

int LGraph_RemoveEdge(LGraph* graph, int v1, int v2)

{

TLGraph* tGraph = (TLGraph*)graph;

int ret = 0;

int condition = (tGraph != NULL);

condition = condition && (0 <= v1) && (v1 < tGraph->count);

condition = condition && (0 <= v2) && (v2 < tGraph->count);

if(condition){

      TListNode* node = NULL;

      int i = 0;

      for(i = 0;i < LinkList_Length(tGraph->la[v1]);i++){

            node = (TListNode*)LinkList_Get(tGraph->la[v1],i);

           

            if(node->v = v2){

                 ret = node->w;

                 LinkList_Delete(tGraph->la[v1],i);

                 free(node);

                 break;

            }

      }

}

return ret;

}

int LGraph_GetEdge(LGraph* graph, int v1, int v2)

{

TLGraph* tGraph = (TLGraph*)graph;

int ret = 0;

int condition = (tGraph != NULL);

condition = condition && (0 <= v1) && (v1 < tGraph->count);

condition = condition && (0 <= v2) && (v2 < tGraph->count);

if(condition){

      TListNode* node = NULL;

      int i = 0;

      for(i = 0;i < LinkList_Length(tGraph->la[v1]);i++){

            node = (TListNode*)LinkList_Get(tGraph->la[v1],i);

           

            if(node->v = v2){

                 ret = node->w;

                 break;

            }

      }

}

return ret;

}

int LGraph_TD(LGraph* graph, int v)

{

TLGraph* tGraph = (TLGraph*)graph;

int ret = 0;

int condition = (tGraph != NULL);

condition = condition && (0 <= v) && (v < tGraph->count);

if(condition){

      int i = 0;

      int j = 0;

      for(i = 0;i < tGraph->count;i++){

            for(j = 0;j < LinkList_Length(tGraph->la[i]);j++){

                 TListNode* node = (TListNode*)LinkList_Get(tGraph->la[i],j);

                 if(node->v == v){

                       ret++;

                 }

            }

      }

      ret += LinkList_Length(tGraph->la[v]);

}

return ret;

}

int LGraph_VertexCount(LGraph* graph)

{

TLGraph* tGraph = (TLGraph*)graph;

int ret = 0;

if(tGraph != NULL){

      ret = tGraph->count;

}

return ret;

}

int LGraph_EdgeCount(LGraph* graph)

{

TLGraph* tGraph = (TLGraph*)graph;

int ret = 0;

if(tGraph != NULL){

      int i = 0;

      for(i = 0;i < tGraph->count;i++){

            ret += LinkList_Length(tGraph->la[i]);

      }

}

return ret;

}

void LGraph_Display(LGraph* graph,LGraph_Printf* pFunc)

{

TLGraph* tGraph = (TLGraph*)graph;

int ret = 0;

if((tGraph != NULL) && (pFunc != NULL)){

      int i = 0;

      int j = 0;

      for(i = 0;i < tGraph->count;i++){

            printf("%d:",i);

            pFunc(tGraph->v[i]);

            printf(", ");

      }

      printf("\n");

     

      for(i = 0;i < tGraph->count;i++){

            for(j = 0;j < LinkList_Length(tGraph->la[i]);j++){

                 TListNode* node = (TListNode*)LinkList_Get(tGraph->la[i],j);

                 printf("<");

                 pFunc(tGraph->v[i]);

                 printf(", ");

                 pFunc(tGraph->v[node->v]);

                 printf(", %d",node->w);

                 printf(">");

                 printf(" ");

            }

      }

      printf("\n");

}

}

八、      总结

1.    邻接矩阵法

优点：直观，容易实现

缺点：当顶点数较多，而边数较少时浪费时间和空间。

2.    邻接链表法

优点：有效利用空间，非常适合边数较少的图。

缺点：实现相对复杂，不容易查找两个顶点间的权值。