dfs和bfs算法邻接表

### DFS 和 BFS 算法在邻接表表示的图中的实现

#### 深度优先搜索 (DFS)

对于深度优先搜索，在邻接表表示的图中，可以通过递归或显式使用栈来实现。此方法适用于有向图和无向图。

void DFS(ALGraph G, int v) {
    cout << "Visit node: " << v;
    visited[v] = true;

    EdgeNode* p = G.vertices[v].firstedge;
    while(p != NULL){
        int w = p->adjvex;
        if(!visited[w]){
            DFS(G,w);
        }
        p = p->next;
    }
}

为了初始化并调用上述函数：

void DFSTraverse(ALGraph &G) {
    memset(visited,false,sizeof(visited));
    
    for(int i=0;i<G.vexnum;++i){
        if (!visited[i]) {
            DFS(G,i);  
        }
    }
}

这段代码展示了如何遍历整个图，即使存在不连通的部分[^1]。

#### 广度优先搜索 (BFS)

广度优先搜索则通常借助队列完成层次化探索的任务。同样地，这里也给出基于C++语言的一个简单例子:

void BFS(ALGraph G,int v) {
    queue<int> q;
    q.push(v);

    memset(visited,false,sizeof(visited));
    visited[v]=true;

    while(!q.empty()){
        int u=q.front();
        q.pop();

        cout<<"Visit node:"<<u<<endl;

        EdgeNode *p=G.vertices[u].firstedge;
        while(p!=NULL){
            int w=p->adjvex;
            if(!visited[w]){
                q.push(w);
                visited[w]=true;
            }
            p=p->next;
        }
    }
}

void BFSTraverse(ALGraph& G) {
    memset(visited,false,sizeof(visited));

    for(int i=0;i<G.vexnum;++i){
        if(!visited[i]){
            BFS(G,i);
        }
    }
}

通过这种方式，可以逐层访问所有可达节点，并记录下它们被首次发现的时间戳等信息。

这两种算法都可用于解决多种实际问题，比如寻找最短路径、检测环路以及构建最小生成树等问题。当处理大规模数据集时，选择合适的策略尤为重要——DFS适合于求解具有较深嵌套结构的问题；而BFS更适合用于计算两点间距离或者查找最近公共祖先等情况。