图的遍历(dfs,bfs)

图的遍历：用深度搜索

//输入
5 5
1 2
1 3
1 5
2 4
3 5

#include<bits/stdc++.h>
using namespace std;

int e[101][101];
int book[101];
int sum=0;
int n;

void dfs(int cur)
{
    printf("%d ",cur);
    sum++;
    if(sum == n)return;
    for(int i = 1; i <= n; i++)
    {
        if(e[cur][i]==1 && book[i]==0)
        {
            book[i] = 1;
            dfs(i);
        }
    }
    return;
}

int main()
{
    int m,a,b;
    //有几个点，有几条边
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            if(i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999;
        }
    
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d", &a, &b);
        e[a][b] = 1;
        e[b][a] = 1;
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            printf("%d ", e[i][j]);
        }    
        printf("\n");
    }
    
    book[1] = 1;
    dfs(1);
    
    return 0;
}

//输出
1 2 4 3 5

图的遍历：用广度搜索

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n, m;
    int e[101][101];
    int book[101]={0};
    int a, b;
    int que[10001];
    int cur;
    scanf("%d %d", &n, &m);
    //初始化二维数组
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            if(i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999;
        }
    
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d", &a, &b);
        e[a][b] = 1;
        e[b][a] = 1;
    }
    
    // for(int i = 1; i <= n; i++)
    // {
    //     for(int j = 1; j <= n; j++)
    //     {
    //         printf("%d ", e[i][j]);
    //     }    
    //     printf("\n");
    // }    
    
    int head = 1;
    int tail = 1;
    que[tail] = 1;
    tail++;
    book[1] = 1;
    
    while(head < tail)
    {
        cur = que[head];
        for(int i = 1; i <= n; i++)
        {
            if(e[cur][i] == 1 && book[i] == 0)            
            {
                que[tail] = i;
                tail++;
                book[i] = 1;
            }
            
            if(tail > n)
            {
                break;
            }
        }
        head++;
    }
    for(int i = 1; i < tail; i++)
        printf("%d ",que[i]);
 
    return 0;
}

//输出
1 2 3 5 4

城市地图-图的深度优先遍历

有5个城市，8条路，通过邻接矩阵存储相关信息，用深度优先去遍历

//输入数据
5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3

#include<bits/stdc++.h>
using namespace std;

int minValue = 99999999;
int e[101][101];
int book[101];
int n;

void dfs(int cur, int dis)
{
    if(dis > minValue)return;
    if(cur == n)
    {
        if(dis < minValue)minValue = dis;
        return;
    }
    
    for(int j = 1; j <= n; j++)
    {
        if(e[cur][j] != 99999999 && book[j] == 0)
        {
            book[j] = 1;
            dfs(j, dis+e[cur][j]);
            book[j] = 0;
        }
    }
    return;
}

int main()
{
    int m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            if(i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999;
        }
    
    int a,b,c;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        e[a][b] = c;
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            printf("%d ", e[i][j]);
        }    
        printf("\n");
    }    
    
    book[1] = 1;
    dfs(1,0);
    printf("%d",minValue);
    return 0;
}

有向图矩阵是不对称的，无向图矩阵是对称的

#include <bits/stdc++.h>
using namespace std;

struct note
{
    int x;
    int s;
};


int main()
{
    struct note que[2501];
    int e[51][51]={0}, book[51]={0};
    int head, tail;
    int n, m, start, end;
    scanf("%d%d%d%d", &n, &m, &start, &end);
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            if(i == j)
            {
                e[i][j] = 0;
            }
            else
            {
                e[i][j] = 99999999;
            }
        }
    
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        e[a][b]= 1;
        e[b][a]= 1;
    }
    
    printf("%d %d %d %d\n", n, m, start, end);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            printf("%d\t",e[i][j]);
        }    
        printf("\n");    
    }
    
    head = 1;
    tail = 1;
    
    que[tail].x = start;
    que[tail].s = 0;
    tail++;
    book[start]=1;
    int flag = 0;
    
    
    
    while(head < tail)
    {
        //for(int p = 1; p < tail; p++)printf("que is %d \n",que[p].x);
        int cur = que[head].x;
        for(int j = 1; j <= n; j++)
        {
            if(e[cur][j] != 99999999 && book[j] == 0)
            {
                que[tail].x = j;
                que[tail].s = que[head].s+1;
                tail++;
                book[j] = 1;
            }
            
            if(que[tail].x == end)
            {
                flag = 1;
                break;
            }
        }
        if(flag == 1)
            break;
        head++;
    }
    
    printf("%d",que[tail-1].s);
    return 0;
}

Continue…