广交好友~~ 想要讨论的可以留下msn~~~ 希望群友网友经常能提出问题，一起解决，共同提高

邻接表

上一篇 / 下一篇  2013-01-21 17:20:20 / 个人分类：Java&C

查看( 796 ) / 评论( 0 ) / 评分( 0 / 0 )

一、邻接表

邻接表是图的一种链式存储结构。对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。又称链接表。
补充：
1.在有向图的邻接表中不易找到指向该顶点的弧。
2.在有向图的邻接表中，对每个顶点，链接的是以该顶点为弧尾的邻接点。

二、图的邻接表表示法

注意：
n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。

1．有向图的邻接表

对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。
【例】有向图G6的邻接表表示如下图所示，其中顶点v1的邻接表上两个表结点中的顶点序号分别为0和4，它们分别表示从v1射出的两条边(简称为v1的出边)：<v1，v0>和<v1，v4>。

2．有向图的逆邻接表

在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。
入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。
【例】G6的逆邻表如上面(b)图所示，其中v0的人边表上两个表结点1和3分别表示射人v0的两条边(简称为v0的入边)：<v1，v0>和<v3，v0>。
注意：
n个顶点e条边的有向图，它的接表表示中有n个顶点表结点和e个边表结点。
3．邻接表的形式说明及其建表算法　
（1）邻接表的形式说明
typedef struct node{//边表结点
int adjvex； //邻接点域
struct node *next； //链域
//若要表示边上的权，则应增加一个数据域
}EdgeNode;
typedef struct vnode{ //顶点表结点
VertexType vertex； //顶点域
EdgeNode *firstedge；//边表头指针
}VertexNode；
typedef VertexNode AdjList[MaxVertexNum]；//AdjList是邻接表类型
typedef struct{
AdjList adjlist；//邻接表
int n，e； 图中当前顶点数和边数
}ALGraph； //对于简单的应用，无须定义此类型，可直接使用AdjList类型。
(2)建立无向图的邻接表算法
void CreateALGraPh(ALGrahp *G)
{//建立无向图的邻接表表示
int i，j，k；
EdgeNode *s；
scanf("%d%d"，&G->n，&G->e)； //读人顶点数和边数
for(i=0；i<G->n；i++){//建立顶点表
G->adjlist[i].vertex=getchar()； //读入顶点信息
G->adjlist[i].firstedge=NULL；//边表置为空表
}
for(k=0；k<G->e；k++){//建立边表
scanf("%d%d"，&i,&j)；读入边(vi，vj)的顶点对序号
s=(EdgeNode *)malloc(sizeof(EdgeNode))； //生成边表结点
s->adjvex=j; //邻接点序号为j
s->next=G->adjlist[i].firstedge；
G->adjlist[i].firstedge=s； //将新结点*s插入顶点vi的边表头部
s=(EdgeNode *)malloc(sizeof(EdgeNode))；
s->adjvex=i; //邻接点序号为i
s->next=G->adjlist[j].firstedge；
G->adjlistk[j].firstedge=s； //将新结点*s插入顶点vj的边表头部
}//end for
}CreateALGraph
该算法的时间复杂度是O(n+e)。
注意：
① 建立有向图的邻接表更简单，每当读入一个顶点对序号<i,j>时，仅需生成一个邻接序号为j的边表结点，将其插入到vj的出边表头部即可。
② 建立网络的邻接表时，需在边表的每个结点中增加一个存储边上权的数据域。


收藏 举报

TAG:

 

评分：0

我来说两句

Open Toolbar