数据结构---图论

2019-11-20   数据结构

SDUT OJ 题解

数据结构实验之图论一:基于邻接矩阵的广度优先搜索遍历

深度优先遍历:类似与树的前序遍历。从图中的某个顶点v出发,访问此顶点,然后从v的未被访问到的邻接点进行遍历,直到图中所有和v有路径相通的顶点都被访问到(注:优先访问外层节点,访问到无新顶点时,会进行回退,访问未被访问过的分支顶点)。

广度优先遍历:类似于树的层序遍历。从图中的某个顶点w出发,让顶点w入队,然后顶点w再出队,并让所有和顶点w相连的顶点入队,然后再出队一个顶点t,并让所有和t相连但未被访问过的顶点入队……由此循环,指定图中所有元素都出队。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a[1000][1000];//邻接矩阵
int flag[1000];//标记顶点有没有遍历过
int b[1000];//记录输出遍历结果
int t;
void bfs(int x,int n)
{
    queue<int>q;//队列中元素均为int类型
    t = 0;
    b[t++] = x;//把遍历起始点放入b数组
    flag[x] = 1;//顶点标记
    q.push(x);//顶点入队
    while(!q.empty())//当队列不为空时
    {
        int v = q.front();//取队列的第一个元素
        q.pop();
        int i;
        for(i =0; i<n; i++)
        {
            if(flag[i]!=1&&a[v][i]==1)//如果其他顶点与队列的头元素是相通的且未被访问过
            {
                b[t++] = i;//把该点放入b数组中
                flag[i] = 1;//标记该点
                q.push(i);//将该点入队
            }
        }
    }
}

int main()
{
    int n,k,m,x,i,u,v;
    cin >> n;
    while(n--)
    {
        memset(a,0,sizeof(a));//每组都要进行初始化
        memset(flag,0,sizeof(flag));
        cin >> k >> m >> x;
        for(i=0; i<m; i++)//m为边数
        {
            cin >> u >> v;
            a[u][v] = a[v][u] = 1;//无向图没有方向
        }
        bfs(x,k);
        for(i=0; i<t; i++)//遍历输出
        {
            if(i==t-1)
            {
                cout << b[i] <<endl;
            }
            else
            {
                cout << b[i] << " " ;
            }
        }
    }
    return 0;
}

数据结构实验之图论二:图的深度遍历

图的深度遍历理解

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

int n[110][110];
int flag[110];
int b,c;

void dfs(int a)
{
    int i;
    if(a==0)
    {
        cout << a;
    }
    else
    {
        cout << " " << a;
    }
    flag[a]=1;
    for(i=0; i<b; i++)
    {
        if(n[a][i]==1&&flag[i]==0)//如果该点存在并且未被标记
        {
            dfs(i);
        }
    }
}

int main()
{
    int a,u,v;
    cin >> a;
    while(a--)
    {
        memset(n,0,sizeof(n));
        memset(flag,0,sizeof(flag));
        cin >> b >> c;
        while(c--)
        {
            cin >> u >> v;
            n[u][v]=1;
            n[v][u]=1;
        }
        dfs(0);
        cout << endl;
    }
    return 0;
}

数据结构实验之图论三:判断可达性

#include <iostream>
#include <string.h>

using namespace std;

int flag[10100];
int n[1010][1010];
int a,b;

void dfs(int s)//深度查询
{
    int i;
    flag[s]=1;//标记
    for(i=1; i<=a; i++)
    {
        if(flag[i]!=1&&n[s][i]==1)//如果没有遍历标记过且s到i有有向线
        {
            flag[i]=1;//标记并且递归
            dfs(i);
        }
    }
}

int main()
{
    int c,d,i;
    while(cin >> a >> b)
    {
        memset(n,0,sizeof(n));
        memset(flag,0,sizeof(flag));
        for(i=1; i<=b; i++)
        {
            cin >> c >> d;
            n[c][d]=1;
        }
        dfs(a);
        if(flag[1]==1)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    return 0;
}

数据结构实验之图论四:迷宫探索

深度优先遍历

#include<iostream>
#include<string.h>
using namespace std;
int mp[1010][1010];//邻接矩阵
int vis[1010];//记录已经遍历过的节点
int a[1010];//记录DFS遍历时经过的路径
int sum,n,m,s,k;//sum记录遍历时所遍历的节点总数
void DFS(int s)//深度优先遍历
{
    vis[s]=1;//标记
    sum++;//总数增加
    a[k++]=s;//正序遍历,存点
    for(int i=1; i<=n; i++)
    {
        if(vis[i]==0&&mp[s][i]==1)//若该点存在并且未被标记
        {
            DFS(i);
            a[k++]=s;//相当于逆序遍历存起来,不存6,是因为6的递归结束,回到5,s是5,a存的是5
                    //图的遍历,到最后一个节点发现不满足条件就会返回到上一个结点,然后一直回返到第一个结点
        }
    }
}
int main()
{
    int T,u,v;
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>s;
        memset(vis,0,sizeof(vis));//初始化
        memset(mp,0,sizeof(mp));
        memset(a,0,sizeof(a));
        while(m--)//创建邻接矩阵
        {
            cin>>u>>v;
            mp[u][v]=mp[v][u]=1;
        }
        k=sum=0;
        DFS(s);
        for(int i=0;i<k;i++)//控制换行,空格
        {
            if(i==0)
                cout<<a[i];
            else
                cout<<" "<<a[i];
        }
        if(sum!=n)// 表示此迷宫不是连通图
            cout<<" "<<0;
        cout<<endl;
    }
    return 0;
}

数据结构实验之图论五:从起始点到目标点的最短步数(BFS)

转载博客

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct node
{
    int data;//存储结点的序号
    int step;//存储已经遍历的结点
}q[2100];

int map[1001][1001];//存储关系
int v[1001];//存储已经遍历的点
int n,m;

void BFS(int x)//此处不可用n
{
    int in=0,out=0;//in表示队头,out表示队尾。
    struct node t;
    q[in].data=x,q[in].step=0;//将x,和0,传入结构体数组q中(队列)。
    in++;
    v[t.data]=1;//标记该点已经被遍历
    while(in>out)
    {
        t=q[out++];
        if(t.data==1)//当结点到达1时表示可以到达1号关隘
        {
            printf("%d\n",t.step);//输出当前步数
            return ;
        }
        int i;
        for(i=0; i<n; i++)
        {
            if(v[i]==0&&map[t.data][i]==1)//满足没有被遍历过,并且存在关系
            {
                q[in].data=i;
                q[in].step=t.step+1;//入队列
                in++;
                v[i]=1;
            }
        }
    }
    printf("NO\n");
    return ;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(map,0,sizeof(map));
        memset(v,0,sizeof(v));
        int i,a,b;
        for(i=0; i<m; i++)
        {
            scanf("%d %d",&a,&b);
            map[a][b]=1;
        }
        BFS(n);
    }
    return 0;
}

数据结构实验之图论六:村村通公路

prim算法(最小生成树)

#include<bits/stdc++.h>
#define INF 0xfffffff //也可以是0x3f3f3f3f 这两个都是接近无穷大的数值;
 
using namespace std ;
 
int n , m ; //顶点数, 边数 ;
 
int Map[3100][3100] ; //记录点与点之间所连接的边的权值;
 
int vis[3100] ; //记录点的访问情况 ;
 
int lowc[3100] ; //记录与这个点相连的边的最小权值(寻找最短路径,也就是最小边);
 
int prim()
{
    int res = 0 ; //最小权值路径的权值和;
    int i , j ;
    vis[1] = 1 ;
    for(i=1;i<=n;i++) //将lowc的初值都附为与定点1所连接边的权值;
    {
        lowc[i] = Map[1][i] ;
    }
    for(i=1;i<n;i++)//因为起一个是初始值,所以不用访问,所以访问n-1个;
    {
        int minc = INF ; //minc是记录最小权值的;
        int p = -1 ; //p记录的是与最小权值有关的点的下标;
        for(j=1;j<=n;j++)
        {
            if(vis[j]==0&&minc>lowc[j])
            {
                minc = lowc[j] ;
                p = j ;
            }
        }
        if(minc == INF)
            return -1 ;
        res += minc ;
        vis[p] = 1 ;
        for(j=1;j<=n;j++)
        {
            if(vis[j]==0&&lowc[j]>Map[p][j]) //如果这个点没有被访问过,而且这个点与原来最小点的权值为x,与现在最小点的权值为y,如果y<x ,那么就把这个点的lowc由x改为y;
            {
                lowc[j] = Map[p][j] ;
            }
        }
    }
    return res ;
}
int main()
{
    int i , j ;
    while(~scanf("%d %d",&n,&m))
    {
        memset(vis,0,sizeof(vis)) ; //将vis[]数组初始化;
        for(i=1;i<=n;i++) //将Map[]数组初始化;
        {
            for(j=1;j<=n;j++)
                {
                    if(i==j)
                        Map[i][j] = 0 ;
                    else
                        Map[i][j] = INF ;
                }
        }
        for(i=0;i<m;i++) //输入边得情况;
        {
            int u , v , t ;
            scanf("%d %d %d",&u,&v,&t);
            Map[u][v] = Map[v][u] = t ;
        }
        printf("%d\n",prim());
    }
    return 0 ;
}

数据结构实验之图论七:驴友计划

Dijkstra算法

#include<bits/stdc++.h>
#define MAX INT_MAX //int型里面最大的数
 
using namespace std ;
 
int n , m ; //顶点数,边数;
 
int Map[550][550] ; //存放点与点之间的权值;
 
int vis[550] ; //点的访问情况 ;
 
int money[550][550] ; //存放点与点之间的过路费 ;
 
 
void Dijkstra(int n , int v0, int vn)
{
    int dist[550] ; //存放v0到vn的最短路径 ;
    int mon[550] ;
    for(int i=0;i<n;i++)
    {
        dist[i] = Map[v0][i] ; //每个点的最短路径都设为与起点相连边上的权值,(不与起点相连的点dist[]数组的值为MAX)
        mon[i] = money[v0][i] ;//每个点的过路费都初始化成与起点v0相连边上的费用。
    }
    vis[v0] = 1 ;  //---->|
    dist[v0] = 0 ;    //  |---->对起点的初始化。
    mon[v0] = 0 ; //----->|
    for(int i=1;i<n;i++) //除了起点一共n-1个点 ;
    {
        int MIN = MAX  ; //先取一个无穷大的数,可以方便以后的替换其他的值; 
        int k = v0 ; //记录最短路径相关点的下标; 
        for(int j=0 ; j<n ; j++) //找出与起始点相连最短的路径;
        {
            if(vis[j]==0&&dist[j]<MIN) //如果这个点没有被访问过,而且这个点的最短路径比min小;(这个循环的作用是找出与起点v0相连的点所形成的边,那个边的权值最小(最短路径最短))
            {
                MIN = dist[j]  ;
                k = j ;
            }
        }
        vis[k] = 1 ; //改变相关点访问状态;
        int j ;
        for(j=0;j<n;j++)
        {
            if(vis[j]==0&&Map[k][j]<MAX) //如果这个点没被访问过。而且这个点j与点k之间存在边的话(Map[k][j]<MAX意思是k,j之间有边连接)
            {
                if(Map[k][j]+dist[k]<dist[j]) //这个点与k点的路径+起点v0到k的最短路径 < 起点v0到j的最短路径
                {
                     dist[j] = Map[k][j] + dist[k] ;
                     mon[j] = mon[j] + money[k][j] ;
                }
                else if(dist[k]+Map[k][j]==dist[j]&&mon[k]+money[k][j]<mon[j]) //路径相同,钱不同 ; 
                {
                    mon[j] = mon[j] + Map[k][j] ;
                }
            }
        }
    }
    printf("%d %d\n",dist[vn],mon[vn]) ;
}
 
int main()
{
    int  t ;
    scanf("%d",&t) ;
    while(t--)
    {
        int v0 , vn ;
        scanf("%d %d %d %d",&n,&m,&v0,&vn);
        int i , j ;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(i==j)
                    Map[i][j] = 0 ;
                else
                    Map[i][j] = MAX ;
            }
        }
        memset(vis,0,sizeof(vis)) ;
        int u , v , t , s ;
        for(i=0;i<m;i++)
        {
            scanf("%d %d %d %d",&u,&v,&t,&s);
            Map[u][v] = Map[v][u] = t ;
            money[u][v] = money[v][u] = s ;
        }
        Dijkstra(n,v0,vn) ;
    }
    return 0 ;
}