精华内容
下载资源
问答
  • 2021-11-25 12:34:15

    图的存储结构(邻接矩阵和邻接表)

    前言:

    前面我们学习图的有些定义和术语,对图这个数据结构有了新的见解和认知,让我们理解图结构的知识,今天我们学习图的存储结构,图的存储结构比较多,我们今天主要是学习邻接矩阵和邻接表,对于邻接矩阵是使用数组的形式,我们不叫顺序存储结构了,叫邻接矩阵,邻接表和我们十字链有异曲同工之处,只不过邻接表的链表要多一点,好了话不多说我们开始学习吧!!!

    每日一遍,防止颓废

    image-20211122113601095

    1.邻接矩阵

    官方术语:

    邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图,其中V={v1,v2,…,vn} [1]  。G的邻接矩阵是一个具有下列性质的n阶方阵:
    ①对无向图而言,邻接矩阵一定是对称的,而且主对角线一定为零(在此仅讨论无向简单图),副对角线不一定为0,有向图则不一定如此。
    ②在无向图中,任一顶点i的度为第i列(或第i行)所有非零元素的个数,在有向图中顶点i的出度为第i行所有非零元素的个数,而入度为第i列所有非零元素的个数。
    ③用邻接矩阵法表示图共需要n^2个空间,由于无向图的邻接矩阵一定具有对称关系,所以扣除对角线为零外,仅需要存储上三角形或下三角形的数据即可,因此仅需要n(n-1)/2个空间。
    

    讲人话就是:邻接矩阵和矩阵的三元组表示法有点相似,就是一个顶点,和一个二维数组组合,二维数组的第一个下标表示边的起点,第二下标表示边的终点,有边把这个位置的值赋值为1,没有就赋值为0如下图:.

    image-20211121225924966

    1.1图的邻接矩阵类型声明:

    #include <stdio.h>
    #include <malloc.h>
    #define MAXVEX 100	  		 //图中最大顶点个数
    #define INF 32767				//表示∞
    typedef char VertexType[10]; 		//定义VertexType为字符串类型
    typedef struct vertex
    {  int adjvex; //顶点编号
       VertexType data; 		//顶点的信息
    } VType;		//顶点类型
    typedef struct graph
    {  int n,e;			//n为实际顶点数,e为实际边数
       VType vexs[MAXVEX];		//顶点集合
       int edges[MAXVEX][MAXVEX]; 		//边的集合
    }  MatGraph;		//图的邻接矩阵类型
    

    1.2 建立图的邻接矩阵运算算法

    由邻接矩阵数组A、顶点数n和边数e建立图G的邻接矩阵存储结构。

    void CreateGraph(MatGraph &g,int A[][MAXVEX],int n,int e)
    {  
    	int i,j;
        g.n=n; g.e=e;
        for (i=0;i<n;i++)
        for (j=0;j<n;j++)
        g.edges[i][j]=A[i][j];
    }
    

    1.3销毁图运算算法

    这里邻接矩阵是图的一种顺序存储结构,其内存空间是由系统自动分配的,在不再需要时由系统自动释放其空间。所以对应的函数不含任何语句。

    void DestroyGraph(MatGraph g)//内存空间是由系统自动分配的,直接关闭程序就释放了
    {  }
    

    1.4 输出图运算算法

    将图G的邻接矩阵存储结构输出到屏幕上

    void DispGraph(MatGraph g)
    {  int i,j;
       for (i=0;i<g.n;i++)
       {  for (j=0;j<g.n;j++)
            if (g.edges[i][j]<INF)
               printf("%4d",g.edges[i][j]);
            else
               printf("%4s","∞");
          printf("\n");
       }
    }
    

    1.5求顶点度运算算法

    对于无向图和有向图,求顶点度有所不同。依据定义,求无向图G中顶点v的度的算法如下:

    int Degree1(MatGraph g,int v)	 //求无向图中顶点的度
    {  int i,d=0;
       if (v<0 || v>=g.n)
          return -1;		 //顶点编号错误返回-1
       for (i=0;i<g.n;i++)
          if (g.edges[v][i]>0 && g.edges[v][i]<INF)
    	 d++;		//统计第v行既不为0也不为∞的边数即度
       return d;
    }
    
    int Degree2(MatGraph g,int v)	 //求有向图中顶点的度
    {  int i,d1=0,d2=0,d;
       if (v<0 || v>=g.n)
          return -1;	//顶点编号错误返回-1
       for (i=0;i<g.n;i++)
          if (g.edges[v][i]>0 && g.edges[v][i]<INF)
    	 d1++;		//统计第v行既不为0也不为∞的边数即出度
       for (i=0;i<g.n;i++)
          if (g.edges[i][v]>0 && g.edges[i][v]<INF)
    	 d2++;		//统计第v列既不为0也不为∞的边数即入度
       d=d1+d2;
       return d;
    }
    
    

    1.6 主函数及效果展示

    int main(int argc, char** argv)
    {
    	MatGraph g;
    	int n=5,e=7,i;
    	int A[MAXVEX][MAXVEX]={{0,1,2,6,INF},{INF,0,INF,4,5},{INF,INF,0,INF,3},{INF,INF,INF,0,INF},{INF,INF,INF,7,0}};
    	CreateGraph(g,A,n,e);	//建立图7.4图的邻接矩阵
    	printf("图G的存储结构:\n"); DispGraph(g);
    	printf("图G中所有顶点的度:\n"); 
    	printf("  顶点\t度\n");
    	for (i=0;i<g.n;i++)
    		printf("   %d\t%d\n",i,Degree2(g,i));
    	DestroyGraph(g);
    	return 0;
    }
    

    image-20211122111847765

    2.邻接表

    邻接表是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个带头结点的单链表,把该顶点的所有相邻点串起来。所有的头结点构成一个数组,称为头结点数组,用adjlist表示,第i个单链表adjlist[i]中的结点表示依附于顶点i的边,也就是说头结点数组元素的下标与顶点编号一致。
    

    讲人话:就是有一个数组类型的单链表,这个数组的每个结点都代表一个头指针,这个头指针再指向一个单链表,这个单链表用来保存下一个你要指向的顶点(也就是头指针)和权值,对权值不知道的同学看博主上一篇文章

    image-20211121234839848

    2.1图的邻接表存储结构的类型声明如下:

    #include <stdio.h>
    #include <malloc.h>
    #define MAXVEX 100				//图中最大顶点个数
    #define INF 32767				//表示∞
    typedef char VertexType[10];	  //VertexType为字符串类型
    typedef struct edgenode
    {  int adjvex;			  //相邻点序号
       int weight;			  //边的权值
       struct edgenode *nextarc;	  //下一条边的顶点
    } ArcNode;		//每个顶点建立的单链表中边结点的类型
    typedef struct vexnode
    {  VertexType data;		  //存放一个顶点的信息
       ArcNode *firstarc; 	  //指向第一条边结点
    } VHeadNode;			  //单链表的头结点类型
    typedef struct 
    {  int n,e;			  //n为实际顶点数,e为实际边数
       VHeadNode adjlist[MAXVEX];	  //单链表头结点数组
    } AdjGraph;			  //图的邻接表类型
    
    

    2.2 邻接表的创建

    image-20211122110615126

    void CreateGraph(AdjGraph *&G,int A[][MAXVEX],int n,int e)
    {  int i,j;
       ArcNode *p;
       G=(AdjGraph *)malloc(sizeof(AdjGraph));
       G->n=n; G->e=e;
       for (i=0;i<G->n;i++)	//邻接表中所有头结点的指针域置空
         G->adjlist[i].firstarc=NULL;
       for (i=0;i<G->n;i++)	//检查A中每个元素
         for (j=G->n-1;j>=0;j--)
            if (A[i][j]>0 && A[i][j]<INF)	      //存在一条边
            {  p=(ArcNode *)malloc(sizeof(ArcNode));  //创建结点p
               p->adjvex=j;
               p->weight=A[i][j];
               p->nextarc=G->adjlist[i].firstarc;  //头插法插入p
               G->adjlist[i].firstarc=p;
            }
    }
    

    2.3销毁图运算算法

    邻接表的头结点和边结点都是采用malloc函数分配的,在不再需要时应用free函数释放所有分配的空间。
    基本思路:通过adjlist数组遍历每个单链表,释放所有的边结点,最后释放adjlist数组的空间。

    void DestroyGraph(AdjGraph *&G)	//销毁图
    {  int i;
       ArcNode *pre,*p;
       for (i=0;i<G->n;i++)		//遍历所有的头结点
       {  pre=G->adjlist[i].firstarc;
          if (pre!=NULL)
          {  p=pre->nextarc;
             while (p!=NULL)  //释放adjlist[i]的所有边结点
             {  free(pre);
                pre=p; p=p->nextarc;
    	 }
    	 free(pre);
          }
       }
       free(G);		   //释放G所指的头结点数组的内存空间
    }
    
    

    2.4输出图运算算法

    将图G的邻接表存储结构输出到屏幕上。

    void DispGraph(AdjGraph *G)		//输出图的邻接表
    {  ArcNode *p;
       int i;
       for (i=0;i<G->n;i++)		//遍历所有的头结点
       {	printf("  [%2d]",i);
    	p=G->adjlist[i].firstarc;	//p指向第一个相邻点	
    	if (p!=NULL)
              printf(" →");
    	while (p!=NULL)
    	{  printf(" %d(%d)",p->adjvex,p->weight);
              p=p->nextarc;		//p移向下一个相邻点
    	}
    	printf("\n");
      }
    }
    
    

    2.5求顶点度运算算法

    对于无向图和有向图,求顶点度有所不同。依据定义,求无向图G中顶点v的度的算法如下:

    int Degree1(AdjGraph *G,int v)   //求无向图G中顶点v的度
    {  int d=0;
       ArcNode *p;
       if (v<0 || v>=G->n)
          return -1;	//顶点编号错误返回-1
       p=G->adjlist[v].firstarc;
       while (p!=NULL)	//统计v顶点的单链表中边结点个数即度
       {  d++;
          p=p->nextarc;
       }
       return d;
    }
    
    int Degree2(AdjGraph *G,int v)  //求有向图G中顶点v的度
    {  int i,d1=0,d2=0,d; ArcNode *p;
       if (v<0 || v>=G->n)
         return -1;		   //顶点编号错误返回-1
       p=G->adjlist[v].firstarc;
       while (p!=NULL)	   //统计v的单链表中边结点个数即出度
       {  d1++;
          p=p->nextarc;
       }
       for (i=0;i<G->n;i++)  //统计边结点中adjvex为v的个数即入度
       {  p=G->adjlist[i].firstarc;
          while (p!=NULL)
          {  if (p->adjvex==v) d2++;
    	 p=p->nextarc;
          }
       }
       d=d1+d2;
       return d;
    }
    
    

    2.6 主函数

    int main(int argc, char** argv)
    {
    	AdjGraph *G;
    	int n=5,e=7,i;
    	int A[MAXVEX][MAXVEX]={{0,1,2,6,INF},{INF,0,INF,4,5},{INF,INF,0,INF,3},{INF,INF,INF,0,INF},{INF,INF,INF,7,0}};
    	CreateGraph(G,A,n,e);	//建立图7.4图的邻接表
    	printf("图G的存储结构:\n"); DispGraph(G);
    	printf("图G中所有顶点的度:\n"); 
    	printf("  顶点\t度\n");
    	for (i=0;i<G->n;i++)
    		printf("   %d\t%d\n",i,Degree2(G,i));
    	DestroyGraph(G);
    	return 0;
    }
    

    时间关系博主就不展示效果了,把这些代码复制过去就可以了

    总结:

    图的存储我们学习的差不多了,邻接矩阵就是一个存放顶点的数组和一个二维数组组成,二维数组用来下标用来表示顶点与顶点的边连接,有这条边就把这两个下标对于的数组赋值1,没有赋值0,邻接表就是有多个链表,一个用来保存头结点,每个头结点会指向一个链表,这个链表用来存顶点的数组的下标,**注:存头结点的链表是结构体数组类型的。**好了这篇文章博主就学完了,传作不易,点赞关注评论收藏,谢谢啦!!!

    1235468910

    更多相关内容
  • 【详解】函数栈帧——多(c语言)

    千次阅读 多人点赞 2021-10-15 12:32:38
    在c语言中我们会将一些功能单独写成函数,以供主函数调用,在表面来看调用的过程就是写出函数后,只需要在调用时中通过函数名将实参传给形参就实现了整个过程,但实际上调用的过程远比你想的复杂,这其中...

    目录

    前言

    一.函数栈帧是什么?

    二、栈帧准备知识

    1.内存分区

    2.什么是栈?

     3.esp,ebp,eax寄存器

     三、详解栈帧创建与销毁全过程

    调用函数之前:

    将传入函数的值放入栈中

    函数执行:

    1.保护当前ebp

     2.创建所需调用函数的栈帧空间

     3.保存局部变量

     4.参数运算

     函数返回:

    1.存储返回值

     2.销毁空间

     3.ebp回上一栈帧栈底

     4.销毁形参

     5.main函数拿到返回值

    总结

    写在最后


    前言

    在c语言中我们会将一些功能单独写成一个函数,以供主函数调用,在表面来看调用的过程就是写出一个函数后,只需要在调用时中通过函数名将实参传给形参就实现了整个过程,但实际上调用的过程远比你想的复杂,这其中函数栈帧起着关键作用。通过本篇文章,我将告诉你函数在调用时计算机内究竟发生了什么?


    一.函数栈帧是什么?

    C语言中,每个栈帧对应着一个未运行完的函数。栈帧中保存了该函数的返回地址和局部变量。(来自百度百科)。

    通过这句话我们可以提炼出两个关键信息:

    1.每个未运行完的函数都有一个对应的栈帧

    2.栈帧保存了函数的返回地址和局部变量

     先对栈帧有一个简单的概念,知道其主要作用是什么就行。


    二、栈帧准备知识

    由于函数栈帧不光涉及c语言代码知识,如果是小白一定要认真看本节,这对帮助你理解栈帧非常重要,也不要因为发现这些知识你之前完全没听说过就产生畏难心理,事实上,我们只需要掌握期其中一些非常关键的地方就足够了。

    1.内存分区

    内存中主要分为栈区堆区静态区,以及其他部分

    栈区由高地址往低地址增长,主要用来存放局部变量,函数调用开辟的空间,与堆共享一段空间。(本篇重点

    堆区:由低地址向高地址增长,动态开辟的空间就在这里(malloc,realloc,calloc,free),与栈共享一段空间。

    静态区:主要存放全局变量和静态变量。 

     

    2.什么是栈?

    前面已经知道栈中存放了函数调用开辟的空间即栈帧,因此我们要明白什么是栈帧,必须先知道什么是栈。

    栈是一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后放入的数据被最先读出来)。

    简单来讲你可以把栈理解为一个弹夹,而我们放的数据就像子弹,当我们射子弹时,总是会把后压入的弹先射出去,因为后压入的弹一定是放在最上面的,而先压入的弹后射出去,因为先压入的弹在最下面。这就是栈最大的特点"先入后出,后入先出",而往栈中放数据我们称作压栈(push),拿出栈中的数据我们叫出栈(pop)。

     压栈(push):

     出栈(pop):

     

     3.esp,ebp,eax寄存器

    ebpebp是基址指针,保存调用者函数的地址,总是指向当前栈帧栈底
    espesp是被调函数指针,总指向函数栈栈顶
    eax累加器,用来乘除法,与函数返回值(本篇主要关注第二个功能)

     简单来讲就是esp和ebp是两个指针,ebp指向当前栈帧栈底,esp指向函数栈栈顶

      

    能看到,ebp并不是指向整个函数栈的栈底,而是指向当前栈帧的栈底,而由于esp总是指向栈顶,且栈只允许一个方向的操作,因此esp指向其实也是当前栈帧的栈顶,不过当前栈帧的栈顶始终与栈顶相同,因此说esp指向的是栈顶。


     三、详解栈帧创建与销毁全过程

    有了以上知识就能够初步理解栈帧从创建到销毁的全过程了,接下来我会一步一步讲解

    假设我们有当前代码:

    #include<stdio.h>
    
    int add(int a, int b)
    {
    	int c = 0;
    	c = a + b;
    	return c;
    }
    
    int main()
    {
    	int a = 1;
    	int b = 1;
    	int sum;
    	sum = add(a, b);
    	return 0;
    }

    调用函数之前:

     此时我们准备执行函数调用"sum = add(a,b);"此时栈中如下:

    将传入函数的值放入栈中

    由于函数调用涉及到传参,因此我们在调用函数之前,需要先将传入的参数保存,以方便函数的调用,因此需要将add函数的a=1,b=2,push入栈保存

      

    函数执行:

    1.保护当前ebp

    由于我们马上要创建新的栈帧空间,因此ebp和esp都得将变动,为了能够让我们调用完add函数后还能让ebp回到当前位置我们需要对ebp的值进行保护,即将此时ebp的值压入栈(至于为什么不需要保护esp,看到后面你就能明白)

       

     2.创建所需调用函数的栈帧空间

    令ebp指向当前esp的位置并根据add函数的参数个数,创建一个大小合适的空间。

     ebp指向当前esp的位置 

     

    ②创建空间

     

     3.保存局部变量

    将add函数中创建的变量"int c = 0"放入刚刚开辟的栈帧空间中

      

     4.参数运算

    根据形参与局部变量,进行对应的运算,这里执行"c = a +b", 得到 c = 2,放入刚才c对应的位置。

     

     到次函数执行就完成了,接下来就要开始实现函数返回

     函数返回:

    1.存储返回值

    现在我们已经达成了目的"add(a,b)",要将之前创建的add的函数栈销毁,以使得我们能够回到main函数中正常执行,而在销毁add的函数栈帧前我们的main函数可还没有拿到运算结果,因此我们需要先将需要返回的值存储起来,存储的位置就是前面提到的eax寄存器,这里"return c",我们将c的值放到eax寄存器中。

      

     2.销毁空间

    拿到了运算结果后,我们就没有任何任何顾虑了,可以直接销毁函数的栈桢空间了。

      

     3.ebp回上一栈帧栈底

    此时ebp拿到之间存储的上一栈帧栈底的值,回到相应的位置,于此同时,存储的ebp没有用了,也将被销毁。

     

     4.销毁形参

    形参也不再有用,因此也随即销毁。(这里也让我们明白:由于形参在调用完函数后就会销毁,且与实参根本不是同一地址,因此形参的改变无法影响实参

      

     5.main函数拿到返回值

    在讲解main函数怎么拿到返回值前,我想先问一个问题:

    上图中所谓的前一栈帧指的是什么?

    大家都知道,我们编写的c程序都是从一个main函数开始的,实际上,代码并不是直接从main函数开始运行的,main函数的本质也是一个被其他代码调用的函数,至于被谁调用,这里就不展开讲解了,这里提出这个问题是想要大家知道:

    main函数是一个函数,它有自己的栈帧

    因此所谓的前一栈帧实际上就是调用add函数的main函数的栈帧。

    因此我们要让main函数拿到返回值,只需要把eax寄存器中的值放入main栈帧中sum对应的位置就行。(这里也能让我们明白:由于我们只有一个eax寄存器,因此c语言的函数只能有一个返回值

      

     至此栈帧的创建与销毁结束,函数调用完成。


    📝总结

    经过以上的学习,我希望大家能学到一下几点:

    什么是函数栈帧?

    函数在调用时发生了什么?

    为什么函数只能有一个返回值?

    为什么形参的改变无法影响实参?

    答案都在文中哦!😘 


    ✨写在最后

    在自己学习函数栈帧的创建与销毁时,我看了很多博客,大家都比较喜欢直接通过汇编代码来讲,我觉得这对于像我这样c语言初学者,以及在此之前根本没接触过汇编的人简直是折磨与煎熬,难以理解发生了什么。因此我决定直接以图形的直观方式为大家讲解,虽然相比于实际情况我省略了些许步骤,但那并不影响我们了解栈帧的创建与销毁。

    对于函数栈帧,我认为并不需要专门去学习相关的汇编知识,只需要作为了解知识,并且能明白我上面提出的四个问题就够了

    展开全文
  • 经验风险:个损失函数函数结构风险:可简单理解为经验风险(种损失函数函数)+λ正则化项。因此,模型的结构风险函数包括了经验风险项和正则项,通常可以表示成如下式子:θ∗=argminθ1N∑i=1NL(yi,f(xi;θ...

    损失函数:用来估量你模型的预测值f(x)与真实值Y的不一致程度,它是一个非负实值函数,通常使用L(Y, f(x))来表示,损失函数越小,模型的鲁棒性就越好。

    经验风险:一个损失函数的函数

    结构风险:可简单理解为经验风险(一种损失函数的函数)+λ正则化项。因此,模型的结构风险函数包括了经验风险项和正则项,通常可以表示成如下式子:

    θ=argminθ1Ni=1NL(yi,f(xi;θ))+λ Φ(θ)

    其中,前面的均值函数表示的是经验风险函数,L代表的是损失函数,后面的 ΦΦ 是正则化项(regularizer)或者叫惩罚项(penalty term),它可以是L1,也可以是L2,或者其他的正则函数。整个式子表示的意思是 找到使目标函数最小时的θθ


    对于损失函数:

    线性回归中的损失函数:平方损失函数可以通过线性回归在假设样本是高斯分布的条件下推导得到.

    逻辑回归中的损失函数:log损失函数在逻辑回归的推导中,它假设样本服从伯努利分布(0-1分布),然后求得满足该分布的似然函数,接着取对数求极值等。而逻辑回归并没有求似然函数的极值,而是把极大化当做是一种思想,进而推导出它的经验风险函数为:最小化负的似然函数(即max F(y, f(x)) —-> min -F(y, f(x)))。

    log损失函数形式:L(Y,P(Y|X))=logP(Y|X)

    这里取对数是为了方便计算极大似然估计。损失函数L(Y, P(Y|X))表达的是样本X在分类Y的情况下,使概率P(Y|X)达到最大值(换言之,就是利用已知的样本分布,找到最有可能(即最大概率)导致这种分布的参数值;或者说什么样的参数才能使我们观测到目前这组数据的概率最大)。因为log函数是单调递增的,所以logP(Y|X)也会达到最大值,因此在前面加上负号之后,最大化P(Y|X)就等价于最小化L了。

    逻辑回归的P(Y=y|x)表达式如下(为了将类别标签y统一为1和0,下面将表达式分开表示):

    将它带入到上式,通过推导可以得到logistic的损失函数表达式,如下:

    逻辑回归最后得到的目标式子如下:

    J(θ)=1mi=1m[y(i)loghθ(x(i))+(1y(i))log(1hθ(x(i)))]J(θ)=−1m∑i=1m[y(i)log⁡hθ(x(i))+(1−y(i))log⁡(1−hθ(x(i)))]

    上面是针对二分类而言的。这里需要解释一下:之所以有人认为逻辑回归是平方损失,是因为在使用梯度下降来求最优解的时候,它的迭代式子与平方损失求导后的式子非常相似,从而给人一种直观上的错觉

    这里有个PDF可以参考一下:Lecture 6: logistic regression.pdf.

    二、平方损失函数(最小二乘法, Ordinary Least Squares )

    最小二乘法是线性回归的一种,OLS将问题转化成了一个凸优化问题。在线性回归中,它假设样本和噪声都服从高斯分布(为什么假设成高斯分布呢?其实这里隐藏了一个小知识点,就是中心极限定理,可以参考【central limit theorem】),最后通过极大似然估计(MLE)可以推导出最小二乘式子。最小二乘的基本原则是:最优拟合直线应该是使各点到回归直线的距离和最小的直线,即平方和最小。换言之,OLS是基于距离的,而这个距离就是我们用的最多的欧几里得距离。为什么它会选择使用欧式距离作为误差度量呢(即Mean squared error, MSE),主要有以下几个原因:

    • 简单,计算方便;
    • 欧氏距离是一种很好的相似性度量标准;
    • 在不同的表示域变换后特征性质不变。

    平方损失(Square loss)的标准形式如下:

    L(Y,f(X))=(Yf(X))2L(Y,f(X))=(Y−f(X))2

    当样本个数为n时,此时的损失函数变为:
    $$L(Y, f(X)) = \sum _{i=1}^{n}(Y - f(X))^2$$
    Y-f(X)表示的是残差,整个式子表示的是 残差的平方和,而我们的目的就是最小化这个目标函数值(注:该式子未加入正则项),也就是最小化残差的平方和(residual sum of squares,RSS)。

    而在实际应用中,通常会使用均方差(MSE)作为一项衡量指标,公式如下:

    MSE=1ni=1n(Yi~Yi)2MSE=1n∑i=1n(Yi~−Yi)2

    上面提到了线性回归,这里额外补充一句,我们通常说的线性有两种情况,一种是因变量y是自变量x的线性函数,一种是因变量y是参数 αα的线性函数。在机器学习中,通常指的都是后一种情况。

    三、指数损失函数(Adaboost)

    学过Adaboost算法的人都知道,它是前向分步加法算法的特例,是一个加和模型,损失函数就是指数函数。在Adaboost中,经过m此迭代之后,可以得到fm(x)fm(x):

    $$f_m (x) = f_{m-1}(x) + \alpha_m G_m(x)$$

    Adaboost每次迭代时的目的是为了找到最小化下列式子时的参数αα 和G:

    $$\arg \min_{\alpha, G} = \sum_{i=1}^{N} exp[-y_{i} (f_{m-1}(x_i) + \alpha G(x_{i}))]$$

    而指数损失函数(exp-loss)的标准形式如下

    $$L(y, f(x)) = \exp[-yf(x)]$$

    可以看出,Adaboost的目标式子就是指数损失,在给定n个样本的情况下,Adaboost的损失函数为:

    L(y, f(x)) = \frac{1}{n}\sum_{i=1}^{n}\exp[-y_if(x_i)]

    关于Adaboost的推导,可以参考Wikipedia:AdaBoost或者《统计学习方法》P145.

    四、Hinge损失函数(SVM)

    在机器学习算法中,hinge损失函数和SVM是息息相关的。在线性支持向量机中,最优化问题可以等价于下列式子:
    $$\min_{w,b}  \ \sum_{i}^{N} [1 - y_i(w\cdot x_i + b)]_{+} + \lambda||w||^2 $$
    下面来对式子做个变形,令:
    $$[1 - y_i(w\cdot x_i + b)]_{+} = \xi_{i}$$
    于是,原式就变成了:
    $$\min_{w,b}  \ \sum_{i}^{N} \xi_i + \lambda||w||^2 $$
    如若取λ=12Cλ=12C,式子就可以表示成:
    $$\min_{w,b}  \frac{1}{C}\left ( \frac{1}{2}\ ||w||^2 $$ + C \sum_{i}^{N} \xi_i\right )$$
    可以看出,该式子与下式非常相似:
    $$\frac{1}{m} \sum_{i=1}^{m} l(w \cdot  x_i + b, y_i) + ||w||^2$$

    前半部分中的ll就是hinge损失函数,而后面相当于L2正则项。

    Hinge 损失函数的标准形式

    L(y)=max(0,1yy~),y=±1L(y)=max(0,1−yy~),y=±1

    可以看出,当|y|>=1时,L(y)=0。

    更多内容,参考Hinge-loss

    补充一下:在libsvm中一共有4中核函数可以选择,对应的是-t参数分别是:

    • 0-线性核;
    • 1-多项式核;
    • 2-RBF核;
    • 3-sigmoid核。

    五、其它损失函数

    除了以上这几种损失函数,常用的还有:

    0-1损失函数
    L(Y, f(X)) = \left\{\begin{matrix}1 ,& Y \neq f(X)\\ 0 ,& y = f(X)    \end{matrix}\right.
    绝对值损失函数
    $$L(Y, f(X)) = |Y-f(X)|$$
    下面来看看几种损失函数的可视化图像,对着图看看横坐标,看看纵坐标,再看看每条线都表示什么损失函数,多看几次好好消化消化。

    OK,暂时先写到这里,休息下。最后,需要记住的是:参数越多,模型越复杂,而越复杂的模型越容易过拟合。过拟合就是说模型在训练数据上的效果远远好于在测试集上的性能。此时可以考虑正则化,
    通过设置正则项前面的hyper parameter,来权衡损失函数和正则项,减小参数规模,达到模型简化的目的,从而使模型具有更好的泛化能力。

    平方误差函数(square error function)与平方损失函数(square loss function):

    最初的最小二乘法并没有统计理论基础,只是一种数值计算方法。一般只求使(tiy(xi,θ))2∑(ti−y(xi,θ))2最小的θ^θ^,也不考虑t的具体模型假设是什么。当我们学习最小二乘的时候,我们总是会问,问什么我们取差的平方和,而不取差的绝对值,或者四次方的和呢?答案是最小二乘法为人们所熟知所运用,最根本的原因是,它与高斯模型下的极大似然估计的结果是一致的!因此,我们使用最小二乘而不使用最小一乘或四乘是有道理的。

    损失函数是用来做预测的,属于决策理论的范畴。在一个估计好的模型t=f(x,θ^)+ϵt=f(x,θ^)+ϵ下,我们如何对一个预测变量xx′的输出tt′进行预测呢?用t^=f(x)t^′=f(x′)作预测呗。有没有想过其原因呢?其实,这时tt′是一个随机变量,这个随机变量可能会取各种各样的值,用f(x)f(x′)作为tt′的预测值,在ϵϵ服从0均值正态分布假设下,意味着用一个随机变量的均值对一个随机变量做预测。显然,预测不可能准确,也就是说tt^t′−t^′不可能为0。但是,在使tt^)2(t′−t^′)2最小的情况下,用均值做预测是最好的选择。而tt^)2(t′−t^′)2就是平方损失函数,即预测可能发生的损失。在其他损失函数下,比如tf(x)‖t′−f(x′)‖,这时用均值做预测,就不会让这个损失函数最小,反而用中位数会更好。

    参考文章:

    http://www.csuldw.com/2016/03/26/2016-03-26-loss-function/


    展开全文
  • 因此树其实也是种特殊的图结构,树的每个节点只能有个入度,而可以有多个,知识点在这里解不讲解了,例如弧,入度,出度等可以查阅书籍或者网上查阅。这里主要讲解的存储结构,遍历方法等。 的存储...
    简要

    图的结构类似于树,都是一个又一个结点(顶点)连接而成,如下图:
    在这里插入图片描述
    因此树其实也是一种特殊的图结构,树的每个节点只能有一个入度,而图可以有多个,图的知识点在这里解不讲解了,例如弧,入度,出度等可以查阅书籍或者网上查阅。这里主要讲解图的存储结构。

    图的存储结构

    图有多种存储结构,例如邻接矩阵,邻接表或者十字链表等,那么它是如何用结构体来实现上面图这种抽象结构的?

    之前文章所说,数据结构一般都有两种表示方法,一种是数组,一种是链式,由于图的结构比较复杂,任意两个点之间都有可能存在联系,因此无法以数据元素放到数组这种来表示它的关系。但是换个思路,当遇到简单的图(有向和无向)或者网(有向和无向,带有路径,权就称为网)表示的时候,你可以用两个数组来存储图的数据信息和顶点之间的关系。那么就引出了邻接矩阵。

    邻接矩阵

    上面说用两个数组来表示图的关系,具体什么意思,首先拿最简单的有向图来举例:
    在这里插入图片描述
    以上关系简单理解,V1可以到V2,V2可以到V3等等这里就不细说。这里所说的用矩阵来表示该图关系,其实是用一个二维数组来表示该矩阵。用下面图来解释什么意思:
    在这里插入图片描述
    二维数组都有序号,有几个顶点就有几行几列,比如V1可以到V2,那么在数组上的第一行第二列的值就应该为 1 , V1无法到达V3
    ,那么数组中第一行的第三列的值就为0,那么自然就懂了, 图中顶点的序号对应数组中的位置 (当然数组中也是从0开始算起的,这里只是帮助理解),有路径,可以到达,那么对应数组的值就为1,如果没有路径那么对应的值就为0,
    那么这里就用了一个二维数组来表示了图中各顶点之间的关系。自然可以发现,第一行为1 的个数就是顶点序号为1 的出度数,列就是顶点总的入度数。

    上面这个是有向图的二维数组定义,那么无向图的二维数组自然就懂了,无向图的定义是两个顶点可以互相到达,那么二维数组就自然成了对称矩阵了,可以自己画画,这里就不说了。

    然后再定义一个数组来存放各个顶点的数据关系,那么就完成了图结构的创建,也可以抽象的想成,定义一个储存图顶点的数组,再定义一个二维数组来存储顶点的关系。
    在这里插入图片描述
    上图就已经完全解释了邻接矩阵如何实现了存储,就是定义一个图的结构体,然后其中定义俩数组一个放顶点(包括顶点的信息),一个放顶点的位置关系。
    那么定义的结构体为:

    //图结构体的定义
    #define MAX_SIZE 20        //定义的最大存储顶点数目
    typedef struct 
    {
         VertexType vex[MAX_SIZE];     //定义顶点数组,存放顶点的信息,如果信息复杂了那么自然还要定义顶点的结构体
         AdjMatrix arcs[MAX_SIZE][MAX_SIZE];     //定义的邻接矩阵(顶点位置关系),如果单纯的就表示一些距离值,那么直接定义一个int 类型的二维数组即可,如果顶点间还有其他信息那么就将其定义成一个结构体
         int vexnum,arcnum;    //定义图的顶点数和弧数,弧数就是顶点关系的个数
    }Graph;
    
    //初始化图
    void init(Graph &G)
    {
       int i,j; 
       printf("请输入顶点数和弧数");
       scanf("%d",&i);
       scanf("%d",&j);
       G.vexnum=i;      //对图的信息进行初始化
       G.arcnum=j;
                  
     for(int x=0;x<G.vexnum;x++)      //这里是根据定义的节点数来对矩阵进行初始化
     {
      for(int y=0;y<G.vexnum;y++)
      {
         G.arcs[x][y]=0;     //对图结构中的位置关系进行初始化,先都化为0,表示节点直接都不相连
      }
     }
     
     for(int x=0;x<G.vexnum;x++)
     {
       printf("输入顶点的信息");        //对节点信息进行输入
       scanf("%s",&G.vex[x]);         //输入到定义的顶点信息数组中
     }
     
     for(int x=0;x<G.vexnum;x++)
     {
      printf("请输入要连接的节点"); 
      int a,b;
        scanf("%d",&a);       //按照顶点在位置数组中的序号来写,数组都是从 0 开始的,也可以写一个根据信息来定在数组中位置的函数。
        scanf("%d",&b);
        G.arcs[a][b]=1;      //获取了需要连接顶点的位置后,将其对应数组中的位置等于 1,表示相通
       //G.arcs[b][a]=G.arcs[a][b]   若为无向图,自然顶点是互相连通的,所以在数组中也是对称的
     }
    }
    
    //输出函数 (就是将图的邻接矩阵输出,就能得到图中顶点的关系)
    void printGraph(Graph &G)
    {
     for(int i=0;i<G.vexnum;i++)
     {
      for(int j=0;j<G.vexnum;j++)
      {
       printf("%d ",G.arcs[i][j]);    //这里是图,所以设置的是1和0代表是否有路径
      }
      printf("\n");
      }
     } 
    

    这里假设有个例子
    在这里插入图片描述
    要来实现上面的图,顶点信息就存它们顶点的名称。

    //结构体定义
    typedef struct       //简单点的图结构
    {
         char vex[MAX_SIZE];      //顶点信息,这里假设存放字符串,表示他们的顶点
         int arcs[MAX_SIZE][MAX_SIZE];     //位置关系数组
         int vexnum,arcnum;    
    }Graph;
    init();     //一下两个函数定义就不重复写了
    printGraph();
    int main()
    {
       Graph G;
       init(G);
       printGraph(G);
    }
    

    那么就输出上面的例图:
    在这里插入图片描述
    先输入图结构的信息,几个顶点几条弧( 几条边 )然后输入三个顶点的信息,执行三次输入操作,然后顶点信息输入完成后,输入弧的信息,你要连接的点,按照顶点在数组中的位置(顶点在顶点数组的位置要和在邻接矩阵对应好),然后输出邻接矩阵,如图,那么可以看出第一行第二个第三个为 1 说明V0可以通到V1和V2 。可以慢慢理解

    上面是有向图,那么有向网(带权值的图,带路径的)自然就懂了。那么初始化定义就可以在原来的基础上加上:

    void init(Graph &G)                     //初始化函数和上面的一样,就是在后面加上权值赋值的操作
    {
     int i,j;
     printf("请输入图的节点数和弧数");
     scanf("%d",&i);
     scanf("%d",&j);
     G.vexnum=i;
     G.arcnum=j;
     for(int x=0;x<G.vexnum;x++)
     {
      for(int y=0;y<G.vexnum;y++)
      {
        G.arcs[x][y]=99;       //先将邻接矩阵每个值定义为99,因为无法到达,那么它的权值就是无穷大,这里用99代替无穷大
      }
     }
     for(int x=0;x<i;x++)
     {
      printf("请输入顶点的数据信息");
      scanf("%s",&G.vex[x]);
     }
     for(int x=0;x<j;x++)
     {
         printf("请输入要连接的点"); 
         int a,b,c;
         scanf("%d",&a);
         scanf("%d",&b);
         printf("请输入它的权值");
         scanf("%d",&c);              //主要在这里修改即可,将原来的 1改为输入权值即可
         G.arcs[a][b]=c; 
     }
    }
    

    那么实现下面这个例子:
    在这里插入图片描述上面标有了权值那么如何实现:

    int main()
    {
     Graph G;
     init(G);
     printGraph(G);
    }
    

    在这里插入图片描述
    输出结果可以从邻接矩阵看出顶点的位置和权值信息。根据矩阵中的序号来推断各顶点之间的信息。(99代表没有路径,无穷大)
    邻接矩阵比较简单。

    邻接表

    邻接表表示法有点类似前面数结构中的孩子表示法,可以看之前的树结构文章。
    总而言之,邻接表的功能是找出与其连接的点以及权值,但是你要找它的入度之类却比较麻烦,需要遍历所有顶点,不如邻接矩阵的。

    邻接表是如何定义的?

    将每个顶点用结构体定义,但是还是要放在那个图结构体的数组中,但是每个顶点结构体中有一个链式表来存放弧的信息,(其连接的下一个点和它的权值)。
    在这里插入图片描述
    上面是框架图,下面为解释图:
    在这里插入图片描述
    每个顶点中有一个链式表来存放它指向的顶点的位置(在数组中的位置)或者也可以存弧的权值,这里的链式表里信息只存放它指向顶点的位置,并不存储指向顶点的数据信息,相当于一个索引。只需要遍历顶点的线性表就可以获得它所指向的有哪些顶点了。这里也可以将该链式表理解为一个存储弧信息的表。

    首先定义图的结构体框架:(这个例子是带有权值的,应该叫做网,但是为了大家方便理解,就先叫做图吧)

    typedef struct ArcNode  //定义图中的表结构,链式表
    {
     int adjvex;    //要连接点在数组中的位置
     int arc;     //定义顶点与该连接点之间的权值
     struct ArcNode *next;  //定义下一个节点,链式表之间的链,实现链式表之间的连接
    }ArcNode;
     typedef struct VNode   //定义图顶点结构
    {
     ArcNode *first;     //每个顶点中的表头的头指针,可根据上面的图像理解
      char vex[10];      //图信息(数据)的存储,这里也可以存储顶点的多个数据,都由自己定,这里就假设存储的是顶点名称
    }VNode;              //定义图顶点结构
    typedef struct 
    {
     VNode NodeList[10];      //定义顶点数组,存放图的顶点,和上面的道理一样
     int vexnum,arcnum;       //定义图的属性,几个顶点几条弧
     }Graph;    //定义图总框架,c语言调用的时候要遵从先后定义顺序,所以该图结构定义在最后面
    

    对链式表不太了解的可以看下面文章
    线性表------最通俗易懂的文章

    然后我们将该中图结构进行一下实例化:

    void initGraph(Graph &G)
    {
     int x,y;
     printf("输入图的节点个数");
     scanf("%d",&x);
     G.vexnum=x;      //定义图的顶点数目
     for(int i=0;i<G.vexnum;i++)    //对顶点的信息进行初始化,输入,因为这里定义的是顶点数组,所以用循环来定义顶点的信息
     {              
      scanf("%s",&G.NodeList[i].vex);    //输入顶点的数据信息
      G.NodeList[i].first=(ArcNode*)malloc(sizeof(ArcNode)); //对每个顶点的链表头指针进行初始化,不懂可以看线性表文章
      G.NodeList[i].first->next=NULL;        
     }
     for(int i=0;i<G.vexnum;i++)    //按照顶点在数组中的位置进行循环对顶点的相关弧来对点的弧进行初始化信息
     {
      printf("这是%s节点,输入它的弧的个数为:",G.NodeList[i].vex);
      int n;
      scanf("%d",&n);     //输入当前顶点的弧数
      ArcNode *p;        //定义一个头指针来绑定每个顶点中的链式表,号方便进行对其的操作
      p=G.NodeList[i].first;   
               
      for(int j=0;j<n;j++)    //对你定义的弧数进行初始化
      {
       ArcNode *q;
       q=(ArcNode*)malloc(sizeof(ArcNode)); //来为链式表的每一个节点来开辟空间(创建一个临时节点来实现链式表的连接)
       
       printf("要连接的节点:"); 
       scanf("%d",&q->adjvex);       //要连接顶点在数组中的位置
       printf("弧的长度为:");
       scanf("%d",&q->arc);          //要连接顶点与当前顶点的权值
       q->next=NULL;        //实现链式表的连接,这里是从尾部进行连接的,上面文章中是从表头后进行连接的,连接原理可以看上面文章
       p->next=q;
       p=q;         //将p指针绑定成下一个节点,方便进行下一次的连接
      }
     }
    }
    

    再定义一个输出函数,当输入顶点的位置后,就可以输出它所连接的点了,这里是有向图,可以输出它所出度的点。

    void printfG(Graph &G,int n)
    {
        ArcNode *p=G.NodeList[n].first->next;     //绑定需要输出的顶点的next指针
        printf("这是%s顶点",G.NodeList[n].vex);    //
        while(p!=NULL)      //对链式表进行循环遍历,若为空,说明以及到了链式表的结尾
        { 
         printf("它连接的顶点有%d,",p->adjvex);    //对其连接点信息的输出
         printf("它俩之间的权值为%d\n",p->arc);
         p=p->next;                            //进行绑定链式表的下一个节点
     }
    }
    
    具体实现

    在这里插入图片描述
    那么就实现一下上面的图,比较简单,方便理解。可见V0的出度弧有两个,那么该顶点的链式表就有两个节点,同理V1和V2。

    int main()
     {
      Graph G;    //定义图的总框架结构
      initGraph(G);   //对该结构进行初始化
      printfG(G,0);   //输出相应的顶点,这里就假设输出V0顶点(这里的0是V0在数组中的位置)
     }
    

    在这里插入图片描述简介明了,输入节点数后,对这几个节点进行初始化:顶点数据,所连接的有那些顶点和之间的权值等等,当然唯一缺点就是不能看顶点的入度,需要遍历所有的顶点。否则你可以设置一个逆邻表,就是链式表所存的信息都是入度的信息,上面例子中链式表所存的信息都是出度的信息。

    上面的邻接表只是方便来看顶点所连接的有哪些点和之间的权值,但是想遍历图中顶点的所有信息和关系,比较麻烦,所以出现了十字链表。

    十字链表

    由于受篇幅长度影响,这里就大概说一下原理,大家可以研究。上面两种图结构中的弧只是一个抽象的意义,你并没有定义弧这个对象吧,所以说的顶点的连接是用一种关系来代替弧的存在,那么十字链表是将弧也进行结构体封装定义,每有一条弧就定义一个结构体,里面存弧所连俩顶点在数组中的位置,然后两个指针域,一个指向相同入度的点,一个指向相同出度的点,(指针所指向的还是弧的结构体)那么你随便查询一个顶点的出入信息,那么就可以使用它的弧节点的指针域,直到为NULL为止。

    可以看下面文章:
    十字链表法

    图的遍历

    图的两种常用遍历方法:深度优先搜索和广度优先搜索

    深度遍历

    深度遍历算法是使用了递归的思想,随便找到一个顶点,然后找到它连接的第一个顶点,一直找连接的第一个顶点,直到找到没有连接的顶点,然后返回到上一级递归找他的另一个子顶点,然后再开始深度搜索,就是一直往下突,直到没有连接的顶点为止(遍历过的节点不能再遍历一次,也相当于是不能连接的点),然后再返回去,重复递归操作就可以遍历完图中所有顶点。下面给出深度遍历图的流程:

    在这里插入图片描述红色数字表示遍历顶点的顺序。

    可以看上图慢慢理解,十分简单。这里可以根据树结构的遍历来理解,当你遍历到最后面的节点无处可走的时候,返回到它的上一个节点,看看有没有第二个子节点,如果有就开始遍历它的第二个子节点,如果没有第二个子节点了了,再返回上一个节点,重复此步骤。只不过在图结构中,只要有连接的可遍历点就一口气捅到最后面,然后回溯(一个一个的回溯,仔细检查是否有第二个子顶点),有点贪心法的味道。

    实现

    那么它是如何实现这种遍历方法?上面说了主要使用递归的方法来实现,首先递归函数的使用和原理得理解,就是定义一个函数,在这个函数里面使用该函数,具体使用这里就不讲解了。

    咱们就拿上图做例子
    在这里插入图片描述

    这里创建过程就不写了,首先你遍历的时候,是如何判定顶点是否已经遍历过了,使你不会再进行第二次遍历?就是设置一个布尔(bool)类型的数组,数组的大小就是你顶点的数目,来存放每个点是否遍历过,初始化为false表示未遍历过,当遍历过后就将相应顶点的 bool 设置为true。

    举个例子,有三个点需要遍历:

    bool visited[3];    //因为三个顶点,所以布尔数组的容量设置为3
     for(int i=0;i<3;i++)
     {
         visited[i]=false;   //将每个顶点进行初始化为false,表示每个点都没有遍历过
      }
      visited[1]=true;     //表示第二个顶点遍历过了,所以将其bool值设置为了true 
    

    那么需要在程序中设置一个全局变量布尔数组,用来监控图遍历的情况,那么为什么要定义全局变量,而不是直接在图创建的时候,在图结构里面定义?因为该种遍历方法使用了递归的方法,会导致布尔数组结果回溯。导致遍历过的顶点再遍历一次,程序错误。

    bool visited[MAX_SIZE];     //全局变量定义需要在函数外
    

    然后定义两个查找子顶点函数

    int findFirst(Graph G,int w)     //定义一个找第一个子顶点的函数,w表示要找哪个顶点的子顶点
    {
     for(int n=0;n<G.vexnum;n++)
     {
      if(G.arcs[w][n]==1&&visited[n]==false) return n;    //根据矩阵的特点找第一个顶点,第几个顶点就是在矩阵的第几行,从第一列开始循环,当为1的时候说明相应的顶点相连,第一个1说明就是其第一个顶点
      //并且返回第一个顶点是哪个顶点(在数组中的位置)
     }
     return 0;     //若该顶点没有任何相连的点后返回0
    }
    
    
    
    int findNext(Graph G,int w,int t)   //找下一个子顶点函数,w表示要找哪个顶点的子顶点,t表示查找的开始点
    {
     for(t=t+1;t<G.vexnum;t++)        //因为这是找next顶点,所以要t=t+1,原因可以看下面的遍历来理解为什么
     {
      if(G.arcs[w][t]==1&&visited[t]==false) return t;    //和上面的一样,当为矩阵中的值为1 的时候说明两点相连,并且返回是哪个顶点
     }
     return 0;      //当没有相邻的顶点后函数就会返回 0
    }
    

    Tip:根据矩阵的性质,给你一个点,可以从矩阵找它的第一个子顶点和下一个子顶点,自己慢慢理解,但是对于无向图大家都知道,是对称矩阵,那么在深度遍历或者广度遍历无向图的时候,找子顶点会有重复现象,已经遍历过了的顶点,再用两个找子顶点函数就会重复,重复遍历,那么就要在找子顶点函数的判断中加上 visited[n]==false 条件,在找到子顶点的同时并且判断该子顶点是否已经遍历过了,如果没有再返回子顶点。

    定义深度遍历函数:

    void DeepTraverse(Graph G)      //深度遍历函数
    {
     for(int v=0;v<G.vexnum;v++) visited[v]=false;   //初始化布尔数组,将每个顶点都设置为false,表示都没有遍历过
     for(int v=0;v<G.vexnum;v++)       //这步是开始进行遍历,使用下面DFS函数,这里为什么还要对所有顶点进行一次循环?
     //深度遍历,只要是相连的顶点,从其中一个点遍历,就可以全部一连串都遍历出来,但是图中可能有不连通的两部分,导致其中不相连,那么有些点就遍历不上了,所以为了防止这种情况,将所有顶点的visited数组遍历一下
     {
       if(visited[v]==false) DFS(G,v);   //根据布尔数组,若为false则开始遍历,调用下面的递归函数,v就是上面开始遍历的点
    }
    
    void DFS(Graph G,int v)       //遍历递归函数
    {
     visited[v]=true;     //遍历的时候,将其对应布尔数组设置为true,表示已经遍历过了
     printf("%s",G.vex[v]);    //将遍历的点数据处理,这里就简单的输出作为数据处理
     for(int w=findFirst(G,v);w>0;w=findNext(G,v,w))  //开始递归操作,进行一个循环先找当前遍历点的第一个子顶点作为 w 的初始值
     //若有第一个子顶点,那么findFirst函数返回的就不是0,开始进行DFS函数递归,若没有子顶点,那么返回0,直接退出该循环,表示该点后面的子顶点遍历完了。
     {
      if(visited[w]==false) DFS(G,w);    //若当前点未遍历过,那么进入DFS函数进行递归
     }
    }
    

    上面就是深度遍历的过程,主要是由递归函数来实现的,所以比较麻烦,可以进行debug操作来一步一步看其过程,下面举个简单的例子来解释一下代码流程

    在这里插入图片描述
    如何创建图结构上篇文章已经讲了,这里就不多说了,下面是创建的结果:
    在这里插入图片描述

    那么代码执行流程 :

    在这里插入图片描述
    橙色文字表示DFS递归级别,就是DFS1是在DFS 0中调用的,DFS 2实在DFS 1 中调用的,这里想要理解其使用,必须先理解递归函数怎么用和它的原理。

    那么会得出其结果为:
    在这里插入图片描述

    因为咱们代码为边遍历边输出它的信息,所以就会得出其遍历顺序为: V0 V1 V3 V2,符合深度遍历的特点。

    那么再看之前的例子:
    在这里插入图片描述
    输出的顺序在片头已经给出,那么用程序试一下:
    在这里插入图片描述
    那么输出结果符合,深度遍历实现。

    总结

    深度遍历你先理解其含义和运行流程,就是随便找到一个顶点一个劲的往下突,突到头后,开始回溯,但是还要将所有顶点再进行一次审查,防止不连通的图,导致顶点遗漏,因为只要开始深度遍历,那么只要其是相连的顶点,那么都可以一次性遍历完,那么这个实现的步骤就是使用递归函数来实现,有点类似8皇后问题。

    广度遍历

    广度遍历顾名思义,遍历方式是一层一层的,就是只要与当前遍历点距离为1的点先开始遍历,,因此也可以称为广度优先遍历,和深度优先遍历不同的是,深度遍历是一个劲的往下突,而广度像是一种横扫的方式。其实用一张图来演示一下流程就懂了。
    在这里插入图片描述
    红色数字表示遍历点的顺序,有点像扩散,就是寻找当前点距离为1的点,但是它是一层一层的,然后再找与上一次所找的顶点距离为1的点,但它并不是同时遍历的,还是有顺序的遍历。
    上面的数组其实是一个辅助理解作用,但是它可以方便理解代码是如何实现的 。

    实现

    广度优先遍历代码实现需要用队列做基础,从上面图看出,可以假设这里有一个数组(当然不是具体的数组,只是一个抽象的集合),存放需要找距离为1的顶点。当你开始的时候,数组中先存放V0,起始点。然后从数组中取出V0(这时候数组为空),寻找与V0距离为1的点,就是紧挨的点,找到了V1和V2,再放到数组中,然后再按存放的顺序,拿出V1,找与它距离为1的顶点,找到V3,放到数组中,按照顺序,是不是该找V2了,然后找与V2距离为1的点,找到V4和V5,那么这回数组中就为 { V3,V4,V5 },同理,再开始找V3,显然没有顶点了,然后按顺序找V4,V5.这就是大概流程,就是先取出一个,找到相关顶点再放到数组中,按顺序找下一个,再取,再放。其实这个思想是代码实现的思想,那么上面说的好像是一层同时遍历是算法的思想。

    其实总结一下就是你找到一个点,找与它相连的几个点,放到数组里,然后依次找这几个点相关的点,再次放到数组里,然后在去找上一次找出的点的相关点放进去,好像是一层一层的。

    那么这里就用了队列做辅助工具,如果不理解队列结构创建和使用的看下面文章
    数据结构-----------队列(最通俗易懂的文章)

    那么我们用一张图来表示队列存储的流程:
    在这里插入图片描述
    那么要用队列数据结构做工具,肯定有队列数据结构的创建和使用:

    typedef struct     //队列数据结构创建,其实就是定义一个结构体,在结构体数组中存储数据
    {
       int *base;      //定义一个数组指针
       int head;       //队列俩索引,不懂看上面文章(和栈中的指针作用一样)
       int tail; 
    }Queue;
    
    int init(Queue &Q)      //初始化队列函数
    {
     Q.base=(int*)malloc(MAX*sizeof(int));   //为数组指针开辟空间,因为队列其实就是在一个结构体里的数组中存储读取数据
     if(!Q.base) return 0;     //基本操作,当分配空间后,如果分配失败,那么返回0
     Q.head=Q.tail=0;          //初始化,让两个索引指向相同的区域
    } 
    
    //定义入队列的函数
    int EnQueue(Queue &Q,int e)      //e表示存储的数据,这里假设队列中的数组是int类型,存储int类型的数据
    {
     if(Q.tail==MAX-1) return 0;      //每当插入数据的时候,首先看所插入对象是否满了,当队尾已经到达最大值,返回0
     Q.base[Q.tail]=e;        //从队尾所指向的区域存储数据,因为你是往数组里面存储
     Q.tail++;       //存储后,tail索引上移
    } 
    
    //出队列函}
    int GetQueue(Queue &Q)
    {
     if(Q.head==Q.tail) return 0;      //当获取数据时候,第一步肯定是看该数据结构是否为空,如上图所示,当head和tail所指向相同区域后说明该数据结构为空
     int e;
     e=Q.base[Q.head];      //从head所指向的区域获得值
     Q.head++;              //获取值后,然后head索引上移
     return e;              //返回值
    }
    

    那么队列数据结构创建好后,并且也理解了广度遍历算法那么代码是如何实现的:

    void BFSTraverse(Graph &G)
    {
     Queue Q;             //创建队列,因为广度遍历要用
     initQueue(Q);        //初始化队列
     for(int v=0;v<G.vexnum;v++) visited[v]=false;    //这个和深度遍历一样,你要遍历图,首先对图中所有顶点用bool数组进行初始化,表示都还未遍历,当然该数组要用全局变量定义原因上面有
     for(int v=0;v<G.vexnum;v++)    //和深度遍历一样作用,可能图中有些点之间不连通,可能会遗忘遍历
     //所以要对所有顶点最后进行一次审查,但是如果联通,只要从一个顶点进去了就一连串可以遍历出来
     {
       if(visited[v]==false)       //开始遍历
      {
       visited[v]=true;            //表示该点已经遍历
       printf("%s",G.vex[v]);      //对该点数据处理,这里就用输出语句代替复杂的处理语句
       EnQueue(Q,v);               //将该点入队列,每个点是先遍历再入队列
       while(Q.head!=Q.tail)       //开始广度遍历精髓,当队列不为空时候表示还没有遍历完,可以看上图理解,当队列为空时候,说明已经遍历完
       {
         int u=GetQueue(Q);      //弹出队列中的第一个点,就是要找子顶点的点,看上图,队列中存储的是顶点在数组中的位置
         for(int w=findFirst(G,u);w>0;w=findNext(G,u,w))    //开始找其子顶点,和深度一样(调用的俩函数和深度一样,不重复写定义了)
         {
         visited[w]=true;       //遍历子顶点
         printf("%s",G.vex[w]);    //对子顶点数据处理
         EnQueue(Q,w);     //将子顶点入队列,看上图演示
       }
       }
      }
     } 
    }
    

    那么对一开始的图进行实例:
    在这里插入图片描述
    下面就为输出的结果,符合广度遍历,但是可能大家觉得有点偶然性,那么再举个例子:

    在这里插入图片描述
    这个是从网上随便找的例子,根据广度遍历,起始点为V0,根据广度遍历点的顺序大家可以先想一下,很简单,首先遍历的点肯定为V1 V2 V5,然后就是 V3 V4
    在这里插入图片描述
    那么就符合了广度遍历。

    最近发现了一个国外挺牛的网站,将所有数据结构都实现了可视化。你可以调节演示速度,有各种算法演示,比如什么查找之类,红黑树,什么都有。可能就是全英文,看不懂的可以用浏览器的翻译软件。地址如下:

    数据结构可视化

    展开全文
  • 导读:Graph kernel可以直观地理解为测量相似度的函数。它们允许如支持向量机之类的内核化学习算法直接在上工作,而不需要进行特征提取即可将其转换为固定长度的实值特征向量。个简...
  • 数据结构与算法必知基础知识

    千次阅读 多人点赞 2021-01-06 22:58:12
    数据结构与算法是程序员内功体现的重要标准之,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这个等式存在。各个中间件开发者,架构师他们都在努力的优化中间件、项目结构以及算法提高运行效率和降低...
  • 函数调用过程中的栈帧结构及其变化

    万次阅读 多人点赞 2018-04-28 02:34:42
    描述了栈帧的通用结构。栈帧是段有界限的内存区间,由最顶端的两个指针界定,寄存器%ebp为帧指针,而寄存器%esp为栈指针(也就是说寄存器%ebp保存了所分配内存的最高地址,寄存器%esp保存了所分配...
  • 镇文☆说在前面☆本章内容应该紧跟着第三章的知识整理发布的,但是中间出了点问题,所以鸽了。不定积分的公式你要说有多少,那是真的多。我在本教材的附录上找到了不定积分表,里面有140多个公式。最初我是打算...
  • 数据结构无向图简单路径

    千次阅读 2019-07-06 00:25:46
    数据结构无向图简单路径 .课程设计目的和要求 目的:锻炼学生对软件界面设计并进行实现的实践能力。 要求:(1)完成课程设计所给的所有功能。 (2)根据课程设计的特点设计出相应的画面。 二.课程设计环境 ...
  • 知识点总结-数据结构

    千次阅读 2018-12-19 23:34:51
    的基本概念和术语 1.之间的关系可以是任意的,任意两个数据元素之间都可能相关。 2.顶点:数据元素。 3.边or弧:从个顶点到另个顶点的路径。&lt;V, W&gt;表示弧,(V,W)表示边,V是弧尾,W...
  • 以sigmoid函数作为神经元的激励函数为例,这个大家可能稍微熟悉一点,毕竟我们逻辑回归部分重点提到了这个非线性的函数,把输入值压缩成0-1之间的个概率值。而通过这个非线性映射和设定的阈值,我们可以把空间切...
  • 学会参数传递机制,lambda表达式,函数式编程针不戳
  • 数据结构知识点汇总

    万次阅读 多人点赞 2018-07-18 15:44:21
    4、栈通常采用的两种存储结构是(线性存储结构和链表存储结构) 5、队列具有(先进先出)的特征,栈具有(后进先出)的特征。 6、链表(插入和删除不需要移动元素,但是无法随机访问任一元素) 7、循环链表的主要...
  • 《数据结构:c语言版》(严蔚敏)知识点整合

    万次阅读 多人点赞 2020-08-16 15:29:43
    数据结构是相互之间存在种或多种特定关系的数据元素的集合,《数据结构》让我认识到了各种数据结构在处理数据上的优缺点,理解掌握相关数据结构的具体操作,在结构的基础上添加好的算法,就能够更好的处理和利用...
  • 知识图谱架构(Knowledge Graph)

    万次阅读 多人点赞 2020-04-07 16:10:57
    开始的Google搜索,到现在的聊天机器人、大数据风控、证券投资、智能医疗、自适应教育、推荐系统,无不跟知识图谱相关。它在技术领域的热度也在逐年上升。 本文以通俗易懂的方式来讲解知识图谱相关的知识、...
  • 编程小知识之 struct 构造函数(C#)

    千次阅读 2019-08-31 12:24:52
    本文简单介绍了 C# 中 struct 构造函数的一些知识~ struct(结构) 类型在 C# 中属于值类型(value type),其构造函数有一些限制: struct 有参构造函数中必须为所有成员(包括自动实现的属性,后面对于这点的说明从略)...
  • 、前言 本人目前研,研究方向为基于深度学习的图像分割,转眼间已接触深度学习快1年,研生活也即将结束,期间看了大量的英文文献,做了大量的实验,也算是对深度学习有了初步的了解吧。 二、激活函数介绍 2.1 ...
  • 《Generating Synthetic Decentralized Social ...为了解决第个问题,我们需要定义个目标函数,其优化将导致结构信息的保存。回想一下,社交网络中最重要的信息之是它的社区结构。因此,希望确保具有相似...
  • 从今天开始,我将正式开启个新的打卡专题——【数据结构·水滴计划】,没错!这是今年上半年的整个系列计划!本专题目的是通过百天刷题计划,通过题目和知识点串联的方式,刷够1000道题!完成对数据结构相关知识...
  • 来自:Microstrong本文概览:1. 卷积背景和基本框架1.1 算法介绍我们都知道在数据结构中,种基础且常用的结构。现实世界中许多场景可以抽象为图结构,如社交网络、交...
  • 2018山西专升本数据结构知识点总结

    万次阅读 多人点赞 2018-06-29 19:41:36
    2018山西专升本数据结构知识点总结
  • ffmpeg.c函数结构简单分析(画图)

    万次阅读 多人点赞 2014-10-04 00:12:40
    前一阵子研究转码的时候看了FFmpeg的源代码。由于ffmpeg.c的代码相对比较长,而且其中有相当部分是AVFilter有关的代码(这...先说明一下自己画的结构图的规则:中仅画出了比较重要的函数之间的调用关系。粉红色的
  • 零基础要学会的15个常用函数

    千次阅读 2021-07-23 03:36:24
    这些函数是最基本的,但应用面却非常广,学会这些基本函数可以让工作事半功倍...统计个单元格区域:=sum(A1:A12)统计多个单元格区域:=sum(A1:A12,B1:B12)************2、AVERAGE虽然Average是个统计函数,但使...
  • 来自:Microstrong本文概览:1. 卷积背景和基本框架1.1 算法介绍我们都知道在数据结构中,种基础且常用的结构。现实世界中许多场景可以抽象为图结构,如社交网络、交...
  • . DeepDive DeepDive (http://deepdive.stanford.edu/) 是斯坦福大学开发的信息抽取系统,能处理文本、表格、图表、图片等多种格式的无结构数据,从中抽取结构化的信息。系统集成了文件分析、信息提取、信息整合...
  • C++函数模板(模板函数)详解

    万次阅读 多人点赞 2019-07-04 16:03:01
    C++函数模板(模板函数)详解定义用法:函数模板的原理延申用法2.1为什么需要类模板2.2单个类模板语法2.3继承中的类模板语法案例1:案例2:2.4类模板的基础语法2.5类模板语法知识体系梳理1.所有的类模板函数写在类的...
  • 考研数据结构知识点汇总

    千次阅读 多人点赞 2019-10-24 16:24:49
    章 1.数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被...5.数据结构:指互相之间存在着种或多种特定关系的数据元素的集合。包括逻辑结构,存储结构和对数据的运算。(数据元素都不...
  • Kotlin系列之扩展函数

    万次阅读 2018-04-17 00:22:18
    简述: 今天带来的是Kotlin浅谈系列的第五弹,这讲主要是讲利用Kotlin中的扩展函数特性让我们的代码变得更加简单和整洁。扩展函数是Kotlin语言中独有的新特性,利用它可以减少很多的样板代码,大大提高开发的效率;...
  • 《算法和数据结构》题海战术篇

    万次阅读 多人点赞 2021-07-15 06:13:43
    刷了 3333 题 算法题 后的点点经验总结 —— 题不是这么刷的!
  • 知识图谱】知识图谱的基础概念与构建流程

    千次阅读 多人点赞 2019-11-09 18:46:49
    目录 1、引言 2、知识图谱的定义 3、知识图谱的架构 3.1知识图谱的逻辑结构 3.2知识图谱的体系架构 ...4、代表性知识图谱库 ...5、知识图谱构建的关键技术 ...我们专知的技术基石之正是知识图谱-构建AI知识体系-专...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 252,211
精华内容 100,884
关键字:

一次函数的知识结构图简单