数据结构之——图论基础
分类
-
无向图 边没有方向
-
完全无向图:所有顶点都相互连接
一共有 ( n ∗ ( n − 1 ) ) / 2(n*(n-1))/2 (n∗(n−1))/2条边
-
-
有向图,边有方向
- 入度、出度
- 完全有向图:一共有 n ∗ ( n − 1 ) n*(n-1) n∗(n−1)条边
-
稀疏图:边数远小于完全图的图
-
稠密图:边数接近完全图的图
-
连通图:任意两个不同顶点都连通的图
- 连通分量:图中的极大连通子图(尽可能大的连通图)(连通图的连通分量就是它自己)
- 强连通:有向图中两个顶点 v iv_i vi、 v jv_j vj,从 v iv_i vi到 v jv_j vj和从 v jv_j vj到 v iv_i vi都连通
- 强连通图:任意两个不同顶点都强连通
- 强连通分量:图中的极大强连通子图(尽可能大的强连通图)(强连通图的强连通分量就是它自己)
-
简单图:不含平行边也不含闭环的图
基本结构
- 权值:边的“费用”,可以理解为边的长度
- 度:该顶点边的总数
- 路径:顶点到顶点之间的边的集合
- 回路:起点和终点相同的路径,也称作“环”
存储方式
邻接矩阵
我们可以利用二维数组来储存图中顶点于顶点之间的关系。
#define size 100int Graph[100][100];
自己到自己设置为无穷大(说明自己不能到自己)
邻接矩阵的存图
#includeusing namespace std;#define N 100int Graph[N][N];int n,e;int x,y,z;int main(){cin>>n>>e;memset(Graph,0x3f,sizeof(Graph));for(int i=1;i>x>>y>>z;//输入边的起点x、终点y和权值zGraph[x][y]=z;//如果图是无向图则还需要反向处理//Graph[y][x]=z;}}
储存每个顶点的度
#includeusing namespace std;#define N 100int Graph[N][N];int Du[N];int n,e,x,y,z;int main(){cin>>n>>e;memset(Graph,0x3f,sizeof(Graph));for(int i=1;i>x>>y>>z;//输入边的起点x、终点y和权值zGraph[x][y]=z;//如果图是无向图则还需要反向处理//Graph[y][x]=z;Du[x]++;//无向图反向处理//Du[y]++;}}
储存顶点的临接点
#includeusing namespace std;#define N 100#define M 200int Graph[N][N];int Du[N];int Near[N][M];//N[i][k]存顶点的k条边的终点int n,e,x,y,z;int main(){cin>>n>>e;memset(Graph,0x3f,sizeof(Graph));for(int i=1;i>x>>y>>z;//输入边的起点x、终点y和权值zGraph[x][y]=z;//如果图是无向图则还需要反向处理//Graph[y][x]=z;Near[x][++Du[x]]=y;//无向图反向处理//Near[y][++Du[x]]=x;}}
边集数组
边集数组的存储
#includeusing namespace std;#define N 101struct Edge{int x,y,z;}edge[N];int n,e;int main(){cin>>n>>e;for(int i=1;i>edge[i].x>>edge[i].y>>edge[i].z;}return 0;}
邻接表
存相邻点的地址
c++实现邻接表_黄色猴子的博客-CSDN博客_c++邻接表
链式前向星
数据结构定义
int head[101];//记录下标对应顶点最后一条边的编号int cnt=0;//记录当前边的编号struct edge{ int next;//记录这条边 起点的下一条 边的编号 int to;//记录边的终点编号 int dis;//记录边的权值}edge[101];
添加边
void Addedge(int from,int to,int dis){edge[++cnt].next=head[from];edge[cnt].to=to;edge[cnt].dis=dis;head[from]=cnt;}
遍历
for(int i=1;i<=n;i++){for(int j=head[i];j;j=edge[j].next){......;}}