首页 > 代码库 > 邻接表怎么写
邻接表怎么写
最近做图的题比较多,除了克鲁斯卡尔和floyd,像广搜,普里姆,Bellman-Ford,迪杰斯特拉,SPFA,拓扑排序等等,都用到图的邻接表形式。
数据结构书上表示邻接表比较复杂,一般形式如下:
1 typedef struct Node 2 { 3 int dest; //邻接边的弧头结点序号 4 int weight; //权值信息 5 struct Node *next; //指向下一条邻接边 6 }Edge; //单链表结点的结构体 7 8 typedef struct 9 {10 DataType data; //结点的一些数据,比如名字11 int sorce; //邻接边的弧尾结点序号12 Edge *adj; //邻接边头指针13 }AdjHeight; //数组的数据元素类型的结构体14 15 typedef struct16 {17 AdjHeight a[MaxVertices]; //邻接表数组18 int numOfVerts; //结点个数19 int numOfEdges; //边个数20 }AdjGraph; //邻接表结构体
其实有种简洁且高效的表示形式:
1 typedef struct 2 { 3 int to; 4 int w; 5 int next; 6 }Edge; 7 Edge e[MAX]; 8 int pre[MAX]; 9 10 //初始化11 memset(pre,-1,sizeof(pre));12 13 //输入14 scanf("%d %d %d",&from,&to,&w1);15 e[i].to = to; e[i].w = w1; e[i].next = pre[from]; pre[from] = i;16 i++;
上面这段代码中,边的结构体Edge由三个元素组成:弧头结点序号,边权值,下一条边的序号。e[i]指的是第i条边。pre[i]记录的是从当前输入的情况来看,序号为i的弧尾结点发出的第一条边的序号是pre[i]。
这样,在操作某个结点发出的边时,可以像这么做:
1 /*now为弧尾结点序号,i为now所发出的边序号,adj为弧头结点序号,w为now-->adj这条边的权值*/2 for(i = pre[now]; i != -1; i = edge[i].next)3 {4 int adj = edge[i].to;5 int w = edge[i].w;6 //do something...7 }
其实,对于哈希表这类的存储结构(链表法解决冲突),与图的邻接表类似,也可以用类似的表示方法:
1 typedef struct 2 { 3 char e[11]; //value 4 char f[11]; //key 5 int next; //下一个结果(hash冲突) 6 }Entry; 7 Entry entry[M]; 8 int hashIndex[M]; //哈希值为M的结果集的第一个在entry中的序号。 9 10 //输入:对key进行hash,11 sscanf(str,"%s %s",entry[i].e,entry[i].f);12 int hash = ELFHash(entry[i].f);13 entry[i].next = hashIndex[hash];14 hashIndex[hash] = i;15 i++;16 17 //使用:18 for(int k = hashIndex[hash]; k; k = entry[k].next)19 {20 //do something..21 }
以上转自http://yzmduncan.iteye.com/blog/883903
邻接表怎么写
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。