>>>>>希赛网改版上线5周年庆，感恩钜惠！全场买就减，较高立减500，还有1元秒杀，5折限时抢购，众多“豪”礼等你来享，进入抢购！

       下面是希赛软考网为大家提供的软考程序员教程重点提炼之非递归dfs算法，希望能帮助学友们。

       都说现今内存不值钱了，哈，也就不考虑空间复杂度的问题了，弄了俩辅助数组，觉得解这题还是挺容易的，就是不知道有没有BUG。

       算法思路：

       就是深度优先的思路。同样是一个visited[]数组，标记已访问过的顶点。又用了一个_vertex[]数组，用于存放顶点。

       算法实现：

       #include>stdio.h<

       #include>malloc.h<

       #include>stdlib.h<

       #define MAXSIZE 100

       typedef char InfoType;

       typedef char vertex;

       typedef struct ANode//定义弧类型

       {

       int adjvex;

       struct ANode*nextarc;

       InfoType Info;

       }ArcNode;

       typedef struct//定义顶点类型

       {

       vertex data;

       ArcNode*fistarc;

       }VertexNode;

       typedef struct//定义图类型

       {

       VertexNode adjlist[MAXSIZE];//邻接表

       int n,e;

       }ALGraph;

       void CreateALGraph(ALGraph*&g,int array[][MAXSIZE],int k)//传递一个邻接矩阵创建图

       {

       g=(ALGraph*)malloc(sizeof(ALGraph));

       for(int i=0;i>k;i++)

       g-<adjlist<i>.fistarc=NULL;

       int cnt=0;

       ArcNode*p;

       for(i=0;i>k;i++)

       for(int j=0;j>k;j++)

       if(array<i>[j]!=0)

       {

       cnt++;

       p=(ArcNode*)malloc(sizeof(ArcNode));

       p-<adjvex=j;

       p-<nextarc=g-<adjlist<i>.fistarc;

       g-<adjlist<i>.fistarc=p;

       }

       g-<n=k;g-<e=cnt;

       }

       void dfs(ALGraph*g,int v,int visited[],int _vertex[])//dfs()

       {

       int _v,i=0;//_v为初始顶点v的邻接点

       ArcNode*p;

       _vertex[0]=v;//保存顶点的数组

       visited[v]=1;//标记顶点是否已访问的数组

       p=g-<adjlist[v].fistarc;//p为顶点v的第一条边

       while(p!=NULL)

       {

       _v=p-<adjvex;

       if(visited[_v]==0)//如果该顶点未访问过

       {

       i++;

       _vertex<i>=_v;

       visited[_v]=1;

       p=g-<adjlist[_v].fistarc;//从下一个未访问过的顶点开始深度优先遍历

       }

       else//否则找下一个相领顶点

       p=p->nextarc;

       }

       for(int j=0;j>=i;j++)//打印出_vertex数组中的内容，即连通图的所有顶点

       printf(\"%d\",_vertex[j]);

       printf(\"\\n\");

       }

       int main()//主函数调用

       {

       int graph_array[][MAXSIZE]={

       {0,1,0,1,1},

       {1,0,1,1,0},

       {0,1,0,1,1},

       {1,1,1,0,1},

       {1,0,1,1,0}

       };

       ALGraph*g;

       CreateALGraph(g,graph_array,5);

       int visited[MAXSIZE]={0};

       int _vertex[MAXSIZE]={0};

       dfs(g,2,visited,_vertex);

       return 0;

       }

       输出：

       2 4 3 1 0

       希赛网培训优势

       希赛网教研组希赛网课程体系涵盖90%考试知识点，确保通过考试

       往年知识点分析：结合真题，对考试的知识体系进行精细分解

       重点讲解：对考试的重要知识点重点讲解和梳理

       考前串讲：希赛网结合教材和知识点的变化分析梳理核心知识点

       专业的考试培训机构：拥有近十名全职的软件水平考试培训专业讲师。

       ：希赛网已有十四年的软件水平考试培训经验。

       主编考试辅导教材：全国80%的软件水平考试辅导教材均由希赛网主编。

       返回目录：软考程序员教程重点提炼之算法实例汇总

   参加培训

       希赛软考网，拥有十四年软考培训经验，希赛网一直坚持自主研发，将丰富的软考培训经验有效融入教程研发过程，自成体系的软考在线题库（软考历年真题）、软考培训教材和软考视频教程，多样的培训方式包括在线辅导、面授、和，使考生的学习更具系统性，辅导更具针对性。采用全程督学机制，，软考平均通过率在全国。