数据结构 C6 图（上）

2022-12-10 147

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构 C6 图

6.1图的基本概念

6.1.1图的定义（见王道书）

图的基本定义（

有向图/无向图

简单图/完全图，数据结构只讨论简单图

完全图/子图

连通/连通图/连通分量/最大连通分量/最小连通分量/强连通/强连通图/强连通分量/最大强连通分量/最小强连通分量

生成树/生成森林

度/入度/出度

边的权和网

稠密图/稀疏图

路径/路径长度/回路/简单路径/简单回路/距离

有向树

6.2图的存储及其基本操作

6.2.1邻接矩阵法

邻接矩阵法：

图的存储结构有向图无向图

对于图，它分为顶点还有边；边就是两个顶点的邻接关系，所以说要把图这个东西储存的话，就一定要分别储存点还有边。

图一般意义分为有向图还有无向图；对于前者后者顶点存储方式相同；但是对于后者存储方式是不同的；

那么我们怎么储存呢；

对于点来说，他就是一个整形数据啥的，用一个一维数组就可以了；对于边来说用二维数组了。如下图1。左边有向右边无向；

看一个有向图的存储方法：

最后的存储结构：

看一个无向图的存储矩阵：错了（第一列最后一个元素是1）

最后转化为：

网呢储存结构

我们之前说了，如果给每条边一个数值作为该边的权重：就变成了网；

那么我们该如何存储网呢？同样是利用矩阵和数组；如果该边不存在则存放无穷

举个例子：

网或者图在语言中是如何定义的？

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct{
  VertexType Vex[MaxVertexNum];
  EdgeType Edge[MaxVertexNum][MaxVertexnum];
int vexnum,arcnum;
}MGraph;

性质

运算：

6.2.2邻接表法

当一个图相对比较稠密的时候，他适合采用上面一种邻接矩阵的方法，但是把，如果说这个图相对比较稀疏的话，那么采用以上算法就是相对比较浪费了，那用现在介绍的这种方法。邻接表法

采用顶点用顺序结构而边用链式结构存储

比如咱们看一个有向图的例子:

kankan是怎么储存的

再看一个无向图的例子：

储存结构：

#define MaxVertNum 100
typedef struct ArcNode{
int adjvex;
struct ArcNode *next;
//InfoType info;//表示权重
}ArcNode;
typedef struct VNode{
  VertexType data;
  ArcNode *first;
}VNode,AdjList[MaxVertexNum];
typedef struct{
  Adjust vetices;//邻接表
int vexnum,arcnum;
}ALGraph;

特点：

比较邻接矩阵和邻接表的异同：

6.2.3十字链表

对于连接表而言找到出边是相对来说比较容易的但是想找到入边来说就是比较难的他需要遍历整个表。

那么我们我们引申出一个新的结构

存储结构

#define MaxVertexNum 100;
typedef struct ArcNode{
int tailvex,headvex;
struct ArcNode *hlink,*tlink;
//infotype info;
}ArcNode;
typedef struct VNode{
  VertexType data;
  ArcNode *firststin,*firstout;
}VNode;
typedef struct{
  VNode xlist[MaxVertexNum];
int vexnum,arcnum;
}GLGraph;

6.2.4邻接多重表

对于无向图，我们之前使用了邻接表的形式：

你看一个对于这两个储存空间，如果删除它的时候，需要遍历，而且要删除两个，这样的话会是很麻烦的。于是引用了咱们今天学习的。

#define MaxVertNum 100;
typedef struct ArcNode{
int ivex ,jvex;
struct ArcNode *ilink,*jlink;
//infotype info;
//bool mark;
}ArcNode;
typedef struct VNode{ 
  VertexType data;
  ArcNode *firstedge;
}VNode;
typedef struct{
  VNode adjmulist[MaxVertexnum];
int vexnum,arcnum;
}AMLGraph;

十字链表邻接多重表

他们都是邻接表的优化；十字链表针对的是有向图，解决了有向图中无法快速找到某一顶点入边的这一弊端。邻接多重表解决了无向图中每一个边要用两个边表结构来存放的弊端。

6.2.5图的基本操作

Adjacent(G,x,y) 判断图G是否存在边或(x,y).

Neighbour(G,x) 列出图G中与结点x相邻的边

InsertVertex(G,x);在图G中插入顶点x

右边更好；

DeleteVertex(G,x)从图G中删除顶点x;

右边更好；

AddEdge(G,x,y);若无向边(x,y)或者不存在，则向图中G中添加该边

左边更好

RemoveEdge(G,x,y)若无向边(x,y)或者有向边存在，则在图G中删除该边；

FirstNeighbor(G,x);求图G中顶点X的第一点邻接点，若有则返回顶点号。若没有邻接点或图不存在x，则返回-1；

NextNeighbor(G,x,y) 假设图G中顶点y是顶点x的一个邻接点，返回除了y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1；

Get_edge_value(G,x,y)；获取图G中边(x,y)或<x,y>对应的权值v;
Set_edge_value(G,x,y); 设置G中边(x,y)或<x,y>的权值为v;

6.3图的遍历

从图的某一点出发，按照某种算法，沿着图中的边，对图中所有的顶点进行一次访问（只访问一次）

6.3.1广度优先搜索

它和树的层次遍历很像，但是如果又按照层次遍历的算法来，一定会出现错误。如下

那么怎么改善呢

算法代码如下：

bool visited[MAX_TREE_SIZE];//定义了一个bool型的辅助标记数组
void BFSTraverse(Graph G){
for(int i=0;i<G.vexnum;++i)
  visited[i]=FALSE;
InitQueue(Q);
for(int i;i<G.vexnum;++i)
if(!visited[i])
BFS(G,i);
}
void BFS(Graph G,int v){
visit(v);
  visited[v]=TRUE;
Enqueue(Q,v);
while(!isEmpty(Q)){
Dequeue(Q,v);
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
if(!visited[w]){
    visited[w];
    visited[w]=TRUE;
Enqueue(Q,w);
}
}
}

BTS算法的性能分析：

关于广度优先搜索解决最短路径问题：（不懂）

==广度优先生成树：=

6.3.2深度优先算法

与树的深度优先遍历之间的联系&& 算法实现

树的优先遍历

void preorder(treenode *R ){
if(R!=NULL){
visit(R);
while(R还有下一个子树T)
Preorder(T);
}
}

图的深度优先遍历：

bool visited[MAX_VERTEX_NUM];
void DFS(Graph G,int v){
visit(v);
  visited[v]=TRUE;
for(w=FirstNeighbor(G,v);w>=0;w=NextNeihbor(G,v,w))
if(!visited[w]){
DFS(G,w);
} 
}