知识卡片
邻接查询返回图内借用视图
graph_adjlist(const Graph,const void,AdjList**)按顶点查找并交回图内AdjList地址,成功0、失败-1;它不是复制。graph_adjlists实际宏返回&graph->adjlists,即List*,与接口图写List返回值不同,遍历时不能任意改动底层链破坏图状态。
graph_is_adjacent(const Graph,const void,const void*)回答第二顶点是否在第一顶点的出邻居集合中,1真0假;它不是任意路径可达查询。graph_vcount/ecount读取维护计数,字段访问O(1),而按顶点定位邻接记录要在链中扫描,最坏O(|V|)。
这些返回地址只在相关图结构/数据保持有效时可使用,查询成功没有交接销毁权,也不提供并发修改保护。
196及02937 graph_adjlist按match命中后*adjlist=list_data(element),不是结构体复制。最坏O(V),额外声明/更新的prev并不参与结果;不因局部字段返回而误判整个定位常数时间。
197与02938 graph_is_adjacent实际查询方向是data1→data2,尽管正文首句表述易倒置。源不存在return0,否则返回set_is_member;未逐层搜索可达路径。外层扫描与目标集合扫描的总上界O(V),假定普通无重复邻接/常数判等。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 3 处
- · 查看原书依据
graph_adjlist 返回值 如果取得邻接表成功,返回0;否则返回-1。 描述 取出graph中由data所指定的顶点的邻接表。返回的邻接表以结构体AdjList的形式保存,该结构体包含与data相匹配的顶点,以及其他与其邻接的顶点。函数返回后得到一个指向邻接表的指针,因此调用者必须保证不修改
- · 查看原书依据
检索邻接表结构链表,直到找到其中包含指定顶点的那个AdjList结构体。 graph_adjlist操作的时间复杂度为O(V),这里V代表图中顶点的个数。这是因为检索邻接表结构链表是复杂度为O(V)的操作。
- · 查看原书依据
data2是否在data1的邻接表中。 graph_is_adjacent的时间复杂度为O(V),这里V代表图中顶点的个数。这是因为检索邻接表结构链表以及对set_is_member的调用都是复杂度为O(V)的操作。