新手小白必看 -- vector 和 链式前向星 存无权图

学习数据结构有两种常见的 邻接表 和 矩阵，矩阵太费空间， 表写起来很复杂
vector 优点：动态内存管理, 更节省空间
vector 的写法, 直接背模板就好啦

/*
    vector 无权无向图 
    4 4
    1 4
    4 2
    2 3
    3 1

    DFS(1);  结果 1 4 2 3
*/
#include<bits/stdc++.h>
using namespace std;

vector<int> v[105];  // 这里vector 实际上是一个动态二维数组
int vis[105];  // 遍历用的数组

void DFS(int start) {  // 递归
    cout << start << " ";
    vis[start] = 1;
    for ( int i = 0; i < v[start].size(); i++ ) {
        if ( vis[v[start][i]] == 0 ) {
            DFS(v[start][i]);
        }
    }
    return ;
}

int main() 
{
    int n, m;   // n:节点个数  m:边数
    cin >> n >> m;

    for ( int i = 1; i <= m; i++ ) {
        int a, b;
        cin >> a >> b;  // 输入两个点连接的边, 以 a 为结点, b 为边
        v[a].push_back(b);
        v[b].push_back(a);  // 存无向图是, 需要把 b 连接到 a, 如果是存有向图, 删除这句
    }
    return 0;
}

前向星与 vector 相比， 空间优于 vector ， 代码复杂度相似

前向星的写法 (前向星和 vector 都是邻接表的简化版, 在遇到图得问题是，从空间方面考虑，建议使用前向星, 因为vector 在申请内存时是默认开两倍的空间)

/*
    前向星 无权无向图  + DFS

    前向星就相当于是优化过后的 邻接表
*/
#include<bits/stdc++.h>
using namespace std;

int vis[105];  // 

struct node {
    int to, next;  // to : 边    //next : 指针
}p[105];

int tot = 1, head[105];  // 头节点， tot : 插入结点
void insert( int u, int v) {  // u : 结点     v : 边
    p[tot].to = v;
    p[tot].next = head[u];
    head[u] = tot++;
}

void DFS(int start){
    vis[start] = 1;
    cout << start << " ";
    for(int i = head[start];i != -1 ; i = p[i].next){
        if(!vis[p[i].to])
            DFS(p[i].to);
    }
}

int main() 
{
    memset(head,-1,sizeof(head));
    int n, m;   // 节点个数， 边数
    cin >> n >> m;
    for ( int i = 1; i <= m; i++ ) {
        int a, b; cin >> a >> b;
        insert(a,b);
        insert(b,a);
    }
    DFS(1);

    return 0;
}