精华内容
下载资源
问答
  • 深度优先遍历与广度优先遍历(邻接数组和邻接版)
    2021-12-21 15:24:58

        关于深度优先遍历 其实可以对照树的前序遍历去理解,就是从给定的节点开始,一直朝它的临边(叶子)向下检索,等到它所联通的最后一个遍历完,再一层一层的遍历回来。这是一个递归的过程,当然也可以用非递归的方法来完成(栈与队列)。其实这也是递归的本质。深度优先遍历就是顺着一个点一直找到最下面一个再找下一个点。

        我们知道一个图可以用邻接表或者邻接矩阵表示 他们都有相应的深度广度遍历

         首先是邻接矩阵的深度优先遍历

         递归方法:

    public class test {
        void dfs(Graph G,int i){                    //递归方法
            visited[i]=true;//判断是否访问过
        sout(G.getvex[i]);
        for(intj=0;j<G.numVertexes;j++){
            if (G.arc[i][j]==1&&!visited[j]){        //找到邻接点且邻接点没被访问过就继续df
                dfs(G,j);                             //s这个点
            }
        }
        void makedfs(){
            for (int a=0;a<G.numVertexes;i++){             //先把visited数组都重置成未被访问
                visited[a]=false;
            }
            for (int a=0;a<G.numVertexes;a++){           //每个点依次dfs
                if (visited[a]==false)
                    dfs(G,a);
            }
            }
    }

    而邻接表的dfs:

    void DFS(Graph G,int i){

    ListNode p=new ListNode(0);

    visited[i]=true;

    sout(G.getvex[i])//遍历到了该节点

    p=verlist[i];       //在顶点列表里找到i节点

    while(p.next!=null){//有邻接节点
    if(!visited[p.next.val]) //邻接节点没有被访问过

    DfS(G,p.next.val);//递归

    p=p.next;

    }

    }

    void makeDFS(){

    //省略了重置visited

    for(int i=0;i<G.numVertexes;i++){
    if(!visited[i])

    GFS(G,i);

    }

    }

    而广度遍历可以类比一下树的层序遍历 一层一层的找,找完一个点的所以邻接点再找下一个点的所有临接点。

    首先是邻接数组的BFS,在书中是写了一个大的for遍历每一个点,然后在其中每一个点进行一个while,while里面是BFS的操作 我认为这个看起来就很难理解(for里套while再套for)所以还是可以按照两个函数写

    public void bfs(boolean[] isVisited,int i ){

        int u;//表示队列头节点的下标
        int w;//表示邻接节点的下标
        //需要一个队列记录访问的顺序
        LinkedList queue = new LinkedList();

        //访问节点,输出节点信息
        System.out.print(getValueByIndex(i) + " ->");
        isVisited[i] = true;

        //将节点加入队列,记录访问顺序
        //队列尾部添加,头部取
        queue.addLast(i);

        while (!queue.isEmpty()){
            //取出队列的头结点,删掉
            u = (Integer) queue.removeFirst();

            //查找头结点u的邻接节点
            w = getFirstNeighbor(u);

            //w != -1 代表找到邻接节点(getfirstneighbor的返回值)
            while(w!= -1 ){
                //判断是否访问过
                if(!isVisited[w]){
                    //若没有访问过,则输出并标记已访问
                    System.out.print(getValueByIndex(i) + " ->");
                    isVisited[w] = true;
                    //将节点入队列,代表访问过
                    queue.addLast(w);
                }
                //以u为起点,查找w邻接结点的下一个邻接结点
                w = getNextNeighbor(u,w);
            }
        }
    }
    至于查找第一个邻接点和下一个邻接点是两个自己封装好的函数

    然后用bfs函数就好啦

    public void bfs(){
        for(int j=0; j< getNumOfVertex(); j++){
            //没有被访问过才进行广度优先搜索
             if(!isVisited[j]){
                bfs(isVisited,j);
             }
        }
    }
    下面是邻接表的广度优先遍历,代码块没什么差别(等我先肝个作业回来补)

    void BFS2(Graph G,int i){

    visited[i]=true;

    sout(vexlist[i].val);

    queue.addLast(vexlist[i]);

    while(!queue.isEmpty()){

    ListNode u=queue.removeFirst();

    ListNode p=vexlist[u];

    while(p.next!=null){

    if(!visited[p.next.val]){

    visited[p.next.val]=true;

    sout (p.next.val);

    queue.addLast(p.next);

    }

    p=p.next;

    }

    }

    }

    }

    然后就是调用函数

    void makeBFS2(){

    //省略visited的重置

    for(int i=0;i<getNumOfVertex();i++){

    if(!visited[i]){

    LinkedList queue = new LinkedList();

    BFS2(G,i);}}

    总算肝完了 其实邻接数组的广度也可以不用那个什么getfirstneighbor之类的,只需要套再一个for里面就行 按顺序找,找到进入while 结束后再找下一个 。这个看起来更直观一点 以后用这个就行 写俩函数简单写 最后代码看起来简单些 不是特别乱

    更多相关内容
  • 算符优先算法中优先函数的构造

    千次阅读 多人点赞 2020-11-04 10:29:09
    算符优先分析中“优先函数的简单构造!”


            这里我介绍的是一种简单的方法,不是书本的那个方法。是我后面那个参考资料上面的作者想出来的。因为这个是在知网上面找到的,是1997年的一篇文章。我就是一个总结,然后画几个比较清楚的图而已(因为从知网上下载的的pdf上面的图有点不太清楚)

    优先函数树形构造法

            我们教材上面的就是陈火旺老师的那本,然后方法就是找节点。这个方法虽然简单,但是操作起来的却有些麻烦,因为我们作图的时候,难免就会看不清楚,或者数错。下面介绍的树形构造法就可以避免这个问题,仅仅只需要根据优先矩阵就可以得出正确结果。

    操作步骤

    对于一个优先表先做如下几个步骤(假设优先函数存在)
    1 ) 对于f(a)对应行中“a>=b 的所有终结符b , 把g(b)作为f(a) 的子树。
    2) 对g(a) 对应列中有b <=a 的. 把f(a) 作为g(b)的子树.
    3 ) 对f(a)重做第( 1 ) 步, 对g(b) 重做第( 2 ) 步。
    4) 重复出现的f或g , 作记号不再对其执行第( 1) , ( 2) 步
    方向图
    5) 构造f(a)函数时, 以f(a) 为根结点, 按( 1 ) ,(2 ),( 3),( 4) 执行.
    6) 构造g(b)函数时, 以g(b) 为根结点, 按(2 ) ,( 1 ) , ( 3 ) , ( 4 ) 执行.
    按照以上5步先画出树,然后查树的节点数(包括根节点,做记号的不查),即可以得到根节点的优先函数值。
    但是我觉得这个操作步骤2有点问题。应该是b>=a的时候,就把f(a)作为g(b)的子树。我也自己做了实验,发现这样做才是正确的。不过也可能是我没有理解原作者的意思。反正,就目前看来,我都是按照如果b<=a,就把f(a)作为g(b)的子树。
    所以,下面我举例的例子,第(2)步都是按照“b>=a的时候,就把f(a)作为g(b)的子树”这个来做的。

    举例操作

            假如现有一个优先矩阵是这样的:这个例子是《编译原理》陈火旺老师(下面我说的教材,没有特别说明也是指的这本教材)那本书上面的。在90页。
    在这里插入图片描述
    那么我们现在用树形构造法来试试怎么得到这个优先函数。因为最后的答案是去掉了 i 和 # 之后得到的,所以我下面也将不会考虑 i 和 # 号。至于为什么不考虑 i 和 #,,就是因为这两个不是算符,我们算符优先函数主要针对的就是算符直接的优先级。但是优先关系矩阵中是给出了 i 和 # 与其他算符之间的优先关系的。我这里其实是有一个疑问的:因为在优先函数这里没有 i 的优先关系,那么在使用优先函数来分析一个句子是不是这个文法定义的合法的句子的时候,那么什么时候该移进这个 i 呢?希望知道的小伙伴可以在下面留言,我们讨论一下。

            计算f(+)的优先函数值。

    1. 从优先矩阵中可以得到:’+‘ >= 的算符有;’+’,’)’,’#'三个。因为不考虑i 和 #(下面就不提醒这一点了),所以f(+)的孩子节点有两个,分别是g(+)和g()),如下图所示。
      在这里插入图片描述
    2. 现在就来找g(’+’) 的子树。我这里还是采用的是如果b>=a,就把f(a)作为g(b)的子树。从优先表中可以看到的就是’+‘ >= 的算符有:’(’。注意,我这里说的’+‘是g(’+‘),也就是从’+‘那一列中寻找。在这里插入图片描述
      所以,g(’+’)的子树就是f(’(’);在这里插入图片描述
    3. 然后找到g(’)’) >=的算符:在这里插入图片描述
      但是f(’(’)已经出现过了(作为g(’+’)子树出现的),所以就不用画出来了。
    4. 然后就是寻找f(’(’) >=的算符。在这里插入图片描述但是g(’)’)也已经出现过了,所以这里也不用画出来了。
    5. 最后每一个节点我们都已经检查过了,没有可以重新添加的了。也就是趋于稳定了(编译原理里面好多都是这样子的,得使所有都不再变化的时候,算法就算结束了)。我们数一下节点的个数,就是4个,和书本95页给出的答案是一样的。

            同理,g(’+’)的树也可以这样画出来。我就给出最后的树,就不一一分析了。
    在这里插入图片描述

    自己的思考

            本质上书本上的画图和这里的画一颗树,都是优先级高的指向优先级低的,所以入度为0的节点,给的优先函数值应大一点,出度为0的,给出的优先函数值应该小一点。

            上面提到的这个简单的方法其本质善和我们教材上的方法是一样的。你可以将教材上的方法中的图给截取一部分出来。例如,你截取以g(’+’)作为顶点的树去看,发现就是和我上面画的一样。

            还有注意的一点就是:我们求出一组优先函数之后,就可以构造出无数组优先函数。所以,如果你求出来的和参考答案给出的不是一样的,也不一定是你错了。只要你的优先函数之间的关系和参考答案上给出的关系是一样的就可以了。

    参考资料

    构造优先函数的更简单方法_树型构造_潘群娜
    这个知网上我找到的一篇关于这个优先函数构造比较简单的方法,如果大家对上面的博客解释的不太清楚的话,可以去知网上看这个原作者写的文章。

    展开全文
  • c++优先队列(自定义比较函数)方式一:struct重载运算符() 方式二:class重载运算符() 方式三:定义函数 方式四:lambda表达式 方式五:function包装lambda表达式 可以使用现成的 less<T>来定义大顶堆 ...

    在这里插入图片描述
    可以使用现成的
    less<T>来定义大顶堆
    greater<T>来定义小顶堆

    从文档出可以看到,传入的可以是 函数指针或者 函数对象(类对操作符()进行了重载,)

    参考链接:函数指针和函数对象
    参考链接:decltype

    方式一:struct重载运算符()

    通过struct重载()操作符,定义了一个函数对象

    struct cmp{
       bool operator()(vector<int>&a,vector<int>&b){
           return a[0]>b[0]; 
       }
    };
    priority_queue<vector<int>,vector<vector<int>>,cmp> q;//小顶堆
    

    这是属于传入 函数对象 的方式

    方式二:class重载运算符()

    通过class重载()操作符,定义了一个函数对象
    注意要加public

    class cmp{
    public:
        bool operator()(vector<int>&a,vector<int>&b){
            return a[0]>b[0]; 
        }
    };
    priority_queue<vector<int>,vector<vector<int>>,cmp> q;//小顶堆
    

    这是属于传入 函数对象 的方式

    方式三:定义函数

    首先定义一个比较函数

    bool cmp(vector<int>&a,vector<int>&b){
    	return a[0]>b[0];
    }
    

    decltype()是用于获得函数指针的 类型的。在模板中也要传入它们的类型。
    decltype()要传入的是一个对象的地址,因此需要对cmp加取值符,&cmp为对象的地址
    在这里插入图片描述
    因此可以由函数地址cmp 转为函数指针 类型 decltype(&cmp)

    priority_queue<vector<int>,vector<vector<int>>,decltype(&cmp)> q(cmp);//小顶堆
    

    写法一:
    在这里插入图片描述
    写法二:
    如果作为类成员函数,一定要声明static
    在这里插入图片描述

    这是属于传入 函数指针的方式。

    方式四:lambda表达式

    auto cmp=[](vector<int>&a,vector<int>&b)->bool{
                return a[0]>b[0];
            };
    priority_queue<vector<int>,vector<vector<int>>,decltype(cmp)> q(cmp);//小顶堆
    

    这是属于传入 函数指针的方式。

    方式五:function包装lambda表达式

    要加入头文件#include<functional>

    由于function对lambda函数进行了包装 ,cmp本身就是一个对象地址。(function对象)
    直接decltype(cmp)获得函数指针 的类型。

    function<bool(vector<int>&,vector<int>&)> cmp=[](vector<int>&a,vector<int>&b)->bool{
                return a[0]>b[0];
            };
    priority_queue<vector<int>,vector<vector<int>>,decltype(cmp)> q(cmp);//小顶堆
    

    这是属于传入 函数指针的方式。

    测试用例

    #include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    
    int main(){
        auto cmp=[](vector<int>&a,vector<int>&b)->bool{
                return a[0]>b[0];
            };
        priority_queue<vector<int>,vector<vector<int>>,decltype(cmp)> q(cmp);//小顶堆
    
        
        q.push({3,4});
        q.push({1,2});
        q.push({5,6});
        vector<int> vec=q.top();
        q.pop();
    
        cout<<vec[0]<<endl;
        cout<<vec[1]<<endl;
    
        system("pause");
        return 0;
    }
    

    输出结果
    在这里插入图片描述

    展开全文
  • 构造优先关系

    2022-04-16 20:22:38
    在自底向下优先分析一章中有一个非常重要的题型——构造优先关系,接下来我们就来看看具体是怎么操作的。注意:进行这一步的前提是要知道FIRSTVT和LASTVT的求法,大家可以看我之前写的博客:FIRSTVT和LASTVT的计算...

    在自底向下优先分析一章中有一个非常重要的题型——构造优先关系表,接下来我们就来看看具体是怎么操作的。注意:进行这一步的前提是要知道FIRSTVT和LASTVT的求法,大家可以看我之前写的博客:FIRSTVT和LASTVT的计算(很长但是很详细)_驼驼学编程的博客-CSDN博客

    1.基本概念

    大家可能不太好理解,我们把它转化成伪代码的形式供同学们理解。

    2.伪代码呈现 

    大伙可能看的还是云里雾里,我来和大家解释一下。

    给大家举一个例子:P->ABC

    我们来看ABC三者的关系,

    (1)如果A和C是终结符,B是非终结符,那么A=C 

    (2)如果A和B都是终结符,A=B

    (3)如果A是终结符并且B不是终结符,对于FIRSTVT(B)中的每个元素都>A

    (4)如果A是非终结符并且B是终结符,对于LASTVT(A)中的每个元素都>B

    3.例题演示 

    我们已经求得了FIRSTVT和LASTVT

    (1)列表:

    左边的终结符为横坐标,右边的终结符为纵坐标

    (2)求出对应关系并填表: 

    1.E->E+T|T

    对于 E->E+T,我们可以看出‘E+’这个形式符合非终结符+终结符,根据上面的(4),我们可以知道LASTVT(E)的每个元素优先级>+。

    我们接着来分析这个式子,'+E'这个形式符合终结符+非终结符,根据上面的 (3),我们可以知道FIRSTVT(E)的优先级<+。

    我们再看E->T,不符合上面的结论,跳过。

    2.T->T*F|F

    推导过程与第一个推导式基本一模一样,只给出推导结果。 

      

    3.F->P↑F|P

    推导过程与第一个推导式基本一模一样,只给出推导结果。

    4.P->(E)|i

    这一步与前几步有点不同,我来带大家推导一遍。

    ’(E)‘可以通过观察可知符合终结符+非终结符+终结符,故符合上面的(1),(=)。

    ’(E‘与’E)’的推导与上面的过程是一样的。

     5.#E#

    大家不要忘了这个隐藏的步骤,推导过程与(4)是一样的。

    (3)判断是否为算符优先文法 

    表里无冲突项,是算符优先文法。

    附:算符优先文法:

    假定G GG是一个不含ϵ \epsilonϵ-产生式的算符文法,对于任何一对终结符a , b a,ba,b,我们说:

    a = b a = ba=b,当且仅当文法G GG中含有形如P → … a b … P \rightarrow \dots ab \dotsP→…ab…或P → … a Q b … P \rightarrow \dots aQb \dotsP→…aQb…的产生式;
    a < b a < ba<b,当且仅当G GG中含有形如P → … a R … P \rightarrow \dots aR \dotsP→…aR…的产生式,而R ⇒ b … R \Rightarrow b\dotsR⇒b…或R ⇒ Q b … R \Rightarrow Qb\dotsR⇒Qb…;
    a > b a > ba>b,当且仅当G GG中含有形如P → … R b … P \rightarrow \dots Rb \dotsP→…Rb…的产生式,而R ⇒ … a R \Rightarrow \dots aR⇒…a或R ⇒ … a Q R \Rightarrow \dots aQR⇒…aQ;
    如果一个算符文法G GG中的任何终结符对( a , b ) (a,b)(a,b)至多只满足a = b 、 a < b 、 a > b a = b、a < b、a > ba=b、a<b、a>b这三个关系之一,则称G GG是一个算符优先文法。
     

    展开全文
  • 问题 首先:普遍认为函数声明提升优于变量提升 但为什么下面的结果是这样的呢(第一个...解释:肯定是函数声明优先,但最后的结果要看谁最后赋值 函数声明先赋值,变量声明执行到赋值语句才赋值 因为两种声明方式共同
  • 以邻接为存储结构,实现创建图、销毁图、查找顶点、获取顶点值、顶点赋值、获得第一邻接点、获得下一邻接点、插入顶点、删除顶点、插入弧、删除弧、深度优先搜索遍历、广深度优先搜索遍历等操作 注: 1.系统设计 2...
  • 有些STL 容器提供了一些与算法同名的成员函数。大多数情况下,应该使用这些成员函数,而不是相应的STL算法。 有两个理由: 成员函数往往速度快。 成员函数通常与容器结合地更紧密,这是算法所不能比的。 set容器的...
  • 邻接—广度优先遍历

    千次阅读 2020-12-15 20:46:29
    下面是使用邻接做出的广度优先遍历案例: #include<stdlib.h> #include<stdio.h> #include<malloc.h> #include<string.h> //图的邻接类型定义 typedef char VertexType[4]; typedef ...
  • “Scala可组合的Future类型可用于将微服务调用缝合在一起,并且它的一些缺点可以通过Cats(一个Scala库,可提供支持类型化、函数式编程样式的抽象化)得到解决。”本教程概述了Scala强大的类型系统及函数式编程功能...
  • 算符优先系列之(二)算符优先关系

    千次阅读 2018-11-27 17:14:49
    已知文法G[S]的表达式,求算符优先关系。因为某些特殊的原因,我们在这规定一下输入输出格式。 已知文法G[S]为: S`-&gt;#S#(拓展文法,不是题目给出的文法) S-&gt;a|@|(T) T-&gt;T,S|S 表达式...
  • 深度优先搜索(DFS)与广度优先搜索(BFS)详解 1.广度优先搜索算法 1.1.前言 和树的遍历类似,图的遍历也是从图中某点出发,然后按照某种方法对图中所有顶点进行访问,且仅访问一次。 但是图的遍历相对树而言要更为...
  • 数据结构实现 6.4:优先队列_基于链表实现(C++版)1. 概念及基本框架2. 基本操作程序实现2.1 入队操作2.2 出队操作2.3 查找操作2.4 其他操作3. 算法复杂度分析3.1 入队操作3.2 出队操作3.3 查找操作4. 完整代码 1. ...
  • 建立一个有向图或无向图,输入其顶点数,边数,并给出相应边的权值,输出该图对应的邻接矩阵,并用递归实现其深度优先遍历和用队列实现其广度优先遍历后的结果. 图的遍历 从给定图中任意指定的顶点(称为初始点)...
  • 无向图-邻接链表的深度优先遍历-DFS

    千次阅读 2018-02-20 21:05:27
    一、DFS思想本算法以无向网为例,存储方式采用邻接链表1)将该网以...深度优先遍历图,直到图中所有和v有路径相通的顶点都被访问到二、算法复杂度:O(n+e) 邻接矩阵和邻接都是实现BFS和DFS的方法,邻接矩阵时间...
  • 函数接口定义: void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ); 其中MGraph是邻接矩阵存储的图,定义如下: typedef struct GNode PtrToGNode; struct GNode{ int Nv; / 顶点数 / int Ne; / ...
  • 一下是使用邻接存储表示,实现图的深度优先遍历的示例。 用于遍历的有向图如下: #include #define MaxVertexNum 6 using namespace std; //抽象数据类型 typedef char vertextype; //边结点类型 typedef struct ...
  • 2.图的存储结构之邻接 3.图的遍历-深度优先搜索遍历DFS:Depth First Search 3.1图的遍历-广度优先搜索遍历BFS:Breadth First Search 3.2深度优先遍历和广度优先遍历实现代码 4.DFS的一应用小例子 注意:图...
  • 练习6.2 邻接存储图的广度优先遍历 (20 point(s)) 试实现邻接存储图的广度优先遍历。 函数接口定义: void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) ); 其中LGraph是邻接存储的图,...
  • 深入理解多态虚函数--虚函数表解析

    千次阅读 2018-02-09 15:02:13
    C++中的虚函数的作用主要是实现了多态的机制。关于多态,简而言之就是用父类型别的指针指向其子类的实例,然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”,这是一种泛型技术。...
  • } } } /** * 从指定顶点vertex开始进行广度优先遍历 * * @param vertex 从vertex顶点开始进行广度优先遍历 */ public void bfs(int vertex) { boolean[] visited = new boolean[numberOfVertex]; Arrays.fill...
  • 【单选题】对一个有n个顶点e条边的图采用邻接表示时,进行BFS遍历的时间复杂度为()【单选题】已知带权连通无向图G=(V, E),其中V={ , , , , , , },E={( , )10, ( , )2, ( , )2, ( , )11, ( , )1, ( , )4, ( , )6, ( ...
  • 深度优先搜索(DFS)与广度优先搜索(BFS)详解

    万次阅读 多人点赞 2020-11-07 18:44:06
    深度优先搜索与宽度优先搜索详解 深度优先搜索(DFS)和宽度优先搜索(BFS)都是常见的搜索算法。在学习DFS和BFS之前,我们首先得知道递归函数的概念。 1. 递归函数 通俗地讲,一个函数自己调用自己的行为就叫递归,...
  • 图的深度优先遍历的基本思想: ...下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A-&g...
  • 操作系统 实验2【动态高优先优先调度算法 C++】
  • 如果优先函数存在,则可以通过以下三个步骤从优先构造优先函数:(1)对于每个终结符a,令其对应两个符号fa和ga,画一张以所有符号fa和ga为结点的方向图。如果a>.b,则从fa画一条弧至gb如果a,则从gb画一条弧至fa 。...
  • 图的广度优先搜索和深度优先搜索

    千次阅读 2020-06-19 12:09:49
    我们知道,算法是作用于具体数据结构之上的,深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构的。这是因为,图这种数据结构的表达能力很强,大部分涉及搜索的场景都可以抽象成“图”。 图上的搜索...
  • 二叉树深度优先遍历解题思路

    多人点赞 热门讨论 2021-12-18 10:14:21
    递归形成条件 我们都理解,深度优先遍历的所使用的编码技巧是递归,而递归有形成的条件有3个: 函数调用自身 有一个终止条件 不断朝终止条件步进 所谓的递归,就是函数不断调用自身的过程,在这个过程中,必须由一个...
  • 深度优先遍历 (1)从图中某个初始顶点v出发,首先访问初始顶点v。 (2)选择一个与顶点v相邻且没被访问过的顶点w,再从w出发进行深度优先搜索,直到图中与当前顶点v邻接的所有顶点都被访问过为止。  (3) 利用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 241,203
精华内容 96,481
关键字:

优先表得到优先函数

友情链接: 栅格法.rar