深度优先遍历和广度优先遍历参考文章
邻表的数据结构定义
类型结构链接节点{ int index； LinkNode *next； } LinkNode，*LNode； 类型描述符{ delemtypedata； LinkNode *first； } TableNode； typedefstructadjlist { tablenodet [ maxsize ]； bool visted[MaxSize]； } adj列表； 1 .深度优先遍历(DFS-Depth First Search )构想：从一个节点出发，访问邻居(如果邻居没有访问过)
如果邻居被访问了，回到前面的顶点，继续访问前面顶点的邻居
重复步骤1和2，直到访问了所有顶点
二叉树的前序扫描也是深度优先扫描的思想
递归实现-实际上是堆栈//递归方法的实现--实质上是堆栈boolDFS(adjlistadj，int index ) /当前节点printf )、Adj.T[index].data； Adj.visted[index]=true； //访问当前节点的邻居for (lnode pre=adj.t [ index ].first； pre！=NULL； pre=pre-next(//如果当前节点的邻居没有访问过，则递归地使用if (adj.visted [ pre-index ]==false ) {DFS ) adj，pre-index； } }返回真； }手动创建堆栈//堆栈方法以创建boolDFS_stack(adjlistadj，int index ) { stackint s； s.push (索引)； //在出发顶点堆栈while (！ s.empty () { int i=s.top； //堆栈顶部索引值bool result=false； //标记邻居是否已全部访问，true中还未访问的邻居if(adj.visted[I]==false ) /如果顶点未访问) { Adj.visted[i]=true； printf('%d '，Adj.T[i].data )； //遍历当前顶点的邻居，如果存在未访问的邻居，则退出将邻居的下标索引添加到堆栈顶部并查找邻居的步骤//result=true； 此外，标记邻居没有访问for (lnode cur=adj.t [ I ].first； cur！=NULL； cur=cur-next(if ) adj.visted[cur-index]==false ) s.push ) cur-index )； 结果=true； 布雷克； (//如果邻居访问过，则堆栈顶部元素if(result==false ) { s.pop )； }printf () (n )； 返回真； )2)广度优先遍历(BFS-Breadth First Search )的思路类似于二叉树的层次遍历，使用队列实现
如果出发点入伍先头要素未被访问，则在访问先头的所有邻居中，如果有被访问的邻居，则重复入伍先头部队2、3直到队伍排空
队列实现//宽遍历，队列为//breadthfirstsearchboolbfs (adjlistadj，int index ) { queueint q； q .推送(索引)； //出发点是while (进入)！ q.empty () /如果团队领导没有访问过，则if (adj.visted (q.front ) ) ]==false ) ) printf('%d '，adj.t ) q.front for (lnode cur=adj.t [ q.front (].first； cur！=NULL； cur=cur-next(//如果邻居没有访问过，则进入团队
if (Adj.visted[cur->index] == false) { q.push(cur->index); } } } //队头出队 q.pop(); } return true;} DFS测试 BFS测试 全部代码 #include <iostream>#include <stack>#include <queue>using namespace std;#define DElemType int#define MaxSize 8typedef struct LinkNode{ int index; LinkNode *next;} LinkNode, *LNode;typedef struct TableNode{ DElemType data; LinkNode *first;} TableNode;typedef struct AdjList{ TableNode T[MaxSize]; bool visted[MaxSize];} AdjList;//初始化已访问列表bool InitAdjList(AdjList &Adj){ for (int i = 0; i < MaxSize; i++) { Adj.visted[i] = false; } return true;}//创建邻接表，链表插入方式为不带头节点的尾插方式bool CreateAdjList(AdjList &Adj){ for (int i = 0; i < MaxSize; i++) { LNode cur; //指向链表中最后一个节点 cin >> Adj.T[i].data; Adj.T[i].first = NULL; while (true) { if (cin.get() == 'n') { break; } LNode N = new LinkNode; cin >> N->index; N->next = NULL; if (Adj.T[i].first == NULL) //不带头节点的链表 { Adj.T[i].first = N; cur = N; } else { cur->next = N; cur = N; } } } return true;}//遍历邻接表void visit(AdjList Adj){ printf("-----------n"); for (int i = 0; i < MaxSize; i++) { cout << Adj.T[i].data << " "; for (LNode cur = Adj.T[i].first; cur != NULL; cur = cur->next) { cout << cur->index << " "; } cout << endl; } printf("-----------n");}//递归方法实现--实质上也是栈//Depth First Searchbool DFS(AdjList &Adj, int index){ //访问当前节点 printf("%d ", Adj.T[index].data); Adj.visted[index] = true; //访问当前节点的邻居 for (LNode pre = Adj.T[index].first; pre != NULL; pre = pre->next) { //如果邻居没有访问过的话，则递归访问 if (Adj.visted[pre->index] == false) { DFS(Adj, pre->index); } } return true;}//栈方法实现bool DFS_stack(AdjList Adj, int index){ stack<int> s; s.push(index); //出发顶点进栈 while (!s.empty()) { int i = s.top(); //去栈顶索引值 bool result = false; //定义邻居是否都已经访问完，true还有没访问的邻居 if (Adj.visted[i] == false) //如果顶点没有访问则访问 { Adj.visted[i] = true; printf("%d ", Adj.T[i].data); } //遍历当前顶点的邻居，如果存在没被访问过的，则把邻居的下标索引加入栈顶，退出找邻居的步骤 //result = true;标记还有邻居没访问 for (LNode cur = Adj.T[i].first; cur != NULL; cur = cur->next) { if (Adj.visted[cur->index] == false) { s.push(cur->index); result = true; break; } } //如果邻居都被访问过，则取出栈顶元素 if (result == false) { s.pop(); } } printf("n"); return true;}//广度遍历，队列实现//Breadth First Searchbool BFS(AdjList Adj, int index){ queue<int> q; q.push(index); //出发点入队 while (!q.empty()) { //如果队头没有访问过的话，则访问 if (Adj.visted[q.front()] == false) { printf("%d ", Adj.T[q.front()].data); Adj.visted[q.front()] = true; for (LNode cur = Adj.T[q.front()].first; cur != NULL; cur = cur->next) { //如果邻居没有被访问过，则进队 if (Adj.visted[cur->index] == false) { q.push(cur->index); } } } //队头出队 q.pop(); } return true;}int main(){ /*1 1 42 0 53 3 5 64 2 6 75 06 1 2 67 2 3 5 78 3 6 */ AdjList Adj; InitAdjList(Adj); CreateAdjList(Adj); visit(Adj); // DFS(Adj, 1); // InitAdjList(Adj); // printf("n"); // DFS_stack(Adj, 2); // InitAdjList(Adj); BFS(Adj, 0);}