1、创建无向图的邻接表存储结构 2、完成图的深度优先遍历 3、完成图的广度优先遍历实验目的

实验目的：

1. 熟悉图的基本概念和相关术语。
2. 掌握图的邻接表存储结构及其基本操作。
3. 掌握图的深度优先遍历和广度优先遍历算法及其实现。

实验内容：

1. 创建无向图的邻接表存储结构。

无向图的邻接表存储结构包含两个部分：一个顶点表和一个边表。顶点表用于存储图中所有的顶点，边表用于存储图中所有的边。

顶点表包含两个字段：顶点编号和顶点名称。边表包含三个字段：起始顶点编号、终止顶点编号和边的权值。

具体实现代码如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 100010
#define MAXM 100010
#define INF 0x3f3f3f3f
using namespace std;

struct Edge{
    int v,next;
}e[MAXM<<1];

int head[MAXN],cnt;

void addEdge(int u,int v){
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

int main(){
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    return 0;
}

2. 完成图的深度优先遍历。

深度优先遍历（DFS）是一种用于遍历或搜索树或图的算法。在搜索过程中，从起点开始，沿着一条路径走到底，然后回溯到上一个节点，再沿着另一条路径继续走到底，直到所有节点都被访问。DFS算法通常使用递归实现。

具体实现代码如下：

bool vis[MAXN];

void dfs(int u){
    vis[u]=1;
    printf("%d ",u);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].v;
        if(!vis[v]) dfs(v);
    }
}

int main(){
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(1);
    return 0;
}

3. 完成图的广度优先遍历。

广度优先遍历（BFS）是一种用于遍历或搜索树或图的算法。在搜索过程中，从起点开始，按照层次顺序逐层扩展，直到找到目标节点或遍历完所有节点。BFS算法通常使用队列实现。

具体实现代码如下：

bool vis[MAXN];

void bfs(int s){
    queue<int> q;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        printf("%d ",u);
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].v;
            if(!vis[v]){
                vis[v]=1;
                q.push(v);
            }
        }
    }
}

int main(){
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    bfs(1);
    return 0;
}