上课笔记【邻接表】

复仇者_零

2024-11-09 20:32:02

发布于：浙江

12阅读

0回复

0点赞

邻接表遍历方式

深度优先搜索的遍历方式

dfs遍历邻接矩阵从a走到b的路径

bool vis[MAXN]; // 标记是否访问过
int mp[MAXN][MAXN]; // 邻接矩阵
int a,b;
void dfs(int it) // it表示当前访问的节点
{
    vis[it] = true; // 标记当前节点为已访问
    if(it==b){
        cout << true << endl;    
        return ;
    }

    // 邻接矩阵查询遍历当前节点的相邻节点
    for(int i=1;i<=n;i++){
        if(mp[it][i] &&!vis[i]){ // 相邻节点未访问过
            dfs(i); // 递归访问相邻节点
        }
    }// 时间复杂度为O(n)
}

dfs遍历邻接表从a走到b的路径

bool vis[MAXN]; // 标记是否访问过
vecotr<int> mp[MAXN]; // 邻接表

void dfs(int it) // it表示当前访问的节点
{
    vis[it] = true; // 标记当前节点为已访问
    if(it==b){
        cout << true << endl;    
        return ;
    }

    // 邻接表查询遍历当前节点的相邻节点
    for(int i=0;i<mp[it].size();i++){
        if(!vis[mp[it][i]]){ // 相邻节点未访问过
            dfs(mp[it][i]); // 递归访问相邻节点
        }
    }
}

邻接表和邻接矩阵查询效率区别

//邻接矩阵遍历方式
for(int i=1;i<=n;i++){ // 遍历所有节点  
        if(mp[it][i] &&!vis[i]){ // 相邻节点未访问过
            dfs(i); // 递归访问相邻节点
        }
    }// 时间复杂度为O(n)


// 邻接表查询遍历当前节点的相邻节点
    for(int i=0;i<mp[it].size();i++){
        if(!vis[mp[it][i]]){ // 相邻节点未访问过
            dfs(mp[it][i]); // 递归访问相邻节点
        }
    } // 时间复杂度为O(m)

广度优先搜索的遍历方式

bfs遍历邻接矩阵从a走到b的路径


bool vis[MAXN]; // 标记是否访问过
int mp[MAXN][MAXN]; // 邻接矩阵
int a,b;
void bfs(){
    queue<int> q; // 队列
    q.push(a); // 起始节点入队
    vis[a] = true; // 标记起始节点为已访问
    while(!q.empty()){
        int it = q.front(); // 取出队首节点
        q.pop(); // 队首出队
        if(it==b){
            cout << true << endl;    
            return ;
        }
        // 邻接矩阵查询遍历当前节点的相邻节点
        for(int i=1;i<=n;i++){ // O(n)
            if(mp[it][i] &&!vis[i]){ // 相邻节点未访问过
                q.push(i); // 相邻节点入队
                vis[i] = true; // 标记相邻节点为已访问
            }
        }
    }
}

bfs遍历邻接表从a走到b的路径

bool vis[MAXN]; // 标记是否访问过
vecotr<int> mp[MAXN]; // 邻接表

void bfs(){
    queue<int> q; // 队列
    q.push(a); // 起始节点入队
    vis[a] = true; // 标记起始节点为已访问
    while(!q.empty()){
        int it = q.front(); // 取出队首节点
        q.pop(); // 队首出队
        if(it==b){
            cout << true << endl;    
            return ;
        }
        // 邻接表查询遍历当前节点的相邻节点
        for(int i=0;i<mp[it].size();i++){ // O(m)
            if(!vis[mp[it][i]]){ // 相邻节点未访问过
                q.push(mp[it][i]); // 相邻节点入队
                vis[mp[it][i]] = true; // 标记相邻节点为已访问
            }
        }
    }
}