图的有向存储

❶ 数据结构——图

转自： http://www.cnblogs.com/mcgrady/archive/2013/09/23/3335847.html

阅读目录

一，图的定义

二，图相关的概念和术语

三，图的创建和遍历

四，最小生成树和最短路径

五，算法实现

这一篇我们要总结的是图(Graph)，图可能比我们之前学习的线性结构和树形结构都要复杂，不过没有关系，我们一点一点地来总结，那么关于图我想从以下几点进行总结：

1，图的定义？

2，图相关的概念和术语？

3，图的创建和遍历？

4，最小生成树和最短路径？

5，算法实现？

一，图的定义

什么是图呢？

图是一种复杂的非线性结构。

在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素(除第一个和最后一个外)只有一个直接前趋和一个直接后继；

在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素(双亲节点)及下一层的多个元素(孩子节点)相关；

而在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。

图G由两个集合V(顶点Vertex)和E(边Edge)组成，定义为G=(V，E)

二，图相关的概念和术语

1，无向图和有向图

对于一个图，若每条边都是没有方向的，则称该图为无向图。图示如下：

因此，(Vi，Vj)和(Vj，Vi)表示的是同一条边。注意，无向图是用小括号，而下面介绍的有向图是用尖括号。

无向图的顶点集和边集分别表示为：

V(G)={V1，V2，V3，V4，V5}

E(G)={(V1，V2)，(V1，V4)，(V2，V3)，(V2，V5)，(V3，V4)，(V3，V5)，(V4，V5)}

对于一个图G，若每条边都是有方向的，则称该图为有向图。图示如下。

因此，和是两条不同的有向边。注意，有向边又称为弧。

有向图的顶点集和边集分别表示为：

V(G)={V1，V2，V3}

E(G)={，，，}

2，无向完全图和有向完全图

我们将具有n(n-1)/2条边的无向图称为无向完全图。同理，将具有n(n-1)条边的有向图称为有向完全图。

3，顶点的度

对于无向图，顶点的度表示以该顶点作为一个端点的边的数目。比如，图(a)无向图中顶点V3的度D(V3)=3

对于有向图，顶点的度分为入度和出度。入度表示以该顶点为终点的入边数目，出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。比如，顶点V1的入度ID(V1)=1，出度OD(V1)=2，所以D(V1)=ID(V1)+OD(V1)=1+2=3

记住，不管是无向图还是有向图，顶点数n，边数e和顶点的度数有如下关系：

因此，就拿有向图(b)来举例，由公式可以得到图G的边数e=(D(V1)+D(V2)+D(V3))/2=(3+2+3)/2=4

4，子图

故名思义，这个就不解释了。

5，路径，路径长度和回路

路径，比如在无向图G中，存在一个顶点序列Vp,Vi1,Vi2,Vi3…，Vim，Vq，使得(Vp,Vi1)，(Vi1,Vi2)，…,(Vim,Vq)均属于边集E(G)，则称顶点Vp到Vq存在一条路径。

路径长度，是指一条路径上经过的边的数量。

回路，指一条路径的起点和终点为同一个顶点。

6，连通图(无向图)

连通图是指图G中任意两个顶点Vi和Vj都连通，则称为连通图。比如图(b)就是连通图。下面是一个非连通图的例子。

上图中，因为V5和V6是单独的，所以是非连通图。

7，强连通图(有向图)

强连通图是对于有向图而言的，与无向图的连通图类似。

8，网

带”权值”的连通图称为网。如图所示。

三，图的创建和遍历

1，图的两种存储结构

1) 邻接矩阵，原理就是用两个数组，一个数组保存顶点集，一个数组保存边集。下面的算法实现里边我们也是采用这种存储结构。如下图所示：

2) 邻接表，邻接表是图的一种链式存储结构。这种存储结构类似于树的孩子链表。对于图G中每个顶点Vi，把所有邻接于Vi的顶点Vj链成一个单链表，这个单链表称为顶点Vi的邻接表。

2，图的两种遍历方法

1) 深度优先搜索遍历

深度优先搜索DFS遍历类似于树的前序遍历。其基本思路是：

a) 假设初始状态是图中所有顶点都未曾访问过，则可从图G中任意一顶点v为初始出发点，首先访问出发点v，并将其标记为已访问过。

b) 然后依次从v出发搜索v的每个邻接点w，若w未曾访问过，则以w作为新的出发点出发，继续进行深度优先遍历，直到图中所有和v有路径相通的顶点都被访问到。

c) 若此时图中仍有顶点未被访问，则另选一个未曾访问的顶点作为起点，重复上述步骤，直到图中所有顶点都被访问到为止。

图示如下：

注：红色数字代表遍历的先后顺序，所以图(e)无向图的深度优先遍历的顶点访问序列为：V0，V1，V2，V5，V4，V6，V3，V7，V8

如果采用邻接矩阵存储，则时间复杂度为O(n2)；当采用邻接表时时间复杂度为O(n+e)。

2) 广度优先搜索遍历

广度优先搜索遍历BFS类似于树的按层次遍历。其基本思路是：

a) 首先访问出发点Vi

b) 接着依次访问Vi的所有未被访问过的邻接点Vi1，Vi2，Vi3，…，Vit并均标记为已访问过。

c) 然后再按照Vi1，Vi2，… ，Vit的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过，依此类推，直到图中所有和初始出发点Vi有路径相通的顶点都被访问过为止。

图示如下：

因此，图(f)采用广义优先搜索遍历以V0为出发点的顶点序列为：V0，V1，V3，V4，V2，V6，V8，V5，V7

如果采用邻接矩阵存储，则时间复杂度为O(n2)，若采用邻接表，则时间复杂度为O(n+e)。

四，最小生成树和最短路径

1，最小生成树

什么是最小生成树呢？在弄清什么是最小生成树之前，我们需要弄清什么是生成树？

用一句语简单概括生成树就是：生成树是将图中所有顶点以最少的边连通的子图。

比如图(g)可以同时得到两个生成树图(h)和图(i)

知道了什么是生成树之后，我们就很容易理解什么是最小生成树了。所谓最小生成树，用一句话总结就是：权值和最小的生成树就是最小生成树。

比如上图中的两个生成树，生成树1和生成树2，生成树1的权值和为：12，生成树2的权值为：14，我们可以证明图(h)生成树1就是图(g)的最小生成树。

那么如何构造最小生成树呢？可以使用普里姆算法。

2，最短路径

求最短路径也就是求最短路径长度。下面是一个带权值的有向图，表格中分别列出了顶点V1其它各顶点的最短路径长度。

表：顶点V1到其它各顶点的最短路径表

从图中可以看出，顶点V1到V4的路径有3条(V1，V2，V4)，(V1，V4)，(V1，V3，V2，V4)，其路径长度分别为15，20和10，因此，V1到V4的最短路径为(V1，V3，V2，V4)。

那么如何求带权有向图的最短路径长度呢？可以使用迪杰斯特拉(Dijkstra)算法。

❷ 数据库中如何存储有向图

方法一：用邻接表的方法存储，
先开辟一块大小为n的存储空间，每一块存储空间为一个链表的开头，一次将数据增加到相应的链表里。
方法二：用邻接矩阵的方法存储，
开辟一个矩阵，在相接的两个点对应的序号的位置存储为1，其余为0，例如：矩阵a[100][100]，1和2相连，则a[1][2]=0

❸ 有向图的邻接表存储如图所示，请画出其邻接矩阵存储结构

有向图的邻接表存储如图所示，其邻接矩阵存储如图：

❹ 数据结构中的图 无向和有向，怎样存入文件

通常图都分为结点和弧，您存储图到文件可以按照这种方法来实现。
typedef struct {
int type; //标识是有向图还是无向图，例如0表示有向图，非0表示无向图
int vexnum;
char *arclist; //arclist指向一个vexnum*vexnum的矩阵，存储节点间的弧
}CHART;

1. 写文件时将上面的结构写入文件，然后将vexnum*vexnum的弧矩阵写入文件
2. 读文件时先读取上面的结构，然后依据vexnum先申请一个vexnum*vexnum大小的空间
赋值给arclist，然后从文件继续读取vexnum*vexnum大小的数据存储到arclist指向的数
组中。

❺ 图的存储结构——所存储的信息有哪些

一、邻接矩阵存储方法

邻接矩阵是表示顶点之间相邻关系的矩阵。

设G=(V，E)是具有n（n＞0）个顶点的图，顶点的顺序依次为0～n-1，则G的邻接矩阵A是n阶方阵，其定义如下：

（1）如果G是无向图，则：

A[i][j]=1：若(i,j)∈E(G) 0:其他

（2）如果G是有向图，则：

A[i][j]=1：若<i,j>∈E(G) 0:其他

（3）如果G是带权无向图，则：

A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他

（4）如果G是带权有向图，则：

A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j∞：其他

注意：带权图和不带权图表示的元素类型不同。

带权图（不论有向还是无向图）A[i][j]用double表示，不带权图（不论有向还是无向图）A[i][j]用int表示。

用一维数组G[ ]存储有4个顶点的无向图如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }

则顶点2和顶点0之间是有边的。

如：

邻接矩阵的特点如下：

（1）图的邻接矩阵表示是唯一的。

（2）无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上（或下）三角形阵的元素即可。

（3）不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵。因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。

（4）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。

（5）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。

（6）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

邻接矩阵的数据类型定义如下：

#define MAXV <最大顶点个数>

typedef struct

{ int no; //顶点编号

InfoType info; //顶点其他信息

} VertexType; //顶点类型

typedef struct //图的定义

{ int edges[MAXV][MAXV]; //邻接矩阵

int n，e; //顶点数，弧数

VertexType vexs[MAXV]; //存放顶点信息

} MGraph; //图的邻接矩阵表示类型

二、 邻接表存储方法

图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。

在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。

其中，表节点由三个域组成，adjvex指示与顶点i邻接的点在图中的位置，nextarc指示下一条边或弧的节点，info存储与边或弧相关的信息，如权值等。

表头节点由两个域组成，data存储顶点i的名称或其他信息，firstarc指向链表中第一个节点。

typedef struct ANode

{ int adjvex; //该边的终点编号

struct ANode *nextarc; //指向下一条边的指针

InfoType info; //该边的相关信息

} ArcNode; //边表节点类型

typedef struct Vnode

{ Vertex data; //顶点信息

ArcNode *firstarc; //指向第一条边

} VNode; //邻接表头节点类型

typedef VNode AdjList[MAXV]; //AdjList是邻接表类型

typedef struct

{ AdjList adjlist; //邻接表

int n,e; //图中顶点数n和边数e

} ALGraph; //完整的图邻接表类型

邻接表的特点如下：

（1）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。

（2）对于有n个顶点和e条边的无向图，其邻接表有n个顶点节点和2e个边节点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。

（3）对于无向图，邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。

（4）对于有向图，邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。

例， 给定一个具有n个节点的无向图的邻接矩阵和邻接表。

（1）设计一个将邻接矩阵转换为邻接表的算法；

（2）设计一个将邻接表转换为邻接矩阵的算法；

（3）分析上述两个算法的时间复杂度。

解：

（1）在邻接矩阵上查找值不为0的元素，找到这样的元素后创建一个表节点并在邻接表对应的单链表中采用前插法插入该节点。

void MatToList(MGraph g，ALGraph *&G)

//将邻接矩阵g转换成邻接表G

{ int i，j，n=g.n; ArcNode *p; //n为顶点数

G=(ALGraph *)malloc(sizeof(ALGraph));

for (i=0;i<n;i++) //给所有头节点的指针域置初值

G->adjlist[i].firstarc=NULL;

for (i=0;i<n;i++) //检查邻接矩阵中每个元素

for (j=n-1;j>=0;j--)

if (g.edges[i][j]!=0)

{ p=(ArcNode *)malloc(sizeof(ArcNode));

//创建节点*p

p->adjvex=j;

p->nextarc=G->adjlist[i].firstarc;

//将*p链到链表头

G->adjlist[i].firstarc=p;

}

G->n=n;G->e=g.e;

}

（2）在邻接表上查找相邻节点，找到后修改相应邻接矩阵元素的值。

void ListToMat(ALGraph *G，MGraph &g)

{ int i，j，n=G->n;ArcNode *p;

for (i=0;i<n;i++)

{ p=G->adjlist[i].firstarc;

while (p!=NULL)

{ g.edges[i][p->adjvex]=1;

p=p->nextarc;

}

}

g.n=n;g.e=G->e;

}

（3）算法1的时间复杂度均为O(n2)。算法2的时间复杂度为O(n+e)，其中e为图的边数。

❻ 图的五种存储结构

图的邻接矩阵（Adjacency Matrix）： 图的邻接矩阵用两个数组来表示图。一个一维数组存储图中顶点信息，另一个二维数组（一般称之为邻接矩阵）来存储图中的边或者弧的信息。从邻接矩阵中我们自然知道一个顶点的度（对于无向图）或者有向图中一个顶点的入度出度信息。

假设图G有n个顶点，则邻接矩阵是一个n*n的方阵。
1.对于如果图上的每条边不带权值来说，那么我们就用真（一般为1）和假（一般为0）来表示一个顶点到另一个顶点存不存在边。下面是一个图的邻接矩阵的定义：

邻接矩阵法实现带权值的无向图的创建如下：

按照如图输入各边（不重复）

测试程序如下：

结果可得该矩阵，证明创建树成功。 假设n个顶点e条边的创建，createGraph算法的时间复杂度为O（n+n*n+e）。如果需要创建一个有向图，那么和上面一样一个一个录入边下标和权值。

邻接矩阵这种存储结构的优缺点： 缺点是对于边数相对顶点较少的稀疏图来说会存在极大的空间浪费。假设有n个顶点,优点是对于有向完全图和无向完全图来说邻接矩阵是一种不错的存储结构，浪费的话也只浪费了n个顶点的容量。

在树的存储结构一节中我们提到对于孩子表示法的第三种：用一段连续的存储单元（数组）存储树中的所有结点，利用一个单链表来存储数组中每个结点的孩子的信息。对于图的存储结构来说，我们也可以利用这种方法实现图的存储

邻接表(Adjacency List): 这种数组与链表相结合的存储方法叫做邻接表。1.为什么不也用单链表存储图的结点信息呢？原因就是数组这种顺序存储结构读取结点信息速率快。对于顶点数组中，每个数据元素还需要存储一个指向第一个邻接顶点的指针，这样才可以查找边的信息2.图中每个顶点Vi(i > 0)的所有邻接点构成一个线性表 （在无向图中这个线性表称为Vi的边表，有向图中称为顶点作为弧尾的出边表） ，由于邻接点的不确定性，所以用链表存储，有多少个邻接点就malloc一个空间存储邻接点，这样更不会造成空间的浪费（与邻接矩阵相比来说）。3.对于邻接表中的某个顶点来说，用户关心的是这个顶点的邻接点，完全可以遍历用单链表设计成的边表或者出边表得到，所以没必要设计成双链表。

邻接表的存储结构：
假设现在有一无向图G，如下图：

从邻接表结构中，知道一个顶点的度或者判断两个顶点之间是否存在边或者求一个顶点的所有邻接顶点是很容易的。

假设现在有一有向图G，如下图：

无向图的邻接表创建示例如下：

假设在上图（无向图）中的V0V1V2V3顶点值为ABCD，则依据下面测试程序可得结果：

邻接表的优缺点： 优点是：邻接表存储图，既能够知道一个顶点的度和顶点的邻接结点的信息，并且更不会造成空间的浪费。缺点是邻接表存储有向图时，如果关心的是顶点的出度问题自然用邻接表结构，但是想了解入度需要遍历图才知道（需要考虑逆邻接表）。

十字链表(Orthogonal List) ：有向图的一种存储方法，它把邻接表和逆邻接表结合起来，因此在十字链表结构中可以知道一个顶点的入度和出度情况。
重新定义顶点表的结点如下图：

现在有一有向图如下图：

则它的存储结构示意图为：

其定义如下：

十字链表是用来存储有向图的，这样可以看出一个顶点的出入度信息。对于无向图来说完全没必要用十字链表来存储。

在无向图中，因为我们关注的是顶点的信息，在考虑节约空间的情况下我们利用邻接表来存储无向图。但是如果我们关注的是边的信息，例如需要删除某条边对于邻接表来说是挺繁琐的。它需要操作两个单链表删除两个结点。因此我们仿照十字链表的方式对边表结点结构重新定义如下图：

它的邻接多重表结构为：

多重邻接表的优点：对于边的操作相比于邻接表来说更加方便。比如说我们现在需要删除(V0,V2)这条边，只需将69步骤中的指针改为nullptr即可。

边集数组(edgeset array)： 边集数组是由两个数组组成，一个存储顶点信息，另一个存储边的信息，这个边数组中的每个数据元素由起点下标，终点下标，和权组成（如果边上含有权值的话）。
边数组结构如下图：

边集数组实现图的存储的优缺点：优点是对于边的操作方便快捷，操作的只是数组元素。比如说删除某条边，只需要删除一个数组元素。缺点是：对于图的顶点信息，我们只有遍历整个边数组才知道，这个费时。因此对于关注边的操作来说，边集数组更加方便。

❼ 有向图和无向图的有关知识

有/无 向图如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。[编辑]简单图一个图如果没有两条边，它们所关联的两个点都相同（在有向图中，没有两条边的起点终点都分别相同）；每条边所关联的是两个不同的顶点则称为简单图(simple graph)。简单的有向图和无向图都可以使用以上的“二元组的定义”，但形如(x,x)的序对不能属于E。而无向图的边集必须是对称的，即如果 ，那么 。[编辑]多重图若允许两结点间的边数多于一条，又允许顶点通过同一条边和自己关联，则为多重图的概念。它只能用“三元组的定义”。[编辑]基本术语在顶点1有一个环阶（Order）：图G中顶集V的大小称作图G的阶。子图（Sub-Graph）：图G'称作图G的子图如果以及 。生成子图（Spanning Sub-Graph）：指满足条件V(G') =V(G)的G的子图G。度（Degree）是一个顶点的度是指与该顶点相关联的总边数，顶点v的度记作d(v)。度和边有如下关系：。出度(out-degree) 和入度 (in-degree)：对有向图而言，顶点的度还可分为出度和入度。一个顶点的出度为 do ，是指有 do 条边以该顶点为起点，或说与该点关联的出边共有do条。入度的概念也类似。邻接矩阵环(loop)：若一条边的两个顶点相同，则此边称作环。路径（path）：从顶点 u 到顶点 v 的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk， ei的起点终点为vi及vi - 1； k 称作路径的长度； v_0=u，称为路径的起点； v_k=v，称为路径的终点。如果 u=v，称该路径是闭的，反之则称为开的；如果 v_1 , ... , v_k 两两不等，则称之为简单路径(simple path)（注意，u=v 是允许的）。行迹（trace）：如果路径P(u,v)中边各不相同，则该路径称为u到v的一条行迹。轨道（track）：即简单路径。闭的行迹称作回路（circuit），闭的轨道称作圈（Cycle）。（现存文献中的命名法并无统一标准。比如在另一种定义中，walk 对应上述的 path，path 对应上述的 track ， trail 对应上述的 trace。）距离（distance）： 从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称作从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）。距离矩阵桥（bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。[编辑]图的存储表示数组（邻接矩阵）存储表示（有向或无向）邻接表存储表示前向星存储表示有向图的十字链表存储表示无向图的邻接多重表存储表示一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域(adjvex)，用以指示与vi邻接的点在图中的位置，链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（info）。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。[编辑]图的遍历图的遍历方法有深度优先搜索法和广度(宽度)优先搜索法。深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：Boolean visited[MAX_VERTEX_NUM]; //访问标志数组Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数void DFSTraverse (Graph G, Status(*Visit)(int v)){ VisitFunc = Visit; for(v=0; v<G.vexnum; ++v) visited[v] = FALSE; //访问标志数组初始化 for(v=0; v<G.vexnum; ++v) if(!visited[v]) DFS(G, v); //对尚未访问的顶点调用DFS}void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图Gvisited[v]=TRUE; VisitFunc(v); //访问第v个顶点for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空(0)，//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。//若w是v的最后一个邻接点，则返回空(0)。 if(!visited[w]) DFS(G, w); //对v的尚未访问的邻接顶点w调用DFS}图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2, …, vi t，并均标记已访问过，然后再按照vi1,vi2, …, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：Boolean visited[MAX_VERTEX_NUM]; //访问标志数组Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数void BFSTraverse (Graph G, Status(*Visit)(int v)){ VisitFunc = Visit;for(v=0; v<G.vexnum, ++v) visited[v] = FALSE; initQueue(Q); //置空辅助队列Q for(v=0; v<G.vexnum; ++v) if(!visited[v]){ visited[v]=TRUE; VisitFunc(v); EnQueue(Q, v); //v入队列 while(!QueueEmpty(Q)){ DeQueue(Q, u); //队头元素出队并置为u for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w)) if(!Visited[w]){ //w为u的尚未访问的邻接顶点 Visited[w]=TRUE; VisitFunc(w); EnQueue(Q, w); } } }}
[编辑]图的重要类型树平面图连通图强连通图有向无环图AOV网AOE网完全图：每一对不同顶点间都有边相连的的图，记作Kn。二分图：顶集，且每一条边都有一个顶点在X中，而另一个顶点在Y中。完全二分图：二分图G中若任意两个X和Y中的顶点都有边相连。若，则图G记作Km,n。正则图：如果图中所有顶点的度皆相等，则此图称为正则图欧拉图:存在经过所有边一次(可以多次经过点)的路径的图哈密顿图:存在经过所有点一次的路径的图

❽ 图的定义与存储

图状结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图是 比树更一般、更复杂的非线性结构，常被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。

图（Graph）是由非空的顶点集合和一个描述顶点之间的关系——边（或者弧）的集合组成的，其形式化定义为：G=(V,E)、V={v1|v1包含data object}、E={(v1,vj)|(vi,vj 包含V^P(vj,vj)。其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(v1,vj）表示一条边。如：G2=(V2,E2)、V2={v1,v2,v3,v4}、E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

1、无向图：在一个图中，如果任意两个顶点构成的偶对(vi,vj）包含E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。

2、有向图：在一个图中，如果任意两个顶点构成的偶对<vj,vj>包含E是有序的（有序对常常用尖括号“<>”表示），即顶点之间的连线是有方向的，则称该图为有向图。

6、顶点的度、入度、出度：顶点的度（Degree）是指依附于某顶点v的边数，通常记为TD(v)。顶点v的入度是指以顶点v为终点的弧的数目，记为ID(V)；出度是指以顶点v为始点的弧的数目，记为OD(V)。有TD(V)=ID(v)+OD(v)。

7、边的权、网：与边有关的数据信息称为权(Weight)。在实际应用中，权值可以有某种含义。例如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间或其他代价等。边上带权的图称为网或网络（network）。

8、路径、路径长度：顶点vp到顶点vq之间的路径（path）是指顶点序列vp、vi1、vi2、···、vim、vq。其中，（vp，vi1）、（vi1，vi2）、···、（vim，vq）分别为图中的边。路径上边的数目称为路径长度。

9、简单路径、回路、简单回路：序列中顶点不重复出现的路径称为简单路径。路径中第一个顶点与最后一个顶点相同的 路径称为回路或环（Cycle）。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。

10、子图：对于图G=（V，E），G'=（V',E'），若存在 V'是V的子集， E'是E的子集，则称图 G'是G的的一个子图。

11、连通、连通图、连通分量：在无向图中，如果从一个顶点vi到另一个顶点vj(i=!j)存在路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量，极大连通子图是指在保证连通与子图的条件下，包含原图中所有的顶点与边。 如下图：

12、强连通图、强连通分量：对于有向图来说，若图中任意一对顶点vi和vj（i=!j）均存在从一个顶点vi到另一个顶点vj和从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量，极大强连通子图的含义同上。

13、生成树：所谓连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图，所谓极小连通子图是指在包含所有顶点且保证连通的前提下尽可能少地包含原图中的边。生成树必定包含且仅包含连通图G的n-1条边。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。

14、生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。

将上图存储到计算机中，请设计一个数据结构并将其合理存储起来？

所谓邻接矩阵（Adjacency Matrix）的存储结构，就是用一维数组存储图中的顶点信息，用矩阵表示图中各顶点的信息，用矩阵表示图中各顶点的信息，用矩阵表示图中各顶点之间的邻接关系。假设图G=(V,E)有n个确定的顶点，即V ={v0,v1，···，vn-1}，则表示G中各顶点相邻关系的矩阵为一个n×n的矩阵，矩阵的元素为：

A[i][j]={1,若(vi,vj)或<vi,vj>是E(G)中的边 ；2，若(vi,vj）或<vi,vj>不是E(G)中的边。

若G是网，则邻接矩阵可定义为：

A[i][j]={wij,若(vi,vj)或<vi,vj>是E(G)中的边 ；0或&，若(vi,vj）或<vi,vj>不是E(G)中的边。

（1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上或下三角矩阵的元素即可。

（2）对于无向图，邻接矩阵的第i行或第i列非零元素或非&元素的个数正好是第i个顶点的度TD(vi)。

（3）对于有向图，邻接矩阵的第i行货第i列非零元素或非&元素的个数正好是第i个顶点的出度OD(vi)或如度ID(vi)。

（4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

在实际应用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外，还有图的顶点树和边树。故可将其形式描述如下：

邻接表（Adjacency List）是图的一种顺序存储于链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图邻接表。

在邻接表表示中有两种结点结构：一种是顶点表的结点结构，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成。另一种是边表即邻接表结点，它由邻接点域（adjvex）和指向下一条邻接边的指针域（next）构成。对于网的边表需再增设一个存储边上的信息（如权值等）的域（info）。