试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。

题目
试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。

相似考题

1.● 拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点 vi 必然在顶点 vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定 （57）（57）A. 包含回路B. 是强连通图C. 是完全图D. 是有向树

2.采用邻接表存储结构,编写一个算法,判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。

3.拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点 vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定(57)。A．包含回路B．是强连通图C．是完全图D．是有向树

4.阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。[说明]邻接表是图的一种顺序存储与链式存储结合的存储方法。其思想是：对于图G中的每个顶点 vi，将所有邻接于vi的顶点vj连成一个单链表，这个单链表就称为顶点vi的邻接表，其中表头称作顶点表结点VertexNode，其余结点称作边表结点EdgeNode。将所有的顶点表结点放到数组中，就构成了图的邻接表AdjList。邻接表表示的形式描述如下： define MaxVerNum 100 /*最大顶点数为100*/typedef struct node{ /*边表结点*/int adjvex; /*邻接点域*/struct node *next; /*指向下一个边表结点的指针域*/ }EdgeNode;typedef struct vnode{ /*顶点表结点*/int vertex; /*顶点域*/EdgeNode *firstedge; /*边表头指针*/}VertexNode;typedef VertexNode AdjList[MaxVerNum]; /*AdjList是邻接表类型*/typedef struct{AdjList adjlist; /*邻接表*/int n; /*顶点数*/}ALGraph; /*ALGraph是以邻接表方式存储的图类型*/深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。下面的函数利用递归算法，对以邻接表形式存储的图进行深度优先搜索：设初始状态是图中所有顶点未曾被访问，算法从某顶点v出发，访问此顶点，然后依次从v的邻接点出发进行搜索，直至所有与v相连的顶点都被访问；若图中尚有顶点未被访问，则选取这样的一个点作起始点，重复上述过程，直至对图的搜索完成。程序中的整型数组visited[]的作用是标记顶点i是否已被访问。[函数]void DFSTraverseAL(ALGraph *G)/*深度优先搜索以邻接表存储的图G*/{ int i;for(i=0;i＜(1);i++) visited[i]=0;for(i=0;i＜(1);i++)if((2)) DFSAL(G,i);}void DFSAL(ALGraph *G,int i) /*从Vi出发对邻接表存储的图G进行搜索*/{ EdgeNode *p;(3);p=(4);while(p!=NULL) /*依次搜索Vi的邻接点Vj*/{ if(! visited[(5)]) DFSAL(G,(5));p=p-＞next; /*找Vi的下一个邻接点*/}}

更多“试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。 ”相关问题

  • 第1题：

    在一个有向图G的拓扑序列中,顶点Vi排列在Vj之前,说明图G中(59)。A.一定存在弧B.

    在一个有向图G的拓扑序列中，顶点Vi排列在Vj之前，说明图G中（59）。

    A.一定存在弧＜vi,vj＞

    B.一定存在弧＜vj,vi＞

    C.可能存在vi到vj的路径，而不可能存在vj到vi的路径

    D.可能存在vj到vi的路径，而不可能存在vi到vj的路径


    正确答案：C
    拓扑序列是拓扑排序的产出物。对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。由此可见，如果Vi排列在Vj之前，说明可能存在vi到vj的路径，而不可能存在vj到vi的路径。

  • 第2题：

    用邻接矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度m路径相连，则只要检查()的第i行和第j列的元素是否为零即可。

    A.mA
    B.A
    C.Am
    D.Am-1

    答案：C
    解析：
    要判断相邻矩阵A中任意两个顶点Vi和Vj之间是否有长度为m的路径相连，只要检查Am的第i行第j的元素是否为0即可，若为0则无，否则就存在。

  • 第3题：

    对n个顶点的有向图G，采用邻接表存储，请回答下列有关问题： （1）如何求图中的边数？ （2）如何判断顶点i到顶点j是否有边相连？ （3）如何求任意一个顶点i的入度？


    ( 1 )累加每个边单链表中的节点个数即为边数。 ( 2 )判断第 i 个边单链表中是否有顶点 j 的节点,若有表示顶点 i 到顶点 j 有边,否则没有边。 ( 3 )扫描所有边单链表,累加顶点 i 的节点个数即为顶点 i 的入度。

  • 第4题：

    拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定(57)。

    A．包含回路

    B．是完全图

    C．是有向树

    D．是强连通图


    正确答案：A
    解析：本题考查图数据结构。对有向图进行拓扑排序的方法如下：①在AOV网中选择一个入度为0(没有前驱)的顶点且输出它；②从网中删除该顶点及其与该顶点有关的所有边；③重复上述两步，直至网中不存在入度为0的顶点为止。

  • 第5题：

    在有向图G 的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）

    A．G中有一条Vj到Vi的路径

    B．G中有一条从Vi到Vj的路径

    C．G中没有边＜Vi,Vj＞

    D．G中有边＜Vi,Vj＞


    图G中有一条从vj到vi的路径

相关内容