江西省住房保障建设厅网站,天津 网站设计公司,建设我们的网站教案,工商网官网什么是图#xff1f;
我们在生活中学习中能看见很多图#xff0c;地图#xff0c;路线图#xff0c;思维导图等等#xff0c;它们都有一个特点#xff0c;
你从中任找一个点#xff0c;你可以找到#xff0c;从这个点出发#xff0c;能够到达什么地方#xff0c;也…什么是图
我们在生活中学习中能看见很多图地图路线图思维导图等等它们都有一个特点
你从中任找一个点你可以找到从这个点出发能够到达什么地方也许不能到达任何地方。
以这个点为终点有哪些点能到达这个点。
利用图我们可以有方向地去到每一个点。也能找到去到这个点最短的方法。
图的建立
下面建立一个简单的图来描述一些图的基本术语
无向图 在这副地图之中每个建筑物被称作顶点
每对建筑物之间连接的小路叫做边
走这条边需要花费的时间叫做边权 像这样的一条路可以让两座建筑的人互相通行不具有方向性的图叫做无向图。
在无向图中每个顶点所连接的边数叫做每个顶点的度数。 有向图 像这样的一条路只允许一种方向的人通过如果要两座建筑物之间互相往来那么需要再建立一条单向路。这样的图叫做有向图。 如果两个顶点之间有不止一条边直接连接就称为重边。
如果一条边的起点和终点是相同的就称为自环。 图的存储
方法一邻接矩阵无重边
也就是建立一个二维矩阵 v[i][j] 代表以i为起点j为终点的边权如果v[i][j]0说明i到j没有直接的路相连。
缺点就是将图存入的时候用到二重循环假设有n个顶点我们需要on^2)的空间复杂度遍历的时候也是on^2)的时间复杂度。 方法二邻接表
邻接矩阵和邻接表的区别就是邻接表只存放具有边的顶点。减少了不必要的存放次数。
下面是邻接表的实现:
1,建立一个结构体里面有两个变量tocost
分别代表终点边权。
2.建立一个二维vector , vectorint p [maxn]
每当读入一条边的起点u终点v边权l 用 p[u] .push_back((edge){ vl}
using namespace std;
const int MAXN 1005;
struct place {int to, cost;
};
vector place p[MAXN];
int v[MAXN][MAXN];
int main()
{int n,m;cin nm;while (m--){int u, v, l;cin u v l;p[u].push_back({ v, l });}for (int i 1; i n; i) {for (int j 0; j p[i].size(); j) {v[i][p[i][j].to] p[i][j].cost;}}for(int i 1; i n; i){for (int j 1; j n; j)cout v[i][j] ;cout endl;}
}
