樱桃季——用深度优先算法如何吃樱桃
深度优先遍历算法
1
深度优先搜索
Depth First Search（简称DFS）
首先访问出发点v，并且标记
选取与v相邻未被访问的点w，访问且标记
再选取与v相邻未被访问的顶点，访问且标记
循环反复到一个顶点的相邻顶点都被访问，依次退回最近被访问的顶点
类似树的先序遍历
将樱桃所在的分支抽象为ABCDE
接下来从A所在的分支开始吃樱桃
按深度优先继续吃D所在分支的樱桃
按深度优先选择E分支
E已经到底回到D层次的C或则B继续，这里我选择C
最后访问B
2
算法思想—递归
链式存储结构——邻接表
typedef struct ArcNode{int adjvex;//边指向结点的位置struct ArcNode *nextarc;//下一条边的指针int info;}ArcNode;typedef struct{char data;//顶点数据ArcNode *firststartc;//指向第一条边的指针}VNode;typedef struct{VNode adjlist[maxsize];//邻接表int n,e;//顶点数和边数}AGraph;
算法设计
int visit[maxsize]={0};//访问顶点标记数组，全为0表示未访问void DFS(AGraph *G,int v)//DFS传入结点位置{ArcNode *p;//visit[v]=1;//1为访问cout<<G->adjlist[v].data<<" ";//访结点数据p=G->adjlist[v].firststartc;//指向第一条边的指针while(!p){if(!visit[p->adjvex])//为0，没有访问{DFS(G,p->adjvex);//递归进入函数继续访问p=p->nextarc;//往后走，下一个结点}}}//邻接表的存储时间复杂度O(n)
CSDN：yma16
数据结构框架学习