> 文档中心 > 数据结构之——图论基础

数据结构之——图论基础


分类

  1. 无向图 边没有方向

    1. 完全无向图:所有顶点都相互连接

      一共有 ( n ∗ ( n − 1 ) ) / 2(n*(n-1))/2 (n(n1))/2条边

  2. 有向图,边有方向

    1. 入度、出度
    2. 完全有向图:一共有 n ∗ ( n − 1 ) n*(n-1) n(n1)条边
  3. 稀疏图:边数远小于完全图的图

  4. 稠密图:边数接近完全图的图

  5. 连通图:任意两个不同顶点都连通的图

    1. 连通分量:图中的极大连通子图(尽可能大的连通图)(连通图的连通分量就是它自己)
    2. 强连通:有向图中两个顶点 v iv_i vi v jv_j vj,从 v iv_i vi v jv_j vj和从 v jv_j vj v iv_i vi都连通
    3. 强连通图:任意两个不同顶点都强连通
    4. 强连通分量:图中的极大强连通子图(尽可能大的强连通图)(强连通图的强连通分量就是它自己)
  6. 简单图:不含平行边也不含闭环的图

基本结构

  1. 权值:边的“费用”,可以理解为边的长度
  2. 度:该顶点边的总数
  3. 路径:顶点到顶点之间的边的集合
  4. 回路:起点和终点相同的路径,也称作“环”

存储方式

邻接矩阵

我们可以利用二维数组来储存图中顶点于顶点之间的关系。

#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){......;}}