数据结构——图（图的概念）

一、图的概念与逻辑结构

• 树没有环，但是图有环。
• 树的父子关系为一对多，图的节点的关系为多对多。
• 图由顶点和边构成。

• 无向图：每条边没有方向，用圆括号表示。（A1，A3）
• 有向图：每条边（弧）有方向，用尖括号表示。<A1，A3>

• 顶点的度：和某个节点有相联的边。
• 入度：指向节点的边。
• 出度：由节点指出的边。

• 简单图：图中不存在某定点到其自身的边，即不存在重复的边。
• 完全图：任意两顶点之间存在边（存在方向相反的边）。边的个数为n(n-1)/2（无向图），n(n-1)（有向图）
• 网（带权图）：边含有权重
• 子图：部分节点和边构成的图。

• 路径：一个顶点到另一个顶点的顶点序列。路径长度为路径上边的个数。
• 环（回路）：第一个顶点和最后一个顶点相同的路径。
• 简单路径：序列中顶点不重复出现的路径。
• 简单环：除了第一个和最后一个，其他顶点都不重复出现。

无向图的连通：

• Vi与Vj连通：无向图中，Vi到Vj之间有路径。
• 连通图：任意点之间存在路径。树天然就是连通的。
• 连通分量：无向图中的极大连通子图。子图无法通过扩展顶点变成连通图。

有向图的连通：

• Vi与Vj连通：有向图中，Vi到Vj，Vj到Vi有路径。
• 强连通图：对于每一对Vi和Vj都存在路径。
• 连通分量：有向图中的极大强连通子图。

二、图的存储结构

2.1顺序存储（邻接矩阵）

有向图：无权图的表示与带权图的表示

2.2链式存储

2.2.1邻接表（有向图&无向图）

树的链式存储有一种是孩子链表存储。类似于树的孩子链表存储，可以用邻接表存储图。

• 图用结构体数组表示
• 顶点节点包含1、数据信息2、指向下一个顶点的指针。
• 边节点的结构体包含1、数组下标2、指向下一个顶点的边

//图的邻接表整体结构
typedef struct{
    VNode vertices[MAX_VERTEX_NUM];//顶点数组，存储所有顶点节点f
    int vexnum,arcnum;//图的当前顶点数、边数（弧数）
}ALGraph;

//顶点节点，存储顶点数据及对应边链表的头指针
typedef struct VNode{
    int data;
    ArcNode* firstarc;//指向该J页点对应边链表的第一个边节点
}VNode;

//边节点（弧节点），存储邻接顶点及链接关系
typedef struct ArcNode{
    int adjvex;//邻接顶点在顶点数组中的下标
    struct ArcNode*nextarc;//指向下一个边节点的指针，构建链表
}ArcNode;

2.2.2逆邻接表（有向图）

• 邻接表为出边表，每个顶点的边链表存储以该顶点为起点的所有出边。
• 逆邻接表为入边表，每个顶点的边链表存储以该顶点为终点的所有入边。

2.2.3十字链表（有向图）

结合邻接表和逆邻接表。

• 顶点节点：data（数据域）、firstIn（指向入边的指针）、firstOut（指向出边的指针）
• 边节点：start（边的起点）、end（边的终点）、nextIn（指向入边的指针）、nextOut（指向出边的指针）

//顶点节点
typedef struct vertexNode{
    int data;
    ArcNode*firstin,*firstout;//第一条入边和第一条出边的指针
}VertexNode;

//边节点
typedef struct ArcNode{
    int tailvex,headvex;//弧尾（起点）和弧头（终点）的顶点下标
    struct ArcNode*hlink,*tlink;//入边表指针(hlink)和出边表指针(tlink)
}ArcNode;

2.2.4邻接多重表（无向图）

无向图用普通邻接表存储时，一条边会被存两次（比如边【0,1】，会在A的邻接表存B，也会在B的邻接表存A）。
我们希望边【0,1】和边【1,0】只用一个节点存储。

• 顶点节点：data（数据信息）、first（指向下一个顶点的指针）
• 边节点：Vi（起点）、ViNext（与起点有关的边）、Vj（终点）、VjNext（与终点有关的边）