39.数据结构笔记之三十九图的邻接表表示实现
39.数据结构笔记之三十九图的邻接表表示实现
“如果我曾经或多或少地激励了一些人的 , 努力 , 我们的工作 , 曾经或多或少或少地扩展了人类的理解范围 , 因而给这个世界增添了一分欢乐 , 那我也就感到满足了。--爱迪生”
我们来看下图的另一种存储表示方法。
1. 邻接表原理
邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。
邻接表的处理方法是这样的：
（1）图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。
（2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。
1.1 邻接表（无向图）
例如，下图1就是一个无向图的邻接表的结构。
从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图2所示。
1.2 邻接表（有向图）
若是有向图，邻接表结构也是类似的，我们先来看下把顶点当弧尾建立的邻接表，这样很容易就可以得到每个顶点的出度，如下图3：
但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表，如下图4：
此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。
1.3 邻接表（网）
对于带权值的网图，可以在边表结点定义中再增加一个数据域来存储权值即可，如下图5
2. 邻接表代码实现
其他和上一节类似，主要是creategraph函数的变化。
2.1 CreateGraph
该函数实现图的邻接表结构建立.
输入顶点数和边数，然后输入顶点信息。
生成边结点表。最后如下图6：
其中a,b,c表示结点信息，0,1,2表示图的第几个结点。
3. 源码
/* 邻接表表示的图结构*/
#include<stdio.h>
#include<stdlib.h>
#defineDEBUG
#defineMAXVEX1000 //最大顶点数
typedefcharVertexType; //顶点类型应由用户定义
typedefintEdgeType; //边上的权值类型应由用户定义
typedefstructEdgeNode //边表结点
{
intadjvex; //邻接点域，存储该顶点对应的下标
EdgeTypeweigth; //用于存储权值，对于非网图可以不需要
structEdgeNode*next; //链域，指向下一个邻接点
}EdgeNode;
typedefstructVertexNode //顶点表结构
{
VertexTypedata; //顶点域，存储顶点信息
EdgeNode*firstedge; //边表头指针
}VertexNode, AdjList[MAXVEX];
typedefstruct
{
AdjListadjList;
intnumVertexes, numEdges; //图中当前顶点数和边数
}GraphList;
int Locate(GraphList *g, charch)
{
inti;
for(i= 0; i < MAXVEX; i++)
{
if(ch== g->adjList[i].data)
{
break;
}
}
if(i>= MAXVEX)
{
fprintf(stderr,"thereis no vertex.\n");
return-1;
}
returni;
}
//建立图的邻接表结构
void CreateGraph(GraphList *g)
{
inti, j, k;
EdgeNode*e;
EdgeNode*f;
printf("输入顶点数和边数:\n");
scanf("%d,%d",&g->numVertexes, &g->numEdges);
#ifdefDEBUG
printf("%d,%d\n", g->numVertexes,g->numEdges);
#endif
for(i= 0; i < g->numVertexes; i++)
{
printf("请输入顶点%d:\n",i);
g->adjList[i].data= getchar(); //输入顶点信息
g->adjList[i].firstedge= NULL; //将边表置为空表
while(g->adjList[i].data== '\n')
{
g->adjList[i].data= getchar();
}
}
for(i= 0; i < MAXVEX; i++)
{
g->adjList[i].firstedge= NULL; //将边表置为空表
}
//建立边表
for(k= 0; k < g->numEdges; k++)
{
printf("输入边(vi,vj)上的顶点序号:\n");
charp, q;
p =getchar();
while(p== '\n')
{
p= getchar();
}
q =getchar();
while(q== '\n')
{
q= getchar();
}
intm, n;
m =Locate(g, p);
n =Locate(g, q);
if(m== -1 || n == -1)
{
return;
}
#ifdefDEBUG
printf("p = %c\n", p);
printf("q = %c\n", q);
printf("m = %d\n", m);
printf("n = %d\n", n);
#endif
//向内存申请空间，生成边表结点
e = (EdgeNode*)malloc(sizeof(EdgeNode));
if(e== NULL)
{
fprintf(stderr, "malloc()error.\n");
return;
}
//邻接序号为j
e->adjvex = n;
//将e指针指向当前顶点指向的结构
e->next = g->adjList[m].firstedge;
//将当前顶点的指针指向e
g->adjList[m].firstedge= e;
f = (EdgeNode*)malloc(sizeof(EdgeNode));
if(f== NULL)
{
fprintf(stderr, "malloc()error.\n");
return;
}
f->adjvex = m;
f->next = g->adjList[n].firstedge;
g->adjList[n].firstedge= f;
}
}
void printGraph(GraphList *g)
{
int i= 0;
#ifdefDEBUG
printf("printGraph()start.\n");
#endif
while(g->adjList[i].firstedge!= NULL && i < MAXVEX)
{
printf("顶点:%c ", g->adjList[i].data);
EdgeNode*e = NULL;
e = g->adjList[i].firstedge;
while(e!= NULL)
{
printf("%d ",e->adjvex);
e= e->next;
}
i++;
printf("\n");
}
}
int main(intargc, char**argv)
{
GraphListg;
CreateGraph(&g);
printGraph(&g);
return0;
}