首页 > 代码库 > 图论讲解（1）——图基础
图论讲解（1）——图基础
前面一直在哔哔数论，是不是感觉很烦的慌了？？
╮(╯▽╰)╭唉，你不烦得慌我都烦得慌了！
既然这样，那我们就改个话题，今天我们就讲讲图论。
有的同学就要问图又是个什么鬼？
难道是这个吗？ 还是这个？？？
哎呀，身为c++选手，我们肯定说的不是这些东西了对吧！
我们信息学上所说的图是指一个有序的二元组（V,E），V是顶点的集合，E是边的集合，E中的每一个元素都用一个二元组（x,y）来表示，其中x,y∈v。
这么说是不是有点太枯燥？
好，那我们下面来看一个我们所说的图。
有人又要说了：这是什么鬼，那么丑，这是个什么图？！
呵呵，很不幸，我们以后说的图都是这个那么恶心的东西。
one。图的相关概念：
有向图：图当中所有的边都是有向的，比如说：就表示1可以直接连接到达2，但2并不能直接到达1，除非有另一条边2——>1.
无向图：图当中的所有便都是无向的，也就是说如果v1可以到达v2的话，那么v2也一定能到达v1。
连通图：无向图中的两个点都是能相互到达的。
对于这个图来说他是个无向连通图。
这是个有向图。
自环：存在从一个点指向其自身的边称为一个自环。比如说存在一条边1——>1，那么这个图中存在自环。
重边：如果存在两条不同的边连接两个相同的节点（如果是有向图就要求起点相同，终点相同），那么这个图中就存在重边。
简单图：指不含有自环和重边的图。
无权图：图中的边没有权值。（如果指长度的话，则可以理解成权值均为1）
有权图：图中的边有权值。
这就是个无权图。
而这是个有权图。
图的基本概念都明白了吧，那么，接下来，我们考虑如何存储一个图。
对于存储图，我们有两种常用的方法：
1.邻接矩阵；
2.邻接链表；
假设给出点数N，边数M，点的编号从1到N，每条边用(a,b)表示从点a到点b的有向边。
我们可以建一个N*N的二维数组，然后这个二维数组当中的元素Aij表示点i到点j是否有边，如果有边则记为1，没有边则记为0.
我们可以把以同一节点为起点的边通过一个链表联系起来。
也就是说，我们可以通过在每一个节点记录一个head[i]表示节点i对应的链表里面的头指针（“第一条边”），
然后在每一条边的信息当中我们记录next[j]表示这条边在链表当中所指的下一条边。
总的来说，图的存储结构主要是两种：
邻接矩阵
邻接链表
而对于两种存储方法的选择，则主要根据图的特点（稠密图还是稀疏图）来选择
当然在数据规模小的时候，采用邻接矩阵要更为简洁
还要看代码吗？？
好吧。
邻接矩阵：
#include<stdio.h>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 10000using namespace std;int e[N][N],vis[N];int n,m,a,b,c;void bfs(int x){ vis[x]=1; for(int i=1;i<=n;i++) { if(e[x][i]&&!vis[i]) bfs(i); }}int main(){ scanf("%d%d",&n,&m);//n个点，m条边 for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); e[a][b]=c;//有向边 } bfs(1); return 0;}
邻接表：
#include<vector>#include<cstdlib>#include<cstring>#include<stdio.h>#include<iostream>#include<algorithm>#define N 100000#define maxn 123456using namespace std;int m,n,x,y,z;bool vis[N];vector<pair<int,int> >vec[N];void bfs(int x){ vis[x]=1; for(int i=0;i<vec[x].size();i++) { if(!vis[vec[x][i].first]) bfs(vec[x][i].first); } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); vec[x].push_back(make_pair(y,z)); } bfs(1); return 0; }
图论讲解（1）——图基础
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。