分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: ① 增加一个新顶点v,InsertVex(G, v); ② 删除顶点v及其相关的边,DeleteVex(G, v); ③ 增加一条边,InsertArc(G, v, w); ④ 删除一条边,DeleteArc(G, v, w)。

题目
分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: ① 增加一个新顶点v,InsertVex(G, v); ② 删除顶点v及其相关的边,DeleteVex(G, v); ③ 增加一条边,InsertArc(G, v, w); ④ 删除一条边,DeleteArc(G, v, w)。

相似考题

1.阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点v出发进行广度优先遍历的过程是： ①访问顶点v； ②访问V的所有未被访问的邻接顶点W1 ,W2 ,..,Wk； ③依次从这些邻接顶点W1 ,W2 ,..,Wk出发，访问其所有未被访问的邻接顶点；依此类推，直到图中所有访问过的顶点的邻接顶点都得到访问。 显然，上述过程可以访问到从顶点V出发且有路径可达的所有顶点。对于从v出发不可达的顶点u，可从顶点u出发再次重复以上过程,直到图中所有顶点都被访问到。 例如，对于图4-1所示的有向图G，从a出发进行广度优先遍历，访问顶点的一种顺序为a、b、c、e、f、d。设图G采用数组表示法（即用邻接矩阵arcs存储），元素arcs[i][j]定义如下：图4-1的邻接矩阵如图4-2所示，顶点a~f对应的编号依次为0~5.因此，访问顶点a的邻接顶点的顺序为b，c，e。 函数BFSTraverse(Graph G)利用队列实现图G的广度优先遍历。 相关的符号和类型定义如下： define MaxN 50 ／*图中最多顶点数*／ typedef int AdjMatrix[MaxN][MaxN]； typedef struct{ int vexnum, edgenum; ／*图中实际顶点数和边（弧）数*／ AdjMatrix arcs; ／*邻接矩阵*／ )Graph; typedef int QElemType； enum {ERROR=0;OK=1}; 代码中用到的队列运算的函数原型如表4-1所述，队列类型名为QUEUE。 表4-1 实现队列运算的函数原型及说明【代码】 int BFSTraverse(Graph G) {//对图G进行广度优先遍历，图采用邻接矩阵存储 unsigned char*visited； //visited[]用于存储图G中各顶点的访问标志，0表示未访问 int v, w, u; QUEUEQ Q; ∥申请存储顶点访问标志的空间，成功时将所申请空间初始化为0 visited=(char*)calloc(G.vexnum, sizeof(char)); If( （1） ) retum ERROR; （2） ； //初始化Q为空队列 for( v=0; v<G.vexnum; v++){ if(!visited[v]){ //从顶点v出发进行广度优先遍历 printf("%d&rdquo;，v)； //访问顶点v并将其加入队列 visited[v]=1； （3） ； while(！isEmpty(Q)){ （4） ； //出队列并用u表示出队的元素 for(w=0;v<G.vexnum; w++){ if（G.arcs[u][w]!=0&& （5） ){ //w是u的邻接顶点且未访问过 printf("%d&rdquo;, w)； //访问顶点w visited[w]=1； EnQueue(&Q, w); } } } } free(visited); return OK; )//BFSTraverse

2.如果顶点v到顶点w之间存在一条路径，则称v和w是邻接的。

3.13、在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（）。A．顶点v的入度B．顶点v的度C．顶点v的出度D．依附于顶点v的边数

4.图G的邻接矩阵如下图所示（顶点依次表示为v0、v1、v2、v3、v4、v5），G是（请作答此空）。对G进行广度优先遍历（从v0开始），可能的遍历序列为（ ）。A.无向图 B.有向图 C.完全图 D.强连通图

更多“分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: ① 增加一个新顶点v,InsertVex(G, v); ② 删除顶点v及其相关的边,DeleteVex(G, v); ③ 增加一条边,InsertArc(G, v, w); ④ 删除一条边,DeleteArc(G, v, w)。 ”相关问题

  • 第1题：

    在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（）。

    A．顶点v的入度

    B．顶点v的度

    C．顶点v的出度

    D．依附于顶点v的边数


    C

  • 第2题：

    设G = ＜V, E＞中无孤立点。M为G的最大匹配, 对于G中每个未覆盖顶点v, 选取与v关联的边组成集合N,则MÈN是G的最小边覆盖。


    错误

  • 第3题：

    给定G = ＜V, E＞, G的匹配中任何两条边都没有公共顶点。


    B

  • 第4题：

    26、网络N=（V, E, W）中V指所有的顶点，E指所有的边，W指所有的边的权值.


    pagerequestsessionapplication

  • 第5题：

    11、设图G的顶点集合为V，数量为|V|，边的集合为E，数量为|E|，以下说法不正确的是（）。

    A．若用十字链表储存的有向图G，共需要|V|+2|E|个指针。

    B．使用邻接表作为G的储存结构，深度优先搜索的时间复杂度为O(V|+|E|)。

    C．如果其邻接矩阵只存储了顶点的出边，则查询一个顶点的度的时间复杂度为O(V|^2 )。

    D．使用邻接表作为G的储存结构，广度优先搜索的时间复杂度为O(V|+|E|)。


    若用十字链表储存的有向图G，共需要|V|+2|E|个指针。;如果其邻接矩阵只存储了顶点的出边，则查询一个顶点的度的时间复杂度为O(|V|^2 )。

相关内容