[数据结构与算法]图的总结

1.图的定义

Graph=（V，R）
V={x|x∈DataObject}
R={VR}
VR={<x,y>|P(x,y) ∧（x，y）∈V}

<x,y>?表示从顶点x到顶点y的一条弧，

x：弧尾或起始点

y：弧头或终端点

< >表示有向图 ，（）表示无向图

2.基本术语

n：图中顶点个数? ? e：图中边或弧的数目

如果不考虑顶点到自身的边或弧

对于无向图，边数范围（0，n（n-1）/2）。若图中每个顶点和其余n-1?个顶点都有边相连，则边数为n（n-1）/2，那么这样的无向图为无向完全图。

对于有向图，边数范围（0，n（n-1））。若图中每个顶点和其余n-1?个顶点都有弧相连，则边树为n（n-1），那么这样的有向图为有向完全图。

对于有很少条边的图称为稀疏图。

3.度

无向图：顶点v的度是指和v相关联边的数目，记作TD（v）

无向图：度分入度和出度。以顶点v为弧头的弧的数目称为该顶点的入度，记为ID（v）。以顶点v? ? ? ? ? ? ? ? 为弧尾的弧的数目称为该顶点的的出度，记为OD（v）。TD（v）=ID（v）+OD(v）

4.权与网

在实际应用中，图的边或弧往往与具有一定意义的数字有关，即每一条边都有与他相关的数，称为权。这种带权的图称为赋权图或网。

5.路径与回路

路径的长度是指路径上经过的弧或边的数目。

在一个路径中，若第一个顶点和最后一个顶点是相同的，则称该路径为回路或环。

若表示路径的顶点序列中的各顶点各不相同，则称这样的路径为简单路径。

除了第一个和最后一个顶点外，其余各顶点均不重复的回路为简单回路

6.连通图

无向图：若从x到y有路径相通，则称顶点x，y是连通的。若无向图中任意两个顶点都是连通的，则称该无向图G为连通图。

有向图：若对于每对顶点有双向路径，则称该有向图为强连通图。

3.图的存储结构

邻接矩阵表示法：也称作数组表示法。用两个数组来表示图，一个用来存储顶点信息的一维数组，一个用来存储图中顶点之间关联关系的二维数组。这个关联关系数组被称为邻接矩阵。

//邻接矩阵表示法
	 #define MAX_VERTEX_NUM 20   //最多顶点个数 
	 #define INFINITY 32768     //表示极大值 
	 
	 typedef enum{DG,DN,UDG,UDN } GraphKind;    //依次为有向图，有向网，无向图，无向网
	 typedef char VertexData;   //顶点数据类型
	 typedef struct ArcNode{
	 	AdjType adj; //对于无权图，0/1表示是否相邻，对带权图，则为权值类型
	 	otherInfo info;
	 }   ArcNode; 
	 typedef struct{
	 	VertexData vertex[ MAX_VERTEX_NUM];   //顶点向量 
	 	ArcNode arcs[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM];//邻接矩阵 
	 	int vexnum,arcnum;//图的顶点数和弧数 
	 	GraphKind kind;//图的种类标志 
	 }  AdjMatrix;
	 

存储空间

无向图：无向图的邻接矩阵是对称矩阵，可以采用特殊矩阵的压缩存储，即只存储其下三角。

? ? ? ? ? ? 需要 n（n-1）/2?个存储空间。

有向图：存储空间需要 n2 个。

对于无向图，其邻接矩阵第i行元素之和就是图中第i个顶点的度

对于有向图，其邻接矩阵第i行元素之和是图中第i个顶点的出度，第i列元素之和是图中第i个顶点的入度

采用邻接矩阵法创建有向图

 int LocateVertex (AdjMatrix * G,VertexData v) //求顶点位置函数
	 {
	 	int j=Error,k;
	 	for(k=0;k<G->vexnum;k++)
	 	if(G->vertex[k]==v)
	 	{
	 		j=k;break;
		 }
		 return (j);
		 }
		 int CreateDN(AdjMatrix *G)
		 {
		 	int i,j,k,weight,VertexData v1,v2;
		 	scanf("%d,%d",&G->arcnum,&G->vexnum);//输入图的顶点和弧数
		 	for(i=0;i<G->vexnum;i++) //初始化邻接矩阵 
			 for(j=0;j<G->vexnum;j++) 
			 G->arcs [i][j].adj=  INFINITY;
			 for(i=0;i<G->vexnum;i++)
			 scanf("%c",&G->vertex[i]);
			 for(k=0;k<G->arcnum;k++)
			 {
			 	scanf("%c,%c,%d",&v1,&G->v2,&weight);//输入一条弧的两个顶点和权值
				  i=LocateVex_M(G,v1);
				  j=LocateVex_M(G,v2);
				  G->arcs[i][j].adj=weight;//建立弧 
				  
			 }
			 return(ok); 
		 }

邻接表表示法

邻接表表示法实际上是图的一种链式存储结构，对于图中存在的边信息则存储，而不相邻接的顶点则不保留信息。一个n个顶点的图的邻接表表示由表头结点表与边表两部分组成。

表头结点表：由所有表头结点以顺序结构的形式存储，以便随机访问任一顶点的边链表。

表头结点有两部分组成：数据域vexdata（存储顶点的名或其他有关信息）---链域firstarc（指向链表中第一个顶?点）

边表：由表示图中顶点间的邻接关系的n个边链表组成。

边链表中结点有三个部分组成：? ? 邻接点域adjvex（存放与顶点相邻接的顶点在图中的位置）----数据域info（存放与边或弧相关的信息）-----链域nextarc（指向与顶点v相关联的下一条边或弧的结点）

? ? ? ? ? ? ? ? ? ?

4.图的遍历? ? ? ? ? ? ?

为了保证图的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，因此要设置一个访问标志数组，用于标记图中每个顶点是否被访问过。初始值为0 ，一旦顶点访问过，则标志数组置为1，表示该?顶点已访问。? ??

深度优先搜素?：类似于根的先根遍历。

基本思想：

1.从图中某个顶点v0出发，首先访问v0

2.找到刚访问过的顶点的第一个未被访问的邻接点，然后访问该顶点。以该顶点为新顶点，重复此步骤，直到刚访问过的顶点没有未被访问的邻接点为止。

3.返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点，然后执行步骤2.

邻接矩阵的深度优先遍历

void DFS(AdjMatrix g,int v0)
{
visit(v0);visited[vo]=True;
for(vj=0;vj<g.vexnum;v++)
if(!visited[vj]&&arcs[v0][vj].adj==1)
DFS(g,vj);
}

邻接表的深度优先遍历

void DFS(AdjList g,int v0)
{
visit(v0); visited[v0]=True;
p=g.vertex[v0].firstarc;
while(p!=NULL)
{
if(!visited[p->adjvex])
DFS(g,p->adjvex);
p=p->nextarc;
}
}

非递归实现深度优先遍历

首先将v0入栈

只要栈不空，则重复下述处理：栈顶顶点出栈，如果未访问，则访问并置访问标志，然后将该顶点所有未访问的邻接点入栈。

void DFS(Graph g,int v0)
{
InitStack(&S);  //初始化空栈
Push(&S,v0);
while(!Is Empty(S))
{
Pop(&S,&v);
if(!visited[v])   //栈中可能有重复顶点
{
visit(v);
visited[v]=True;
w=FirstAdjVertex(g,v);  //求v的第一个邻接点
while(w!=-1)
{
if(!visited[w])
Push(&S,w);
w=NextAdjVertex（g,v,w）; //求v相对于w的下一个邻接点
     }
   }
  }
}