最近做图的题比较多,除了克鲁斯卡尔和floyd,像广搜,普里姆,Bellman-Ford,迪杰斯特拉,SPFA,拓扑排序等等,都用到图的邻接表形式。
数据结构书上表示邻接表比较复杂,一般形式如下:
typedef struct Node
{
int dest; //邻接边的弧头结点序号
int weight; //权值信息
struct Node *next; //指向下一条邻接边
}Edge; //单链表结点的结构体
typedef struct
{
DataType data; //结点的一些数据,比如名字
int sorce; //邻接边的弧尾结点序号
Edge *adj; //邻接边头指针
}AdjHeight; //数组的数据元素类型的结构体
typedef struct
{
AdjHeight a[MaxVertices]; //邻接表数组
int numOfVerts; //结点个数
int numOfEdges; //边个数
}AdjGraph; //邻接表结构体
其实有种简洁且高效的表示形式:
typedef struct
{
int to;
int w;
int next;
}Edge;
Edge e[MAX];
int pre[MAX];
//初始化
memset(pre,-1,sizeof(pre));
//输入
scanf("%d %d %d",&from,&to,&w1);
e[i].to = to; e[i].w = w1; e[i].next = pre[from]; pre[from] = i;
i++;
上面这段代码中,边的结构体Edge由三个元素组成:弧头结点序号,边权值,下一条边的序号。e[i]指的是第i条边。pre[i]记录的是从当前输入的情况来看,序号为i的弧尾结点发出的第一条边的序号是pre[i]。
这样,在操作某个结点发出的边时,可以像这么做:
/*now为弧尾结点序号,i为now所发出的边序号,adj为弧头结点序号,w为now-->adj这条边的权值*/
for(i = pre[now]; i != -1; i = edge[i].next)
{
int adj = edge[i].to;
int w = edge[i].w;
//do something...
}
其实,对于哈希表这类的存储结构(链表法解决冲突),与图的邻接表类似,也可以用类似的表示方法:
typedef struct
{
char e[11]; //value
char f[11]; //key
int next; //下一个结果(hash冲突)
}Entry;
Entry entry[M];
int hashIndex[M]; //哈希值为M的结果集的第一个在entry中的序号。
//输入:对key进行hash,
sscanf(str,"%s %s",entry[i].e,entry[i].f);
int hash = ELFHash(entry[i].f);
entry[i].next = hashIndex[hash];
hashIndex[hash] = i;
i++;
//使用:
for(int k = hashIndex[hash]; k; k = entry[k].next)
{
//do something..
}
- 大小: 25.4 KB
分享到:
相关推荐
这是我整理过的关于ACM题目常用到的算法代码,word文档,条理清晰,绝对有用。目录如下: 一.数论 1.阶乘最后非零位 2. 模线性方程(组) 3. 素数表 4. 素数随机判定(miller_rabin) 5. 质因数分解 6. 最大公...
二分图最大匹配(hungary邻接表形式,邻接阵接口) 二分图最大匹配(hungary正向表形式) 二分图最佳匹配(kuhn_munkras邻接阵形式) 一般图最大匹配(邻接表形式) 一般图最大匹配(邻接阵形式) 一般图最大匹配(正向表...
二分图最大匹配(hungary邻接表形式,邻接阵接口) 二分图最大匹配(hungary正向表形式) 二分图最佳匹配(kuhn_munkras邻接阵形式) 一般图最大匹配(邻接表形式) 一般图最大匹配(邻接阵形式) 一般图最大匹配(正向表...
8.1 二分图最大匹配(hungary邻接表) 83 8.2 二分图最大匹配(hungary邻接阵) 84 8.3 二分图最大匹配(hungary正向表) 84 8.4二分图最佳匹配(kuhn_munkras邻接阵) 85 8.5 一般图匹配(邻接表) 86 8.6 一般图匹配(邻接阵)...
2. 二分图最大匹配(hungary邻接表形式,邻接阵接口) 10 3. 二分图最大匹配(hungary邻接阵形式) 10 4. 二分图最大匹配(hungary正向表形式) 11 5. 二分图最佳匹配(kuhn_munkras邻接阵形式) 11 6. 一般图匹配(邻接表...
8.1 二分图最大匹配(hungary邻接表) 83 8.2 二分图最大匹配(hungary邻接阵) 84 8.3 二分图最大匹配(hungary正向表) 84 8.4二分图最佳匹配(kuhn_munkras邻接阵) 85 8.5 一般图匹配(邻接表) 86 8.6 一般图匹配(邻接阵)...
2. 二分图最大匹配(hungary 邻接表形式,邻接阵接口) ...... 10 3. 二分图最大匹配(hungary 邻接阵形式) ... 10 4. 二分图最大匹配(hungary 正向表形式) ... 11 5. 二分图最佳匹配(kuhn_munkras 邻接阵形式) .. 11 6....
ACM-ICPC要求的知识点 ACM/ICPC要求的知识点 排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间...指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示)
2. 二分图最大匹配(hungary邻接表形式,邻接阵接口) 10 3. 二分图最大匹配(hungary邻接阵形式) 10 4. 二分图最大匹配(hungary正向表形式) 11 5. 二分图最佳匹配(kuhn_munkras邻接阵形式) 11 6. 一般图匹配(邻接表形式...
2. 二分图最大匹配(hungary邻接表形式,邻接阵接口) 10 3. 二分图最大匹配(hungary邻接阵形式) 10 4. 二分图最大匹配(hungary正向表形式) 11 5. 二分图最佳匹配(kuhn_munkras邻接阵形式) 11 6. 一般图匹配(邻接表形式...
完整版的浙江大学ACM模板,PDF原版,很好用的
2. 二分图最大匹配(hungary邻接表形式,邻接阵接口) 10 3. 二分图最大匹配(hungary邻接阵形式) 10 4. 二分图最大匹配(hungary正向表形式) 11 5. 二分图最佳匹配(kuhn_munkras邻接阵形式) 11 6. 一般图匹配(邻接表形式...
指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示) 按位运算(and,or,xor,shl,shr,一些应用) 图论(图论模型的建立,平面图,欧拉公式与五色定理,求强连通分量,求割点和桥,欧拉回路...
1 7.1 图的基本概念 图的定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构: Graph=( V, E ) 其中 V = { x " x 某个数据对象} 是顶点的有穷... 12 7.2.2 邻接表 (Adjacency List) 1) 存储特点 对于
代码可能涉及图的表示(邻接矩阵/邻接表)、遍历(DFS/BFS)、最短路径(Dijkstra/Floyd-Warshall)等算法。 字符串:处理文本数据的重要工具。代码可能包括字符串匹配(KMP/Boyer-Moore)、编辑距离、后缀数组等...
例如,数组的连续存储,链表的动态分配节点,树和图的邻接矩阵或邻接表表示等。 基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和...
本书第1章介绍图论基本概念和图的两种存储表示方法:邻接矩阵和邻接表,第2~9章分别讨论图的遍历与活动网络,树与生成树问题,最短路径问题,可行遍性问题,网络流问题,点支配集、点覆盖集、点独立集、边覆盖集、...
图路径问题及及生成树课件,有由多年带领ACM校队的老师讲授,对于图路径问题及及生成树问题讲得十分透彻,十分适合入门。
例如,数组的连续存储,链表的动态分配节点,树和图的邻接矩阵或邻接表表示等。 基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和...