图

图的基本概念

图是一种非线性数据结构。非线性指的是结点之间的关系可以是任意的，任意两个数据元素之间都可能相关。参考程杰老师的《大话数据结构》，可以简单的理解为人际关系，会考虑多对多的关系，而非简单的一对一、一对多。

在图中的数据元素称为顶点，顶点之间的逻辑关系称为边，没有方向的边为无向边，用无序偶对来表示，写成（A,D）。有向边则是有方向的边，也可以称为弧。箭头从A指向D，A是弧尾，D是弧头，<A,D>表示弧，不可以写成<D,A>。 无向图中任意两个顶点之间都存在边，称为无向完全图，含有n个顶点的无向完全图有n*(n-1)/2 条边。有向完全图则存在n*（n-1）条边。若图中顶点为n，边数为e，如果e<nlbn,则该图为稀疏图，否则为稠密图。 把以顶点v为终点的边的数目称为入度，以v为起点的边数常称为出度。 图的边或者弧有一个与他相关的数，这个数称为权。带权的图称为网络。沿路径经过的边数称为路径的长度。有向图中，有一个顶点，从该顶点出发有路径可以到达图中其他的所有顶点，这个点称为图的根,这个图是有根图。 无向图中，任意两个顶点都连通，叫连通图，他的极大连通子图称为图的连通分量。有向图中任意两个顶点从vi到vj和从vj到vi都有路径，称为强连通图。

图的存储方法

邻接矩阵

邻接矩阵方法是用一个对称的矩阵来记录各个顶点时间是否存在边。如果存在边，元素值为对应的权值。i=j，元素值为0（对角线），不存在边，元素值为无穷大。

#include<stdio.h> #include<string.h> #include<stdlib.h> typedef char vertexType; typedef int edgeType; typedef struct{ vertexType vexs[100]; edgeType arc[100][100]; int vexnumber,edgenumber; }MGraph; void createMGraph(MGraph *G){ int i,j,k,w; printf("请输入顶点数和边数\n"); scanf("%d,%d",&G->vexnumber,&G->edgenumber); //读取顶点数和边数 for(i=0;i<G->vexnumber;i++){ scanf(&G->vexs[i]); } for(i=0;i<G->vexnumber;i++){ for(j=0;j<G->vexnumber;j++){ G->arc[i][j]=-1; } } for(k=0;k<G->vexnumber;k++){ printf("请输入边（vi，vj）的上下标i，j和权值w\n"); scanf("%d,%d,%d",&i,&j,&w); G->arc[i][j]=w; G->arc[j][i]=w; //设置对称矩阵 } }

邻接表

是一种顺序存储和链式存储相结合的存储方法。存储结构由两部分组成，使用一个具有两个域的结构体数组来存储，这个数组称为顶点表。一个域称为指针域，另一个称为顶点域。

typedef char vertexType; typedef int edgeType; typedef struct edgenode{ //邻接链表结点 int adjvex; edgeType weight; struct edgenode *next; //链域 }edgenode; typedef struct{ vertexType vertex; //顶点域 egdenode *link; //指针 }vexnode; vexnode ga[n]; //顶点表

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

void createAdjlist(vexnode ga[]){ //建立无向图的邻接表 int i,j,k; edgenode *s; for(i=0;i<N;i++){ ga[i].vertex=getchar(); //读入顶点信息 ga[i]->link=NULL; //边表头指针初始化 } for(k=0;k<E;k++){ //建立边表 scanf("%d %d",&i,&j); //读入顶点序号 s=malloc(sizeof(edgenode)); //生成邻接点序号为j的边表结点*s s->adjvex=j; s->next=ga[i].link; ga[i].link=s; //将s插入顶点vi的边表头部 s=malloc(sizeof(edgenode)); //生成邻接点序号为i的边表结点 s->adjvex=i; s->next=ga[j].link; ga[j].link=s; //将s插入顶点vj的边表头部 } }

如果要建立有向的邻接表，只须去除生成邻接点序号为i的边表结点s，并将s插入顶点vj边表头部的那一段语句即可。要加上权的话就在边表的每个结点中增加一个权的数据域。

一个图邻接矩阵表示是唯一的，邻接表表示不是唯一的。取决于建立邻接表的算法和边的输入次序。判断vi，vj是否是一条边只需判断矩阵中的arcc[i][j]是否为0即可。而在邻接表中需要扫描对应的邻接链表。

图的遍历

分为以邻接矩阵为存储结构的遍历（A) 和以邻接表为存储结构的遍历（L）

深度优先遍历

图的深度优先遍历（DFS）类似于树的先序遍历。

邻接矩阵：

int visited[n]; MGraph g; void DFSA(int i){ int j; printf("node:%c\n",g.vexs[i]); visited[i]=1; for(j=0;j<n;j++){ if((g.arc[i][j]==1)&&(visited[j]==0)) DFSA(j); } } //DFSA

邻接表：

int visited[n]; vexnode ga[n]; void DFSL(int i){ edgenode *p; printf("%c\n",ga[i].vertex); visited[i]=1; p=ga[i].link; while(p!=NULL){ if(visited[p->adjvex]==0) DFSL(p->adjvex); p=p->next; } } //DFSL

广度优先遍历

邻接矩阵：

int visited[n]; MGraph g; sequeue *q; void BFSA(int k){ int i,j; setnull(q); printf("%c\n",g.vexs[k]); visited[k]=1; enqueue(q,k); while(!empty(q)){ i=dequeue(q); for(j=0;j<n;j++) if((g.arc[i][j]==1)&&visited[j]!=1){ printf("%c\n",g.vexs[j]); visited[j]=1; enqueue(q,j); } } }

邻接表：

int visited[n]; vexnode ga[n]; sequeue *q; void BFSL(k){ int i; edgenode *p; setnull(q); printf("%c\n",ga[k].vertex); visited[k]=1; enqueue(q,k); while(!empty(q)){ i=dequeue(q); p=ga[i].link; while(p!=NULL){ if(visited[p->adjvex]!=1){ printf("%c\n",ga[p->adjvex].vertex); visited[p->adjvex]=1; enqueue(q,p->adjvex); } p=p->next; } } } //BFSL