首页 > 代码库 > 1.7图结构

1.7图结构

  数据元素存在3种关系:

1)先行后续,即一个数据元素有一个直接前驱和一个直接后继,这种组织结构叫线性结构;

2)层次关系,每一层上数据元素可能和下一层中的多个数据元素相关,但只和上一层中的一个数据元素相关,这类组织结构叫树结构;

3)数据元素间是”一对多“或者”多对一“的关系,即任意两个数据元素之间都可以存在关系,这类组织结构叫图结构;

 

图:由顶点的非空有限集合V(由N>0个顶点组成)与边的集合E(顶点之间关系)所构成的,分为有向图和无向图。

图的存储形式:邻接矩阵存储、邻接表存储。

 

邻接矩阵存储方法也称为数组存储方法,核心思想利用两个数组来存储一个图。一个数组是一维数组,用来存放图中数据;一个是二维数组,用来表示图中顶点之间的关系。//详见课本

 

邻接表存储方法适合存储稀疏矩阵图(边的数目很少的图)。

邻接表存储方法是一种顺序分配与链式分配相结合的存储方法,由链表和顺序数组组成。链表用来存放边的信息,数组用来存放顶点的数据信息。具体来说,对于图中的每一个顶点分别建立一个链表,如果一个图具有n个顶点,其邻接表就含有n个线性链表。每个链表前面设置一个头结点,称为顶点结点,顶点结点的结构图如下所示:

vertex  next

顶点域vertex用来存放顶点的数据信息,指针域next用来指向依附于顶点vertex的第一条边。通常将一个图的n个顶点结点放到一个统一的数组中进行管理,并用该数组的下标表示顶点在图中的位置。

而在每一个链表中,链表的每一个结点称之为边结点,它表示依附于对应的顶点结点的一条边。边结点结构如下:

adjvex weight  next

adjvex域存放该边的另一端顶点在顶点数组中的位置(数组下标);weight存放边的权重,对于无权重的图,忽略此项;next是一个指针域,指向下一个边结点,最后一个边结点的next域为NULL;

 

邻接表的定义

#define MAX_VERTEX_NUM 20	
typedef struct ArcNode {//单链表中结点类型 
	int adjvex;			//该边指向的顶点在顺序表中位置(数组下标) 
	struct ArcNode *next;//指向下一条边的指针 
	infoType *weight;	//边的权重,可省略 
}ArcNode;

typedef struct VNode{
	VertexType data;	//顶点中的数据信息 
	ArcNode *firstarc;	//指向单链表,即指向第一条边 
}VNode;

VNode G[MAX_VERTEX_NUM];//VNode类型的数组G,是图中顶点的存储容器

 

  

图的创建

CreateGraph(int n,VNode G[]) {
	int i,e;
	ArcNode *p,*q;
	printf("input the information of the vertex\n");
	for(i=0;i<n;i++) {
		Getdata(G[i]);//得到每个顶点中的数据
		G[i].firstarc=NULL;//初始化第一条边为空
	}
	
	for(i=0;i<n;i++) {
		printf("Creat the edges for the %dth vertex\n",i);
		scanf("%d",&e);//输入边指向的顶点下标
		while(e!=-1) {
			p = (ArcNode *)malloc(sizeof(ArcNode));//创建一条边
			p->next=NULL;  //链表结点的next域置为NULL
			p->adjvex = e;   //将该边指向顶点的信息赋给adjvex
			if(G[i].firstarc == NULL)	G[i].firstarc=p;  //i结点的第一条边
			else	q->next = p;   //下一条边
			q=p;
			scanf("%d",&e);
		}
	}
} 

  注意:创建边的过程和创建链表过程类似。当输入为-1时,表示该顶点依附的边创建完毕,即该顶点指向的单链表创建完毕。

 

图的遍历操作要求是求解图的连通性问题,进行拓扑排序,求解最短路径,求解关键路径等运算的基础。

深度优先搜索:

//深度优先搜索一个连通图
void DFS(VNode G[],int v) { int w; visit(v); visited[v]=1; w=FirstAdj(G,v);//找到顶点v的第一个邻接点,如果无邻接点,返回-1 while(w!=-1) { if(visited[w]==0) DFS(G,w); w=NextAdj(G,v);//找到顶点v的下一个邻接点,如果无邻接点,返回-1 } } //对图G=(V,E)进行深度优先搜索的主算法 void Travel_DFS(VNode G[],int visited[],int n) { int i; for(i=0;i<n;i++) visited[i]=0; for(i=0;i<n;i++) if(visited[i]==0) DFS(G,i); }

  

宽度优先搜索:

void BFS(VNode G[],int v) {
	int w;
	visit(v);
	visited[v]=1;
	EnQueue(q,v);// 顶点v入队列 
	while(!emptyQ(q)) {
		DeQueue(&q,&v);//出队列,元素由v返回 
		w=FirstAdj(G,v);//找到顶点v的第一个邻接点,如果无邻接点,返回-1
		while(w!=-1) {
			if(visited[w]==0) {
				visit(w);
				EnQueue(q,w);//顶点w入队列 
				visited[w]=1;
			}
			w=NextAdj(G,v);//找到顶点v的下一个邻接点,如果无邻接点,返回-1 
		}
	}
}

void Travel_BFS(VNode G[],int visited[],int n) {
	int i;
	for(i=0;i<n;i++)
		visited[i]=0;
	for(i=0;i<n;i++)
		if(visited[i]==0)
			BFS(G,i);
}

  

1.7图结构