十六、图

 

1.定义

由点和线连成的一张图，点是有穷非空的

术语：

顶点：线性表中数据元素叫元素，树中叫节点，而图中叫顶点（Vertex）

ps.线性表中相邻的点只有顺序关系，树中相邻的点只有层次关系，而图不管哪两个顶点都可能有关系，关系用边来表示，边可以一条都没有。

无向边：两个点之间的边没有方向

有向边：同理，也称为”弧”

有向图G2=（V2，{ E2 }），其中顶点集合V2={
A，B，C，D}，弧集合E2={ <A，D>，<B，A>，<C，A>，<B，C>}

这里有向边用的是<>，无向边用的是（）

简单图：①不存在顶点到其自身的边②同一条边不重复出现

完全图：任意两个顶点都存在边，无向的叫无向完全图。有向且方向互为相反的叫有向完全图

稠密图、稀疏图

网：边上的数字是权，带权的图叫网

子图

2.顶点与边的关系

度：有多少边连着这个点，这个点就有多少度

边数=度数总和/2

有向图中指向点的弧叫做的数目称为顶点的入度，相反称为出度

度=入度+出度

边数=入度和=出度和

路径的长度=边数（弧数）

回路、环：从某个顶点出发，最后回到这个顶点的路径称为回路或环。

除了出发点，其他点不重复的叫简单回路或简单环，连出发点都不重复的叫简单路径

3、连通图

任意两个点都连通

连通分量：①要是子图

②子图是连通的

③连通子图含有极大顶点数

④具有极大顶点数的连通子图包含依附于这些顶点的所有边

强连通图：任意两个点之间都存在路径，有向图的极大强连通子图称为强连通分量

生成树：n个顶点n-1条边

有向树：有向图中恰有一个顶点入度为0，其它顶点入度为1

4.图的存储结构

1）邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。

一个一维数组存储图中顶点信息

一个二维数组存储图中边或弧的信息

举例：

如上这样一个无向图，它的顶点通过一维的顶点数组来存放，边通过二维的矩阵来存放

其中对角线为0代表每个顶点都不存在自身的边，两个点对应的位置为1代表两点之间有边，为0代表没有，其中v1和v3为0，代表两点之间没有边

因此，我们可以通过这个矩阵获得以下信息：

**①判断两点之间有无边非常容易
**

**②某个顶点的度就是这个顶点在矩阵中对应那一行元素的和，v1的度为1+0+1+0=2
**

**③求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍。a[i][j]为1就是邻接点
**

以上是有向图的存储方式

那么如果是一个带权值的网该如何存储呢？

如图左是一个网，在矩阵中我们用0表示不存在自身的边，用数值表示权值，用∞表示不存在权值

那么如何用代码来表示这种存储结构呢？

图的基本结构和准备

  1. typedef char VertexType;//顶点类型由用户自定义

  2. typedef int EdgeType;//边类型

  3. #define MAXVEX 100//最大顶点数

  4. #define INFINITY 65535//用65535代表∞

  5. typedef struct

  6. {

  7. VertexType vexs[MAXVEX];//顶点表

  8. EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵

  9. int numVertexes, numEdges;//当前的顶点数和边数

  10. }MGraph;

CreateMGraph方法，建立邻接矩阵存放图信息

  1. void CreateMGraph(MGraph *G)

  2. {

  3. int i, j, k, w;

  4. printf(“输入顶点数和边数：n”);

  5. scanf_s(“%d, %d”, &G->numVertexes,

    &G->numEdges);//输入顶点和边数

  6. for (i = 0; i < G->numVertexes; i++)//读入顶点信息，建立顶点表

  7. scanf_s(&G->vexs[i]);

  8. for (i = 0; i < G->numVertexes; i++)

  9. {

  10. for (j = 0; j < G->numVertexes; j++)

  11. G->arc[i][j] = INFINITY;//初始化矩阵，全部复制为65535

  12. }

  13. for (k = 0; k < G->numEdges; k++)

  14. {

  15. printf(“输入边（vi，vj）上的下标i，下标j和权w：n”);

  16. scanf_s(“%d, %d, %d”, &i, &j, &w);//输入边（vi，vj）上的权w

  17. G->arc[i][j] = w;

  18. G->arc[j][i] = G->arc[i][j];//因为是无向图，矩阵对称

  19. }

  20. }

2）邻接表

如果要处理一个稀疏有向图，邻接矩阵会显得很浪费空间。

因此联系链表和孩子表示法，可以创造出新的存储方式，称为邻接表

处理方法：

①图中顶点用一个一位数组存储，并且每个数据元素还需要指向第一个邻接点的指针，以便于查找边信息。

②图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数补丁，所以用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

顶点表中的节点都是由data和firstedge两个域表示的，data用于存放顶点信息，firstedge是指针域，用于指向第一个邻接点。

边表节点由adjvex和next两个域组成。adjvex存储某顶点的下标，next指向顶点的下一邻接点。

有向图的邻接表和逆邻接表，逆邻接表用来表示顶点的入度

对于带权值的网图，边表节点多加一个weight数据域就OK了

算法：

边表节点的结构

  1. //边表节点

  2. typedef struct EdgeNode

  3. {

  4. int adjvex;//邻接点域，用于存放邻接点的下标

  5. EdgeType weight;//权值域

  6. struct EdgeNode * next;//链域，指向下一邻接点

  7. }EdgeNode;

  8. //顶点表节点

  9. typedef struct VertexNodes

  10. {

  11. VertexType data;//顶点与

  12. EdgeNode * firstEdge;//边表头指针

  13. }VertexNode, AdjList[MAXVEX];

  14. typedef struct

  15. {

  16. AdjList adjList;

  17. int numVertexes, numEdges;

  18. }GraphAdjList;

CreateALGraph方法，利用头插法，对于无向图，一条边对应都是两个顶点

  1. void CreateALGraph(GraphAdjList *G)

  2. {

  3. int i, j, k;

  4. EdgeNode * e;

  5. printf(“输入顶点数和边数：n”);

  6. scanf_s(“%d,%d”, &G->numVertexes, &G->numEdges);

  7. for (i = 0; i < G->numVertexes; i++)

  8. {

  9. scanf_s(&G->adjList[i].data);//输入顶点信息

  10. G->adjList[i].firstedge = NULL;//将第一个指针置为空

  11. }

  12. for (k = 0; k < G->numEdges; k++)

  13. {

  14. printf(“输入边（vi，vj）上的顶点序号：n”);

  15. scanf_s(“%d,%d”, &i, &j);

  16. e = (EdgeNode

    *)malloc(sizeof(EdgeNode));//申请内存空间，创造边表节点

  17. e->adjvex = j;//下标为j

  18. e->next =

    G->adjList[i].firstedge;//e的指针指向的下一个是顶点表节点指向的空

  19. G->adjList[i].firstedge = e;//顶点表节点的指针指向e

  20. e = (EdgeNode *)malloc(sizeof(EdgeNode));

  21. e->adjvex = i;//下标为i

  22. e->next =

    G->adjList[j].firstedge;//e的指针指向的下一个对象是上面的e

  23. G->adjList[j].firstedge = e;//顶点表节点的下一指针指向e

  24. }

  25. }

3）十字链表

之前的邻接表是由缺陷的，它只关心了出度的问题，而入度却必须遍历整个图才能知道。反之，逆邻接表也解决值解决了入度的问题。

那么有没有能把邻接表和逆邻接表结合起来的方法呢？

答案就是十字链表

这个是重新定义的顶点表节点结构

其中firstin是入度，指向第一个入度点，firstout是出度

这个是重新定义的边表节点结构

其中tailvex是当前顶点的下标

headvex是顶点指向的下一点的下标

headlink是指入边表指针域，指向终点相同的下一条边

taillink是指边表指针域，指向起点相同的下一条边

对于顶点v0，有两个入边对于v1和v2，因此v0的firstin指向v1中边表节点headvex为0的节点，然后headlink指向v2中headvex为0的节点，如图①②。同理可得后面三种

4）邻接多重表

虽然邻接表能够优化存储方式，但是一旦需要进行增加删除等操作，就会显得十分麻烦，如图：

要删除v0和v2这条边，就必须删除邻接表中两个节点，那么有没有更好的数据结构来解决这个问题呢？

如图我们可以把边表节点改成这样的结构，

其中ivex和jvex是某条边依附的两个顶点的下标

· ilink指向ivex顶点的下一条边，jlink同理

首先连接 ①②③④，将顶点一一对应边

接着顶点v0的（v0，v1）的邻边有（v0，v3）（v0，v2），因此⑤⑥指向下一条依附于顶点v0的边的目标。同理可得⑦⑧⑨⑩

5）边集数组

边集数组是由两个一维数组组成。一个存储顶点信息，另一个存储边信息，这个边数组每个数据元素由一条边的起点下标，终点下表和权组成

其中begin存储起点下标，end存储终点下表，weight存储权

5.图的遍历

1）定义

从某个顶点访问其余顶点，且每个顶点只访问一次

2）分类

①深度优先遍历（Depth_First_Search）

仔细搜查每个角落

从顶点v开始，先输出该顶点，然后访问未被访问的邻接点，如果图中尚有点未被访问，则另选图中一个未曾访问的顶点作为起点，重复上述步骤

算法：

邻接矩阵的DFS结构和算法

  1. typedef int Boolean; //Boolean是布尔类型，其值是TRUE或FALSE

  2. Boolean visited[MAX]; //访问标识的数组

  3. //邻接矩阵的深度优先递归算法

  4. void DFS(MGraph G, int i)

  5. {

  6. int j;

  7. visited[i] = TRUE;

  8. printf(“%c “, G.vexs[i]); //打印顶点，也可以其他操作

  9. for (j = 0; j < G.numVertexes; j++)

  10. {

  11. if (G.arc[i][j] == 1 && !visited[j])

  12. DFS(G, j); //递归访问邻接点

  13. }

  14. }

DFSTraverse方法，遍历邻接矩阵

  1. //邻接矩阵深度遍历操作

  2. void DFSTraverse(MGraph G)

  3. {

  4. int i;

  5. for (i = 0; i < G.numVertexes; i++)

  6. {

  7. visited[i] = FALSE; //将每个顶点都初始化为未访问状态

  8. }

  9. for (i = 0; i < G.numVertexes; i++)

  10. {

  11. if (!visited[i])

  12. {

  13. DFS(G, i); //对未访问的顶点执行DFS

  14. }

  15. }

  16. }

邻接表的结构和算法

  1. //邻接表的深度优先递归算法

  2. void DFS(GraphAdjList GL, int i)

  3. {

  4. EdgeNode * p;

  5. visited[i] = TRUE;

  6. printf(“%c “,GL->adjList[i].data); //打印顶点，也可以其他操作

  7. p = GL->adjList[i].firstedge;

  8. while(p)

  9. {

  10. if (!visited[p->adjvex])

  11. DFS(GL, p->adjvex); //递归访问邻接点

  12. p = p->next;

  13. }

  14. }

邻接矩阵的算法为O（n^2^），邻接表为O（n+e），从效率的角度上来讲邻接矩阵优于邻接表

②广度优先遍历（Breadth_First_Search）

广度遍历是先把每个房间简单看一下，如果没找到再逐渐深入。

如上图，把图的层次变换成右边那样

如果说DFS是树的前序遍历，那么BFS则是树的层序遍历

邻接矩阵的算法

  1. void BFSTraverse(MGraph G)

  2. {

  3. int i, j;

  4. Queue Q;

  5. for (i = 0; i < G.numVertexes; i++)

  6. {

  7. visited[i] = FALSE;

  8. }

  9. InitQueue(&Q); //初始化一辅助用的队列

  10. for (i = 0; i < G.numVertexes; i++) //对每一个顶点做循环

  11. {

  12. if (!visited[i]) //若是未访问过就处理

  13. {

  14. visited[i] = TRUE; //访问后设置已访问

  15. printf(“%c “, G.vexs[i]); //打印顶点

  16. EnQueue(&Q, i); //将此顶点入队

  17. while (!QueueEmpty(Q)) //若队列不为空

  18. {

  19. DeQueue(&Q, &i); //将队中元素出队，赋值给i

  20. for (j = 0; j < G.numVertexes; j++)

  21. {

  22. //判断其他顶点若与当前顶点存在边且未访问过

  23. if (G.arc[i][j] == 1 && !visited[j])

  24. {

  25. visited[j] = TRUE; //将找到的此顶点标记为已访问

  26. printf(“%c “, G.vexs[j]); //打印顶点

  27. EnQueue(&Q, j); //将找到的此顶点入队

  28. }

  29. }

  30. }

  31. }

  32. }

  33. }

邻接表的算法

  1. void BFSTraverse(GraphAdjList GL)

  2. {

  3. int i;

  4. EdgeNode * p;

  5. Queue Q;

  6. for (i = 0; i < GL->numVertexes; i++)

  7. {

  8. visited[i] = FALSE;

  9. }

  10. InitQueue(&Q); //初始化一辅助用的队列

  11. for (i = 0; i < GL->numVertexes; i++) //对每一个顶点做循环

  12. {

  13. if (!visited[i]) //若是未访问过就处理

  14. {

  15. visited[i] = TRUE; //访问后设置已访问

  16. printf(“%c “, GL->adjList[i].data); //打印顶点

  17. EnQueue(&Q, i); //将此顶点入队

  18. while (!QueueEmpty(Q)) //若队列不为空

  19. {

  20. DeQueue(&Q, &i); //将队中元素出队，赋值给i

  21. p = GL->adjList[i].firstedge; //找到当前顶点边表链表头循环

  22. while(p)

  23. {

  24. //判断其他顶点若与当前顶点存在边且未访问过

  25. if (!visited[p->adjvex])

  26. {

  27. visited[p->adjvex] = TRUE; //将找到的此顶点标记为已访问

  28. printf(“%c “, GL->adjList[p->adjvex].data); //打印顶点

  29. EnQueue(&Q, p->adjvex); //将找到的此顶点入队

  30. }

  31. p = p->next

  32. }

  33. }

  34. }

  35. }

  36. }

6.最小生成树

数据结构

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！