数据结构6——初步认识“图”
数据结构6——初步认识“图”
线性表（线性结构）是一对一； 树（层次结构） 是一对多； 那么图（网状结构）就是多对多。
ps：本节无具体的代码实现。
一、图的基本概念
1.1 图的定义
在图中，通常把数据元素称为顶点（Vertex），把顶点之间的关系称为边（Edge）。图由两部分组成：顶点和边，表示为G=(V,E)。
根据边的有向性，可把图分为两类：
（1）无向图。图中任意一条边都是无向的。
（2）有向图。图中的边是有向的，称为有向图。有向边有称为“弧”。一条从A到B的弧，称B是弧头，A是弧尾。
网：一种特殊的图。有时图的边或弧带有和它相关的具有一定意义的实数， 称为权（Weight），带权的图称为网（Network）。无向网：带权无向图。有向网：带权有向图。
1.2 图的基本术语
（1） 邻接、依附与边/弧的表示
有向图：如果从v到w存在一条弧，记为<v,w>并称v邻接到w；w邻接自v；w是v的邻接点<v,w>弧依附于顶点v、w。
无向图：v与w之间如果存在一条边，记为(v,w)称v与w互为邻接点。边(v,w)依附于顶点v、w。
在无向图中，( v, w ) 和 ( w, v )是等价的，而在有向图中，弧具有方向性，因此 < v, w > ≠ < w, v >
在图结构中，顶点之间的逻辑关系： 邻接。
（2） 度、入度和出度
在无向图中，顶点V的度（Degree）是指依附于V的边的条数，记为TD (V)，即V的邻接点个数。
在有向图中： ① 入度：以顶点V为弧头的弧的数目，称为V的入度 （In Degree），记为ID (V)； ② 出度：以顶点V为弧尾的弧的数目，称为V的出度 （Out Degree），记为OD (V)。 ③ 度：TD (V) = ID (V) + OD (V)
（3）路径和回路
路径：从一个顶点vi走到另一个顶点vj所经过的顶点序列 (不唯一)
路径的长度：路径中边的数目（顶点个数－1）
回路（或环）：第一个顶点和最后一个顶点相同的路径称为回路。如（0,1,2,0）、（4,6,5,4）、（0,1,4,6,5,4,1,2,0）
简单路径：顶点不重复出现的路径（没有回路的路径）
简单回路：除了第一个顶点与最后一个顶点外，其余顶点 不重复出现的回路。
（4）完全图、稀疏图和稠密图
无向完全图： 无向图中，任意两个顶点都存在边。N个顶点无向完全图边的条数e=N(N-1)/2
有向完全图： 有向图中，任意两个顶点都存在一对方向相反的弧。 N个顶点有向完全图弧的条数e=N(N-1)
（5）子图
设有两个图G1=(V1, E1)和G2=(V2, E2) ，如果V1是V2的子集， E1也是E2的子集，则称G1是G2的子图。
（6）（强）连通图与（强）连通分量
连通：从顶点V到顶点W有一条路径，则说V和W是连通的。
在无向图中：
· 连通图：如果图G中任意两个顶点都是连通的， 则称图G是连通图。
· 非连通图（特点：由若干个局部连通的子图组成）
· 连通分量：非连通图中的极大连通子图。极大：包含所有连通的顶点，以及与顶点关联的所有边，即尽可能最大的部分。
在有向图中：
· 顶点V与顶点W各自都有路径相通，则说V和W是强连通的
· 强连通图：任意两个顶点都是强连通（两个方向都连通）的图
· 强连通分量：非强连通图的极大强连通子图
（7）生成树与生成森林
生成树：一个（无向）连通图的极小连通子图。极小：保证所有顶点连通所需的最少边。
特点：（1）连通、不存在回路 （2）只要添加任何一条边，必定存在回路 （3）n个顶点（无向）连通图，其生成树的边必为n-1 （4）生成树中任意两个顶点间的路径是唯一的 （5）生成树并不唯一
推论1：如果一个（无向）图有n个顶点，但边数小于n-1 则它必是非连通图（非连通图的快速初步诊断）。
生成森林：非连通图的每个连通分量的生成树集合。有向图的生成树是一棵有向树。
二、图的抽象数据类型
三、图的存储结构
3.1邻接矩阵
用两个数组来实现： 一个一维数组用于存储顶点信息； 一个二维数组（称为邻接矩阵）用于存放数据元素的关系（即顶点间的边或弧）。
图的邻接矩阵：有N个顶点的图的邻接矩阵是N阶方阵。若图中存在边（Vi, Vj）或弧< Vi, Vj >，A[i,j] =1； 若图中不存在边（Vi, Vj）或弧< Vi, Vj >，A[i,j] =0。 对角线一定为0。那么无向图的邻接矩阵一定是对称矩阵。
网的邻接矩阵（边带有权值）：若图中存在边(Vi, Vj)或弧< Vi, Vj >， 且其上有权值weigh，即A[i,j] =weightt；若图中不存在边（Vi, Vj）或弧 < Vi, Vj > ，即A[i,j] =MAXVAL（ ）。
邻接矩阵结构
#define INFINITY INT_MAX // 最大值∞
#define MAX_VERTEX_NUM 20 // 最大顶点个数
// 类型标志{有向图,有向网,无向图,无向网}
enum GraphKind {DG, DN, AG, AN};
struct MGraph{
int vexs[ Max_Vertex_Num ]; //顶点数组
int arcs[ Max_Vertex_Num ][ Max_Vertex_Num ];//邻接矩阵
int vexnum; //当前顶点数
int edgenum; //当前边/弧数
GraphKind kind;//图的种类标志
}
用邻接矩阵作存储结构建立无向网的算法
void CreateGraph( MGraph &G )
{
cin>>G.vexnum>>G.edgenum;//输入顶点和边的数目
for (i = 0 ; i < n ; i ++ )
{
cin>>G.vexs[i];//构造顶点数组
}
//初始化邻接矩阵
for ( i = 0 ; i < n ; i ++ )
{
for ( j = 0 ; j < n ; j ++ )
{
G.arcs[i][j] = INFINITY;
}
}
//输入边的信息
for ( i = 0 ; i < e ; i ++ )
{
cin>>beginNode;//输入边依附的第一个顶点编号
cin>>endNode;//输入边依附的第二个顶点编号
cin>>weight;//输入边的权值
G.arcs[endNode][beginNode] = G.arcs[beginNode][endNode]=weight;
}
}
使用邻接矩阵的优点： ① 便于查找图中任一条边（弧）或边（弧）上的 权值； ② 便于计算图中任一顶点的度； ③ 便于查找任一顶点的所有邻接点。
3.2邻接表
在邻接矩阵中，边关系是采用顺序存储结构（二维数组）存放， 而邻接表则采用单链表的方式来存放边关系。为图中每个顶点建立一个单链表，存放依附于该顶点的边信息（如该边的另一个顶点以及边的权值等）。
const MAX_VERTEX_NUM = 20;
typedef enum {DG, DN, AG, AN} GraphKind;
typedef struct EdgeNode { // 边表结点的结构
int adjvex; // 邻接点的位置（序号）
struct EdgeNode *nextedge; // 指向下一条边的指针
int weight; // 与边相关的权值，无权则为0
} ;
typedef struct VexNode { // 顶点结点的结构
VexType data; // 顶点信息
EdgeNode *firstedge; // 单链表的头指针
};
typedef struct { // 图的邻接表结构定义
VexNode vexs[ MAX_VERTEX_NUM ]; // 顶点表结点数组
int vexnum, edgenum; // 图的当前顶点数和边数
GraphKind kind; // 图的种类标志
} ALGraph;
邻接表的优点： 容易计算顶点的度 （有向图：出度－邻接表、入度－逆邻接表）；容易判断任意两个顶点之间是否存在边； 容易找到与v的所有邻接点。
四、图的遍历
从图的某一顶点出发，访问图中所有顶点，且使每个顶点仅被访问一次。 图的遍历有两种方式：深度优先搜索遍历和广度优先搜索遍历。
4.1深度优先搜索遍历
深度优先搜索遍历可以类比树的前序遍历。从图的某一顶点v出发：（1）先访问顶点v0（类似于根结点） （2）以v0的邻接点v1、v2和v3为“出发点”，分别遍历它们所在的子图
我们设立一个访问标志数组 visited[w]，以判断邻接点是否已经被提前访问。visit[wi]表示顶点wi是否已经被访问：如果顶点wi被访问，visited[wi]标记 为true，表示已被访问，否则为false。
bool visited[Max_Vertex_Num ];//标记数组—布尔类型即可。假定初始为false
// 从顶点v出发，深度优先搜索遍历连通图 G
void DFS(Graph G, v)
{
visited[v] = TRUE;
Visit (v);//访问v，并设置visited[v]为true，表示v已被访问
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//w从v的第一个邻接点开始，到最后一个邻接点
{
if (!visited[w])
DFS(G, w); // 以未被访问的邻接点w开始 递归调用DFS
}
}
非连通图如何进行深度优先遍历？以顶点v1出发进行深度优先遍历，一定可以把v1所在连通子图的顶点遍历完。 如果存在没被访问的顶点，则说明还有没被访问的另一个连通子图，则从该子图的任意顶点（如v3）出发再进行深度优 先遍历。依次类推，直到所有连通子图被遍历完为止。
void DFSTraverse(Graph G)
{
// 对图 G 作深度优先遍历。
for (v=0; v<G.vexnum; ++v)
{
visited[v] = FALSE; // 访问标志数组初始化
}
for (v=0; v<G.vexnum; ++v) //确保每个顶点都被访问
{
if (!visited[v])
{
DFS(G, v);
}
// 对未被访问的顶点为起点，再调用DFS
}
4.2广度优先搜索遍历
从图的某一顶点v出发 （1）先访问顶点v （2）依次访问v中未被访问的邻接点v1、v2….vk （3）按照v1－>vk的次序，访问v1未被访问的邻接点、v2未被访问的邻接点，...，vk未被访问的邻接点 （4）直至所有（与v相通的）顶点都被访问
第一遍时，访问v1、v2、v8 ；第二遍时，访问v7、v3、v5； 第三遍时，访问v6、v4。
void BSF( Graph G , v )
{
创建一个空队列Q
visited[v] = TRUE;
Visit(v); // 访问v
EnQueue(Q, v); // v入队列
while (!QueueEmpty(Q))
{
DeQueue(Q, v); // 队头元素出队
for(w从第一个v的邻接点开始，到最后一个邻接点)
if ( !visited[w] )
{
visited[w]=TRUE;
Visit(w);
EnQueue(Q, w); // 访问的顶点w入队列
} // if
} // while
}//end BSF
void BFSTraverse(Graph G)
{
for (v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //初始化访问标志
//开始遍历过程：
for ( v=0; v<G.vexnum; ++v )//确保每个顶点都被访问
{
if ( !visited[v])
{
BFS( G , v );
}
}
} // BFSTraverse