邻接矩阵

优先访问小编号结点的顺序遍历并输出该图，比较轻松实现这个要求

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

//邻接矩阵
const int N=1010,M=N*N; //稠密图

int n,m;
int g[N][N];
//g[i][j]表示i到j的一条有向边
//边无权时，g[i][j]=1表示有边，g[i][j]=0表示无边
//边有权时，g[i][j]表示权重，g[i][j]=0x3f3f3f3f表示无边，初始化memset(g,0x3f,sizeof g)
bool st[N];

void dfs(int u){
    st[u]=true;
    printf("%d ",u);

    //注意if语句的意思 有边并且i点没有遍历过
    for(int i=1;i<=n;i++)
        if(g[u][i]&&!st[i]) dfs(i);
}

void bfs(){
    queue<int> q;
    q.push(1);

    st[1]=true;

    while(q.size()){
        int t=q.front();
        printf("%d ",t);
        q.pop();

        for(int i=1;i<=n;i++)
            if(g[t][i]&&!st[i]) {
                st[i]=true;
                q.push(i);
            }
    }
}

int main(){
    scanf("%d%d",&n,&m);

    //以无权重的无向图为例
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);

        g[x][y]=1;
        g[y][x]=1;
    }


    dfs(1);

    puts("");

    memset(st,false,sizeof st);

    bfs();

    return 0;
}

邻接表（用链表）

优先访问小编号结点的顺序遍历并输出该图，不是很好实现，需要先将边存起来，然后排序，然后逆序输入，
因为我们必须保证每个单链表是有序的，采用的是头插法故而这样做

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=1e5+10,M=1e6+10;

typedef pair<int,int> PII;

int n,m;
int h[N],e[M],ne[M],idx;
bool st[N];
PII g[M];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u){
    st[u]=true;
    printf("%d ",u);

    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]) dfs(j);
    }
}

void bfs(){
    queue<int> q;
    q.push(1);

    memset(st,false,sizeof st);
    st[1]=true;

    while(q.size()){
        int t=q.front();
        printf("%d ",t);
        q.pop();

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(!st[j]){
                st[j]=true;
                q.push(j);
            }
        }
    }
}

int main(){
    memset(h,-1,sizeof h);

    cin>>n>>m;

    int k=-1;
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);

        k++,g[k].first=a,g[k].second=b;
        k++,g[k].first=b,g[k].second=a;
    }

    sort(g,g+m);

    for(int i=2*m-1;i>=0;i--){
        add(g[i].first,g[i].second);
    } 

    dfs(1);

    puts("");

    bfs();

    return 0;
}

邻接表（用vector）

优先访问小编号结点的顺序遍历并输出该图，需要对g的每一行排序

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include <vector>

using namespace std;

const int N=1e5+10,M=1e6+10;

int n,m;
vector<vector<int>> g;
bool st[N];

void dfs(int u){
    st[u]=true;
    printf("%d ",u);

    for(int i=0;i<g[u].size();i++){
        int j=g[u][i];
        if(!st[j]) dfs(j);
    }
}

void bfs(){
    queue<int> q;
    q.push(1);

    memset(st,false,sizeof st);
    st[1]=true;

    while(q.size()){
        int t=q.front();
        printf("%d ",t);
        q.pop();

        for(int i=0;i<g[t].size();i++){
            int j=g[t][i];
            if(!st[j]) {
                st[j]=true;
                q.push(j);
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);

    g.resize(n+1);

    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);

        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());

    dfs(1);

    puts("");

    bfs();

    return 0;
}

直接存边

使用一个数组来存边，数组中的每个元素都包含一条边的起点与终点（带边权的图还包含边权）。（或者使用多个数组分别存起点，终点和边权。）在 Kruskal 算法 中，由于需要将边按边权排序，需要直接存边。