• 题目描述
  • • 输入格式
    • 输出格式
    • 数据范围
    • 输入样例：
    • 输出样例：
• 图的链表存储+ bfs算法求解
  • 分析
  • 图的链表存储
  • 图的邻接矩阵存储
  • 代码
  • 时间复杂度
• 参考文章

题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1，点的编号为 1∼n。

请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

数据范围

1≤n,m≤10^5

输入样例：

4 5
1 2
2 3
3 4
1 3
1 4

输出样例：

1

图的链表存储+ bfs算法求解

分析

图的链表存储

使用数组模拟单链表实现

const int N = 100010;
int h[N], e[N], ne[N], idx = 0; // n个单链表，用来存每个点能够到达的其他顶点

void init()
{
	memset(h, -1, sizeof h); // 初始所有表头指向-1
}
// 在顶点a和b之间建立一条边
// 头插法
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}


int main()
{
    // 遍历一个点能到的其他点
    // a点能到的其他点
    for(int i = h[a]; i != -1; i = ne[i])
    {
        int t = e[i];
        // t就是与a邻接的点
    }
}

使用vector实现

const int N = 100010;
int n, m;
vector<int> G[N]; // 存图
// 在顶点a和b之间建立一条边
// 头插法
void add(int a, int b)
{
   G[a].push_back(b);
}

int main()
{
    // 遍历一个点能到的其他点
    // a点能到的其他点
    for(auto p : G[a])
    {
        int t = p;
        // t就是与a邻接的点
    }
}

图的邻接矩阵存储

就是使用一个二维数组来存边的信息，比较浪费空间

代码

使用数组模拟链表

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

const int N = 100010;

int h[N], e[N], ne[N], idx = 0; // 单链表存图
int d[N]; // 表示到某个点的最短距离 
int st[N];
int n, m;
// a,b之间建立一条边 
void add(int a, int b) 
{
	// idx 表示当前这个节点的编号 
	e[idx] = b; // 创造一个节点存b的值
	ne[idx] = h[a]; // 头插 
	h[a] = idx; // 头插 
	idx++;
}

int bfs()
{
	queue<int> q;
	d[1] = 0;
	st[1] = true;
	q.push(1);

	while(q.size())
	{
		int t = q.front();
		q.pop();
		// 该点的距离 
		int dis = d[t];
		// 找到了终点 
		if(t == n) return dis;

		// 遍历t所有相邻的节点 
		for(int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i]; // j表示该点的值
			if(!st[j])
			{
				st[j] = true; // 该点访问过了，其最小距离已经求出 
				q.push(j); // 把这个点放入队列
				d[j] = dis + 1; 
			 } 
		}
	}
	return -1;
}


int main()
{
	memset(h, -1, sizeof h); // 初始化所有的链表头
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b); // 创建一条边 
	} 
	// 使用bfs第一次发现的点的距离，就是到该点的最短距离
	cout << bfs() << endl;
	return 0; 
	 
 } 

使用vector

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

const int N = 100010;
int n, m;
vector<int> G[N]; // 存图
int d[N];

int bfs()
{
    memset(d, -1, sizeof d); // 初始化距离d
    
    queue<int> q;
    d[1] = 0;
    q.push(1);
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        if(t == n) return d[t];
        
        // 枚举所有t邻接的点
        for(auto point : G[t])
        {
            if(d[point] == -1)
            {
                q.push(point);
                d[point] = d[t] + 1;
            }
        }
    }
    return -1;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        G[a].push_back(b); // 有向图
    }
     cout << bfs() << endl;
     return 0;
}

时间复杂度

参考文章

https://www.acwing.com/activity/content/code/content/47104/

https://www.cnblogs.com/moomcake/p/9774402.html

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#define N 10000
using namespace std;
struct EDGE
{
    int to;//终点
    int cost;//边的权值
};
vector<EDGE>G[N];//G[i]中i表示出发点
int m,n;
int temp1;//出发点
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        EDGE e;
        scanf("%d%d%d",&temp1,&e.to,&e.cost);//输入出发点，终点，边的权值
        G[temp1].push_back(e);//将数据压入动态数组，表示在这个出发点下引出的边
        //相当于二维动态数组
    }
    for (int i=1; i<=n; i++) //按照出发点的顺序遍历
    {
        for(int j=0; j<G[i].size(); j++) //遍历出发点所引出的边
        {
            EDGE e=G[i][j];//1以二维数组形式输出
            printf("from %d to %d,the cost is %d\n",i,e.to,e.cost);
        }
    }
    return 0;
}