|
邻接表的形式说明及其建表算法 ()邻接表的形式说明 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 ne; 图中当前顶点数和边数 }ALGraph; //对于简单的应用无须定义此类型可直接使用AdjList类型 ()建立无向图的邻接表算法 void CreateALGraPh(ALGrahp *G) {//建立无向图的邻接表表示 int ijk; EdgeNode *s; scanf(%d%d&G>n&G>e); //读人顶点数和边数 for(i=;in;i++){//建立顶点表 G>adjlist[i]vertex=getchar(); //读入顶点信息 G>adjlist[i]firstedge=NULL;//边表置为空表 for(k=;ke;k++){//建立边表 scanf(%d%d&i&j);读入边(v i v j )的顶点对序号 s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点 s>adjvex=j; //邻接点序号为j s>next=G>adjlist[i]firstedge; G>adjlist[i]firstedge=s; //将新结点*s插入顶点v i 的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s>adjvex=i; //邻接点序号为i s>next=G>adjlist[j]firstedge; G>adjlistk[j]firstedge=s; //将新结点*s插入顶点v j 的边表头部 }//end for }CreateALGraph 该算法的时间复杂度是O(n+e) 注意 ① 建立有向图的邻接表更简单每当读人一个顶点对序号时仅需生成一个邻接序号为j的边表结点将其插入到v j 的 出边表头部即可 ② 建立网络的邻接表时需在边表的每个结点中增加一个存储边上权的数据域 图的两种存储结构比较 邻接矩阵和邻接表是图的两种最常用的存储结构它们各有所长下面从及执行某些常用操作的时间这两方面来作一比较 |
