图总结之存储结构代码详解

一、图的存储结构

1.1 邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

看一个实例，下图左就是一个无向图。

从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足a_ij = a_{ji<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3ViPqGjvLS0077Y1fO1xNfzyc+9x7W909LPwr3HtcTW97bUvcfP386q1uGjrNPSyc+9x7XE1Kq6zdfzz8K9x8/gttTTprXE1KrIq7a8ysfP4LXItcShozxicj4KPC9wPgo8cD4KICAgILTT1eK49r7Y1fPW0KOsutzI3dLX1qq1wM281tC1xNDFz6Khozxicj4KPC9wPgo8cD4KICAgIKOoMaOp0qrF0LbPyM7S4sG9tqW148rHt/HT0LHfzt6x377NutzI3dLXwcujuzxicj4KPC9wPgo8cD4KICAgIKOoMqOp0qrWqrXAxLO49ralteO1xLbIo6zG5Mq1vs3Kx9XiuPa2pbXjdmnU2sHavdO+2NXz1tC12mnQ0Lvyo6i12mnB0KOptcTUqsvY1q66zaO7PGJyPgo8L3A+CjxwPgogICAgo6gzo6nH87alteN2abXEy/nT0MHavdO1477Nyse9q77Y1fPW0LXaadDQ1KrL2Mmow+jSu7Hpo6xhcmNbaV1bal3OqjG+zcrHwdq907Xjo7s8L3A+CjxwPgogICAgtvjT0M/yzby9sr6/yOu2yLrNs/a2yKOstqW143ZptcTI67bIzqoxo6zV/brDyse12mnB0Lj3yv3WrrrNoaO2pbXjdmm1xLP2tsjOqjKjrLy0tdpp0NC1xLj3yv3WrrrNoaM8YnI+CjwvcD4KPHA+CiAgICDI9M28R8rHzfjNvKOs09BuuPa2pbXjo6zU8sHavdO+2NXzysfSu7j2biputcS3vdXzo6y2qNLlzqqjujxicj4KPC9wPgo8cD4KICAgIDxpbWcgc3JjPQ=="https://www.cppentry.com/upload_files/article/49/1_nhwvc__.png" width="362" height="71" alt="\">}

这里的w_ij表示(v_i,v_j)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下面左图就是一个有向网图，右图就是它的邻接矩阵。

那么邻接矩阵是如何实现图的创建的呢？代码如下。（有向图）

#include 
  
   
typedef char VertexType;                //顶点类型
typedef int EdgeType;                   //边权值类型
#define INF    65535               //用65535来代表无穷大
typedef struct
{
    VertexType vexs[MAXVEX];            //顶点表
    EdgeType   arc[MAXVEX][MAXVEX];         //邻接矩阵，可看作边
    int numVertexes, numEdges;      //图中当前的顶点数和边数
}Graph;

void CreateGraph(Graph *G)
{
	int i,j,k,w;
	printf("输入顶点数和边数：\n");
	scanf("%d%d",&G->numVertexes,&G->numEdges);
	getchar();
	printf("输入%d个顶点符号：\n",G->numVertexes);
	for(i=0;i
   
    numVertexes;i++) scanf("%c",&G->vexs[i]); getchar(); for(i=0;i
    
     numVertexes;i++) for(j=0;j
     
      numVertexes;j++) G->arc[i][j]=INF; for(k=0;k<2*G->numEdges;k++)//关于循环次数无向图G->numEdges次，有向图G->numEdges*2次 { printf("输入边(vi,vj)上的下标i,j和权w:");//如果是有向图，就按照方向输入下标 scanf("%d%d%d",&i,&j,&w); G->arc[i][j]=w; G->arc[j][i]=G->arc[i][j];//有向图去掉这句 } } //打印图 void printGraph(Graph g) { int i, j; for(i = 0; i < g.numVertexes; i++) { for(j = 0; j < g.numVertexes; j++) { printf("%d ", g.arc[i][j]); } printf("\n"); } } int main() { Graph g; //邻接矩阵创建图 CreateGraph(&g); printGraph(g); return 0; }
     
    
   
  

测试数据：

4 6
ABCD
0 1 8
0 2 7
0 3 65535
1 0 65535
1 2 4
1 3 65535
2 0 65535
2 1 65535
2 3 2
3 0 5
3 1 3
3 2 65535

输出：

1.2 邻接表

邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。

邻接表的处理方法是这样的：

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

（2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

例如，下图就是一个无向图的邻接表的结构。

从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示。

对于邻接表结构，图的建立代码如下。（无向图）

#include 
  
   
#define MAXVEX 1000         //最大顶点数
typedef char VertexType;        //顶点类型
typedef int EdgeType;           //边上权值类型

typedef struct EdgeNode         //边表结点
{
    int adjvex;         //邻接点域，存储该顶点对应的下标
    EdgeType weigth;        //用于存储权值，对于非网图可以不需要
    struct EdgeNode *next;      //链域，指向下一个邻接点
}EdgeNode;

typedef struct VertexNode       //顶点表结构
{
    VertexType data;        //顶点域，存储顶点信息
    EdgeNode *firstedge;        //边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVertexes, numEdges;  //图中当前顶点数和边数
}GraphList;

//建立图的邻接表结构
void CreateGraph(GraphList *g)
{
    int i, j, k;
    EdgeNode *e;
    printf("输入顶点数和边数:\n");
    scanf("%d%d", &g->numVertexes, &g->numEdges);
	getchar();
    for(i = 0; i 
   
    numVertexes; i++) { printf("请一次一个输入顶点%d:\n", i); scanf("%c",&g->adjList[i].data); //输入顶点信息 getchar(); g->adjList[i].firstedge = NULL; //将边表置为空表 } g->adjList[i].firstedge = NULL; //建立边表 for(k = 0; k < g->numEdges; k++)//关于邻接表的循环次数无向图与与有向图都是g->numEdges次 { printf("输入无向图边(vi,vj)上的顶点序号和权值:\n"); int w; scanf("%d%d%d",&i,&j,&w); e =new EdgeNode; e->adjvex = j; //邻接序号为j e->weigth = w; //边
    
     的权值 e->next = g->adjList[i].firstedge;//将e指针指向当前顶点指向的结构 g->adjList[i].firstedge = e;//将当前顶点的指针指向e e = new EdgeNode; e->adjvex =i; e->weigth = w; //边
     
      的权值 e->next = g->adjList[j].firstedge; g->adjList[j].firstedge = e; } } void printGraph(GraphList *g) { int i = 0; while(g->adjList[i].firstedge != NULL && i < MAXVEX) { printf("顶点:%c\n", g->adjList[i].data); EdgeNode *e = NULL; e = g->adjList[i].firstedge; while(e != NULL) { if(e->adjvex!=i) printf("邻接点下标:%d 边:<%c,%c> weigth: %d\n", e->adjvex,g->adjList[i].data,g->adjList[e->adjvex].data,e->weigth); e = e->next; } i++; printf("\n"); } } int main(int argc, char **argv) { GraphList g; CreateGraph(&g); printGraph(&g); return 0; }
     
    
   
  

测试数据：

4 6
A
B
C
D
0 2 5
0 3 7
1 0 8
2 1 3
2 3 2
3 1 4

输出：

1.3 十字链表

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度情况。下面介绍的这种有向图的存储方法：十字链表，就是把邻接表和逆邻接表结合起来的。

重新定义顶点表结点结构，如下所示。

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

重新定义边表结构，如下所示。

其中，tailvex是指弧起点在顶点表的下表，headvex是指弧终点在顶点表的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以增加一个weight域来存储权值。

比如下图，顶点依然是存入一个一维数组，实线箭头指针的图示完全与邻接表相同。就以顶点v₀来说，firstout指向的是出边表中的第一个结点v₃。所以，v₀边表结点hearvex = 3，而tailvex其实就是当前顶点v₀的下标0，由于v₀只有一个出边顶点，所有headlink和taillink都是空的。

重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v₀来说，它有两个顶点v₁和v₂的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点，如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v₂，如上图圆圈2。对于顶点v₁，它有一个入边顶点v₂，所以它的firstin指向顶点v₂的边表结点中headvex为1的结点，如上图圆圈3。

十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以v为尾的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。

而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图应用中，十字链表是非常好的数据结构模型。

这里就介绍以上三种存储结构，除了第三种存储结构外，其他的两种存储结构比较简单。