图的建立与遍历c++代码

以下是建立和遍历图的C++代码示例：

建立图：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int head[maxn],nxt[maxn<<1],ver[maxn<<1],idx;
int n,m;
void add(int x,int y)
{
    ver[++idx]=y;
    nxt[idx]=head[x];
    head[x]=idx;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);//如果是无向图，还要加入反向边
    }
    return 0;
}

遍历图：

深度优先搜索（DFS）：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int head[maxn],nxt[maxn<<1],ver[maxn<<1],tot;
int n,m;
bool vis[maxn];
void add(int x,int y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void dfs(int x)
{
    vis[x]=true;
    //遍历x的所有出边
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(!vis[y])
            dfs(y);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);//如果是无向图，还要加入反向边
    }
    dfs(1);//从节点1开始遍历
    return 0;
}

广度优先搜索（BFS）：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int head[maxn],nxt[maxn<<1],ver[maxn<<1],tot;
int n,m;
bool vis[maxn];
void add(int x,int y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void bfs(int x)
{
    queue<int> q;
    q.push(x);
    vis[x]=true;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        //遍历u的所有出边
        for(int i=head[u];i;i=nxt[i])
        {
            int v=ver[i];
            if(!vis[v])
            {
                q.push(v);
                vis[v]=true;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);//如果是无向图，还要加入反向边
    }
    bfs(1);//从节点1开始遍历
    return 0;
}