无锡高端网站建设咨询,购物网站创业时是如何做宣传的,定制衣服的网站,素材网站设计模板图论不同地方讲的不太一样#xff0c;本文仅限作者的理解
定义
图一般由点集 V V V 和边集 E E E 组成。 对于 v ∈ V v\in V v∈V#xff0c;称 v v v 为该图的一个节点。 对于 e ∈ E e\in E e∈E#xff0c;一般用二元组 ( u , v ) (u,v) (u,v) 表示 e e e…图论不同地方讲的不太一样本文仅限作者的理解
定义
图一般由点集 V V V 和边集 E E E 组成。 对于 v ∈ V v\in V v∈V称 v v v 为该图的一个节点。 对于 e ∈ E e\in E e∈E一般用二元组 ( u , v ) (u,v) (u,v) 表示 e e e其中 u , v ∈ V u,v\in V u,v∈V。在无向图中该二元组无序即边为双向在有向图中该二元组有序即边为单向。 一个带有边权边的长度的图称为带权图此时边一般记为 ( u , v , w ) (u,v,w) (u,v,w)。 下面分别是一个无向图和一个有向图的例子
连通性
从一个图中选出一些节点和边构成一个合法的新图称做原图的子图。 扩展至最大的符合某一要求的子图被称为分量。 通过图中的边可以使节点之间联通单向联通也算的图称做连通图。 节点之间两两可以互相到达的有向图被称做强联通图。 如果一个图中某一个点及其边被删去后图将不再联通则称该点为原图的一个割点。 没有割点的图被称为点双连通图。 如果一个图中某一条边被删去后图将不再联通则称该边为原图的一个割边。 没有割边的图被称为边双连通图。 读者可以自行理解联通子图、联通分量、强连通子图、强连通分量、点双联通子图、点双联通分量、边双联通子图、边双联通分量等概念。
树与环
一个没有环的图称为无环图。 一个没有环的有向图称为有向无环图DAG。 一个没有环且联通的无向图称为树。 一个有恰一个环且联通的无向图称为基环树。 一个是树且包含所有节点的子图称为原图的生成树。
存储
一般有两种存储方式邻接矩阵和邻接表。
邻接矩阵
使用一个矩阵来存储图对于矩阵中的一个元素 G u , v G_{u,v} Gu,v 在无权图中 u , v u,v u,v 之间有边为 1 1 1无边为 0 0 0 在带权图中 u , v u,v u,v 之间有边为 w w w无边为 inf \inf inf。
邻接表
使用多个数组来存储图对于每一个数组 G u G_u Gu 在无权图中 u , v u,v u,v 间有边则加入 v v v 在带权图中 u , v u,v u,v 间有边则加入有序二元组 ( v , w ) (v,w) (v,w)。
代码
分为定义输入和遍历三部分
邻接矩阵
int G[N][N];
memset(G,0,sizeof(G));//无权
memset(G,INF,sizeof(G));//带权for (int i1;im;i){//无权int u,v;cinuv;G[u][v]1;G[v][u]1;//仅限无向图//带权int u,v,w;cinuvw;G[u][v]w;G[v][u]w;//仅限无向图
}for (int u1;un;u) for (int v1;vn;v)if (G[u][v])//无权if (G{u][v]!INF)//带权邻接表
vectorint G[N];//无权
//带权
struct edge{int v,w;};
vectoredge G[N];for (int i1;im;i){//无权int u,v;cinuv;G[u].push_back(v);G[v].push_back(u);//仅限无向图//带权int u,v,w;cinuvw;G[u].push_back({v,w});G[v].push_back({u,w});//仅限无向图
}for (int u1;un;u)for (int v:G[u])//无权for (edge e:G[u])//带权
