NOIP高中信息技术竞赛资料 - -数据结构(10)

第6章 图

6.2 图的存储结构

图的存储表示方法很多，这里介绍两种最常用的方法。至于具体选择哪一种方法，主要取决于具体的应用和要施加的操作。

为了适合用C语言描述，以下假定顶点序号从0开始，即n个顶点图G顶点集是V(G)={v0,v1,…,vn-1}。

1.图的邻接矩阵表示法 （1）图的邻接矩阵

设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是元素具有如下性质的n阶方阵：

?1A[i,j]???0(vi,vj)或?vi,vj?是E(G)中的边(vi,vj)或?vi,vj?不是E(G)中的边（2）图的邻接矩阵表示法

①用邻接矩阵表示顶点间的相邻关系； ②用一个顺序表来存储顶点信息。

V0 V3 V1 V2 ?0??1A??0??1?

101101001??1?0??0??图6.7 一个无向图的邻接矩阵表示

（3）网络的邻接矩阵

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

(vi,vj)或?vi,vj?是E(G)中的边?wijA[i,j]??(vi,vj)或?vi,vj?不是E(G)中的边 ?0或?其中：wij表示边上的权值；∞表示一个计算机允许的、大于所有边上权值

的数。网络的邻接矩阵如图6.8。

B 5 D 9 3 A 4 6 C 7 E 8 ??963????9?45???A??64??7????35??8????78???? 图6.8 一个网络的邻接矩阵表示

第6章 图

【课堂实践6.1】分别写出图6.1的无向图G1和图6.2的有向图G2的邻接矩阵。

（4）图的邻接矩阵存储结构的描述

#define VertexNum 20 //最大顶点数 typedef char VertexType;//顶点类型定义 typedef int EdgeType;//权值类型定义 typedef struct{

VertexType vexs[VertexNum]; //顶点表

EdgeType edges[VertexNum][VertexNum];//邻接矩阵，可看作边表 int n,e;//图中当前的顶点数和边数 }MGraph;

（5）建立无向网络的算法

void CreateMGraph(MGraph *G){//建立无向网(图)的邻接矩阵表示

int i,j,k,w;

scanf(\输入顶点数边数 getchar();

printf(\读入顶点信息，建立顶点表:\

for(i=0;in;i++) //读入顶点信息，建立顶点表

G->vexs[i]=getchar();

getchar();

for(i=0;in;i++)

for(j=0;jn;j++) G->edges[i][j]=0; //邻接矩阵初始化

for(k=0;ke;k++){//读入e条边,建立邻接矩阵 scanf(\输入权w G->edges[i][j]=w; G->edges[j][i]=w; } }

2.图的邻接表表示法

（1）图的邻接表

对于图G中的每个顶点vi，把所有邻接于vi的顶点vj链成一个带头结点的

第6章 图

单链表，这个单链表就称为顶点vi的邻接表(Adjacency List)。

（2）邻接表的结点结构 ①表结点结构

邻接表中每个表结点均有两个域

（1）邻接点域adjvex,存放与vi相邻接的顶点vj的序号j； （2）链域next,将邻接表的所有表结点链在一起。

注意：若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域。 ②头结点结构

顶点vi邻接表的头结点包含两个域 （1）顶点域vertex,存放顶点vi的信息； （2）指针域firstedge,vi的邻接表的头指针。 （3）无向图的邻接表

对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。

图6.7的无向图的邻接表如图6.9。

序号 vertex firstedge V0 1 3 ∧ 0 1 V1 0 2 3 ∧ V2 2 1 ∧

3 V3 0 1 ∧

顶点表 边表

注意：n个顶点e

图6.9 图的邻接表表示

条边的无向图的邻接表表

示中有n个顶点表结点和2e个边表结点。

（4）有向图的邻接表

对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。

图6.2的有向图G2的邻接表如图6.10(a)。

注意：n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。

（5）有向图的逆邻接表

第6章 图

在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。

入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。

图6.2的有向图G2的逆邻接表如图6.10(b)。

0 1 2 3 V1 V2 V3 V4 ∧ 3 0 ∧ ∧ 2 1 ∧ 0 1 2 3 V1 V2 V3 V4 3 ∧ ∧ ∧ ∧ 0 0 2

（6）图的邻接表存储结构的描述 图的邻接表存储结构的描述

typedef struct node{//边表结点定义 int adjvex; //邻接点域 struct node *next; //链域

//若要表示边上的权，则应增加一个数据域 }EdgeNode;

typedef struct vnode{ //顶点表结点定义 VertexType vertex; //顶点域 EdgeNode *firstedge;//边表头指针 }VertexNode;

typedef VertexNode AdjList[VertexNum];//AdjList是邻接表类型 typedef struct{//邻接表定义 AdjList adjlist;//邻接表 int n,e; //图中当前顶点数和边数 }ALGraph;

(a) 邻接表 (b) 逆邻接表

图6.10 图6.2中G2的邻接表和逆邻接表

（7）建立无向图的邻接表算法 建立无向图的邻接表算法：

void CreateALGraph(ALGraph *G){//建立无向图的邻接表表示

int i,j,k; EdgeNode *s;

第6章 图

scanf(\读入顶点数和边数 getchar();

for(i=0;in;i++){//建立顶点表

G->adjlist[i].vertex=getchar(); //读入顶点信息 G->adjlist[i].firstedge=NULL;//边表置为空表 }

for(k=0;ke;k++){//建立边表

scanf(\读入边(vi,vj)顶点对序号

s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点 s->adjvex=j; //邻接点序号为j s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s;//将新结点*s插入顶点vi的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i; //邻接点序号为i s->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=s;//将新结点*s插入顶点vj的边表头部 } }

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库NOIP高中信息技术竞赛资料 - -数据结构(10)在线全文阅读。