图的存储及基本操作

邻接矩阵法

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。

图的邻接矩阵存储结构定义如下：

#define MaxVertexNum 100  // 顶点数目的最大值
typedef char VertexType;  // 顶点的数据类型
typedef int EdgeType;     // 带权图中边上权值的数据类型
typedef struct {
    VertexType Vex[MaxVertexNum];               // 顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵，边表
    int vexnum, arcnum;  // 图的当前顶点数和边数/弧数
} MGraph;

注意：

1. 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可省略）。
2. 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeType 可定义为值为 0 和 1 的枚举类型。
3. 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用 压缩存储。
4. 邻接矩阵表示法的空间复杂度为 #card=math&code=O%28n%5E2%29&id=ZfBL4)，其中 为图的顶点数 。

图的邻接矩阵存储表示法具有以下特点：

1. 对于无向图，邻接矩阵的第 行（或第 列）非零元素（或非 元素）的个数正好是第 个顶点的度 #card=math&code=TD%28v%29&id=ISEc1)。时间复杂度 #card=math&code=O%28%7CV%7C%29&id=cS7ZW)。
2. 对于有向图，邻接矩阵的第 行（或第 列）非零元素（或非 元素）的个数正好是第 个顶点的出度 #card=math&code=OD%28v%29&id=TtlMm) [或入度 #card=math&code=ID%28v%29&id=Lym4S) ]。第 行结点的度即为，第 行和列的非零元素（或非 元素）的个数之和。时间复杂度 #card=math&code=O%28%7CV%7C%29&id=vNB85)。
3. 设图 的邻接矩阵为 $\mathbf{A} \mathbf{A}^n$ 的元素 等于由顶点 到顶点 的长度为 的路径的数目。（妙啊）
4. 稠密图适合使用邻接矩阵的存储表示。
5. 无向图的邻接矩阵一定是一个对称矩阵（并且唯一）。 因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素。
6. 用邻接矩阵法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。

   邻接表法

   当一个图为稀疏图时，使用邻接矩阵法显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。

所谓邻接表，是指对图 中的每个顶点 建立一个单链表，第 个单链表中的结点表示依附于顶点 的边（对于有向图则是以顶点 为尾的弧），这个单链表就称为顶点 的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点。

#define MaxVertexNum 100 // 图中顶点数目的最大值
typedef char VertexType;  // 顶点的数据类型
// "边/弧"
typedef struct ArcNode {
    int adjvex;            // "边/弧"指向哪个结点
    struct ArcNode *next;  // 指向下一条弧的指针
    // InfoType info       // 边权值
} ArcNode;

// "顶点"
typedef struct VNode {
    VertexType data;  // 顶点信息
    ArcNode *first;   // 第一条边/弧
} VNode, AdjList[MaxVertexNum];

// 用邻接表存储的图
typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

图的邻接表存储方法具有以下特点：

1. 若 为无向图，则所需的存储空间为 #card=math&code=O%28%7CV%7C%2B%202%7CE%7C%29&id=gh9yf)；若 为有向图，则所需的存储空间为 #card=math&code=O%28%7CV%7C%2B%20%7CE%7C%29&id=iOaBY)。前者的倍数 2 是由于无向图中，每条边在邻接表中出现了两次。
2. 对于稀疏图，采用邻接表表示将极大地节省存储空间。
3. 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为 #card=math&code=O%28n%29&id=qf7s2) 。 但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
4. 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表存储方式是类似的。
5. 图的邻接表表示并不唯一，因为在每个项点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

   十字链表法

   十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。

弧结点中有 5 个域：尾域（tailvex） 和头域（headvex）分别指示弧尾和弧头这两个顶点在图中的位置；链域 hlink 指向弧头相同的下一条弧；链域 tlink 指向弧尾相同的下一条弧；info 域指向该弧的相关信息。这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上。

顶点结点中有 3 个域：data 域存放顶点相关的数据信息，如顶点名称；firstin 和 firstout 两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。

在十字链表中，既容易找到 为尾的弧，又容易找到 为头的弧，因而容易求得顶点的出度和入度。图的十字链表表示是不唯一的， 但一个十字链表表示确定一个 图。空间复杂度：#card=math&code=O%28%7CV%7C%2B%7CE%7C%29&id=umKM4)

TODO 代码实现十字链表法

邻接多重表法

邻接多重表是无向图的另一种链式存储结构。

在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低。

与十字链表类似，在邻接多重表中，每条边用一个结点表示，其结构如下所示。

其中，mark 为标志域，可用以标记该条边是否被搜索过；ivex 和 jvex 为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点 ivex 的边；jlink 指向下一条依附于顶点 jvex 的边，info 为指向和边相关的各种信息的指针域。

每个顶点也用一个结点表示，它由如下所示的两个域组成。

其中，data 域存储该顶点的相关信息，firstedge 域指示第一条依附于该顶点的边。

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

空间复杂度：#card=math&code=O%28%7CV%7C%2B%7CE%7C%29&id=ousYf)。

图的基本操作

图的基本操作是独立于图的存储结构的。而对于不同的存储方式，操作算法的具体实现会有着不同的性能。在设计具体算法的实现时，应考虑采用何种存储方式的算法效率会更高。

图的基本操作主要包括（仅抽象地考虑，故忽略掉各变量的类型）：

• Adjacent (G,x,y)：判断图 是否存在边 或 #card=math&code=%28x%2Cy%29&id=sdVMZ)。邻接矩阵时间复杂度：#card=math&code=O%281%29&id=d2egP)，邻接表时间复杂度：%5Csim%20%20O(%7CV%7C)#card=math&code=O%281%29%5Csim%20%20O%28%7CV%7C%29&id=fiBn0)。
• Neighbors (G,x)：列出图 中与结点 邻接的边。邻接矩阵时间复杂度：#card=math&code=O%28%7CV%7C%29&id=oJzpu)；邻接表无向图时间复杂度：%5Csim%20%20O(%7CV%7C)#card=math&code=O%281%29%5Csim%20%20O%28%7CV%7C%29&id=y81zC)，邻接表有向图出边时间复杂度：%5Csim%20O(%7CV%7C)#card=math&code=O%281%29%5Csim%20O%28%7CV%7C%29&id=Bi9Qa)，邻接表有向图入边时间复杂度：#card=math&code=O%28%7CE%7C%29&id=LEfY4)。
• InsertVertex(G,x)：在图 中插入顶点 。邻接矩阵和邻接表时间复杂度：#card=math&code=O%281%29&id=rtGmL)
• DeleteVertex(G,x)：从图 中删除顶点 。邻接矩阵无向图时间复杂度：#card=math&code=O%28%7CV%7C%29&id=vBfXX)，邻接表无向图时间复杂度：%5Csim%20O(%7CE%7C)#card=math&code=O%281%29%5Csim%20O%28%7CE%7C%29&id=cz7TM)；邻接矩阵有向图时间复杂度：#card=math&code=O%28%7CV%7C%29&id=EUR94)，邻接表删出边：%5Csim%20O(%7CV%7C)#card=math&code=O%281%29%5Csim%20O%28%7CV%7C%29&id=iWxCz)，邻接表删入边：#card=math&code=O%28%7CE%7C%29&id=HKzl1)
• AddEdge (G,x,y)：若无向边 #card=math&code=%28x%2C%20y%29&id=iifg9) 或有向边 不存在，则向图 中添加该边。邻接矩阵 #card=math&code=O%281%29&id=aEizi)，邻接表 #card=math&code=O%281%29&id=tYXC9)
• RemoveEdge(G,x,y)：若无向边 #card=math&code=%28x%2C%20y%29&id=XfTSC) 或有向边 存在，则从图 中删除该边。邻接矩阵 #card=math&code=O%281%29&id=sY85a)，邻接表 %20%5Csim%20O(%7CV%7C)#card=math&code=O%281%29%20%5Csim%20O%28%7CV%7C%29&id=AqZTk)
• FirstNeighbor(G,x)：求图 中顶点 的第一个邻接点，若有则返回顶点号。若 没有邻接点或图中不存在 ，则返回 -1。邻接矩阵无向图 %5Csim%20O(%7CV%7C)#card=math&code=O%281%29%5Csim%20O%28%7CV%7C%29&id=xPPgh)，邻接表无向图 #card=math&code=O%281%29&id=gqnTL)；邻接矩阵有向图 %5Csim%20O(%7CV%7C)#card=math&code=O%281%29%5Csim%20O%28%7CV%7C%29&id=hbwTN)，邻接表有向图找出边邻接点：#card=math&code=O%281%29&id=WKKEg)，邻接表有向图找入边邻接点：%5Csim%20O(%7CE%7C)#card=math&code=O%281%29%5Csim%20O%28%7CE%7C%29&id=S7qRX)
• NextNeighbor (G,x,y)：假设图 中顶点 是顶点 的一个邻接点，返回除 外顶点 的下一个邻接点的顶点号，若 是 的最后一个邻接点，则返回 -1。邻接矩阵 %5Csim%20O(%7CV%7C)#card=math&code=O%281%29%5Csim%20O%28%7CV%7C%29&id=qdwUT)，邻接表 #card=math&code=O%281%29&id=FkHtB)；
• Get_edge_value(G,x,y)：获取图 中边 #card=math&code=%28x%2C%20y%29&id=pO9Sl) 或 对应的权值。时间复杂度同 Adjacent (G,x,y)
• Set_edge_value(G,x,y,v)：设置图 中边 #card=math&code=%28x%2C%20y%29&id=pzDJ8) 或 对应的权值为 。时间复杂度同 Adjacent (G,x,y)

此外，还有图的遍历算法：按照某种方式访问图中的每个顶点且仅访问一次。图的遍历算法包括深度优先遍历和广度优先遍历。

TODO 分析十字链表法和邻接多重表法下的基本操作的时间复杂度