图的遍历

邻接矩阵

/*
第一行输入n m代表结点个数和边的个数
下面m行分别输入a b x代表ab之间有权值为x的路径
*/

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn = 100; 
int mp[maxn][maxn];//二维数组表示邻接矩阵
int vis[maxn];

// 初始化
void init()
{
    for(int i = 0;i<maxn;i++)
    {
        vis[i] = 0;
    }
}
// 利用邻接矩阵存储无向图

// 访问当前结点为x 深度遍历
void dfs(int x)
{
    cout << x << " ";
    vis[x] = 1;// 代表已经访问
    for(int i = 0;i<n;i++)
    {
        // 这里需要注意的是这个i和x的关系 别写错了是<x,i>
        if(mp[x][i]!=0 && vis[i]==0) // 存在路径 且未访问
        {
            dfs(i);// 然后深度遍历该结点的邻居
        }
    }
}

// 根据这个结点进行广度搜索
// 再次基础上 可以具体算出来和源点的距离
// 也可每次pop队列中的所有元素 这样就可以求出每一层的具体结点数
void bfs(int root)
{
    init();
    queue<int>q;
    q.push(root);
    vis[root] = 1;
    int d[maxn];//代表和源点的距离
    d[root] = 0;//自身和自身距离为0
    while(!q.empty())
    {
        int front = q.front();
        q.pop();
        cout << front <<" " << d[front] <<"\n";
        for(int i = 0;i<maxn;i++)
        {
            if(mp[front][i] != 0 && vis[i] == 0)// 当前结点存在通路 且未访问
            {
                q.push(i);
                d[i] = d[front] + 1;//比他的发源地多一个距离
                vis[i] = 1;
            }
        }
    }
}

int main()
{
    cin >> n >> m;//代表点的个数和边的个数
    for(int i = 0;i<m;i++)
    {
        int a,b,x;
        cin >> a >> b >> x;
        mp[a][b] = x;
        mp[b][a] = x;
    }
    init();
    dfs(0);
    bfs(0);
    return 0;
}
/*
6 8
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1 
3 2 2
3 4 3
4 5 3
*/

邻接表

/*
第一行输入n m代表结点个数和边的个数
下面m行分别输入a b x代表ab之间有权值为x的路径
*/

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int inf = 0x3fffffff;
const int maxn = 100; 
int vis[maxn];
/*
利用邻接表来建立图 从而实现Bell-Ford

*/
struct Node{
    int id;
    int val;// 因为这里虽然是一个结点 但是是头节点指向该结点 存在边权
    // 因为邻接表的实际含义是存储邻居的 故而彼此的弧也很好判断
    Node* next;
    Node(int _id,int _val) : id(_id),val(_val),next(NULL){}
};
Node *head[maxn];// 这里建立的是头节点顺序存储的 里面每一个对象是其邻居结点
// 而head[i]代表的是结点i的头指针 每次增加完元素 指针也会变化 

// 结点ab之间增加一个权值为x的边 作为无向图 应该是彼此的邻居
void add(int a,int b,int x)
{
    Node * p = new Node(b,x);
    p->next = head[a];//采用头插法 里面的顺序和插入的相同
    head[a] = p;

    Node *q = new Node(a,x);// 无向图 边是双向的
    q->next = head[b];
    head[b] = q;
}

// 根据邻接矩阵 深层遍历
void DFS(int v){

    cout << v;
    vis[v] = 1;
    // 遍历v的邻居
    Node *p = head[v];
    while(p!=NULL){
        int nw = p->id;
        if(vis[nw]==0){

            DFS(nw);
        }
        p = p->next;
    }
}

int main()
{
    cin >> n >> m;//代表点的个数和边的个数
    for(int i = 0;i<m;i++)
    {
        int a,b,x;
        cin >> a >> b >> x;
        add(a,b,x);
    }
    DFS(0);
    return 0;
}
/*
6 8
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1 
3 2 2
3 4 3
4 5 3
*/