以邻接矩阵作为存储结构实现图的创建与基本操作:
typedef int Status;
typedef int VRType;
typedef char InfoType;
typedef char VertexType;
 
/*①图的邻接矩阵存储结构定义*/
typedef struct ArcCell
{
   //VRType是顶点的关系类型，对无权图用1或0表示是否相邻，对带权图（网）用权值
VRType adj;              
InfoType *info;          //该弧段相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];     //顶点向量
AdjMatrix arcs;                      //邻接矩阵
int vexnum,arcnum;                   //图的顶点数和边（弧）数
GraphKind kind;                      //图的种类标志
}MGraph;




#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE   1
#define FALSE  0
#define OK     1
#define ERROR  0
#define OVERFLOW -2
#define INFINITY       0   //最大值无穷 
#define MAX_VERTEX_NUM 20        //最大顶点数  
typedef int Status;
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_VERTEX_NUM];
typedef enum {DG,DN,UDG,UDN} GraphKind; //{0有向图、1有向网、2无向图、3无向网}

/*①图的邻接矩阵存储结构定义*/
typedef struct ArcCell
{
	VRType adj;              //VRType是顶点的关系类型，对无权图用1或0表示是否相邻，对带权图（网）用权值
	InfoType *info;          //该弧段相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
	VertexType vexs[MAX_VERTEX_NUM];     //顶点向量
	AdjMatrix arcs;                      //邻接矩阵
	int vexnum,arcnum;                   //图的顶点数和边（弧）数
	GraphKind kind;                      //图的种类标志
}MGraph;

//构造有向图
Status CreateDG(MGraph &G);
//构造有向网
Status CreateDN(MGraph &G);
//构造无向图
Status CreateUDG(MGraph &G);
//构造无向网
Status CreateUDN(MGraph &G);
//1-创建图
Status CreateGraph(MGraph &G);
//2-销毁图
Status DestroyGraph(MGraph &G);
//3-获取顶点位置
Status LocateVex(MGraph G, VertexType u);


//构造有向图
Status CreateDG(MGraph &G)
{
	int i,j,k,IncInfo,w;   
    VertexType v1,v2;  
    printf("请输入有向图G的顶点数，边数，边是否含有其他信息(是:1,否:0):\n"); 
    scanf("%d%d%d",&G.vexnum ,&G.arcnum,&IncInfo);  
    printf("请输入顶点的值:\n"); 
    for(i=0;i<G.vexnum;++i)//构造顶点向量  
        scanf("%s",G.vexs[i]);  
    for(i=0;i<G.vexnum;++i)//初始化邻接矩阵  
        for(j=0;j<G.vexnum;++j)  
        {  
            G.arcs[i][j].adj=INFINITY;  
            G.arcs[i][j].info=NULL;  
        }    
        for(k=0;k<G.arcnum;++k)  
        {  
            scanf("%s%s%d",&v1,&v2,&w); 
            i=LocateVex(G,v1);  //弧尾
            j=LocateVex(G,v2);  //弧头
            G.arcs[i][j].adj=w; 
            if(IncInfo)  
            {     printf("请输入该边的相关信息:");  
                  gets(G.arcs[i][j].info);
            } 
        }  
        G.kind=DG;  
        return OK;  
}

//构造有向网
Status CreateDN(MGraph &G)
{
	int i,j,k,w,IncInfo;  
    VertexType v1,v2;  
    printf("请输入有向网G的顶点数，边数，边是否含有其他信息(是:1,否:0):\n"); 
    scanf("%d%d%d",&G.vexnum ,&G.arcnum,&IncInfo);  
    for(i=0;i<G.vexnum;++i)//构造顶点向量  
        scanf("%s",G.vexs[i]);  
    for(i=0;i<G.vexnum;++i)//初始化邻接矩阵  
        for(j=0;j<G.vexnum;++j)  
        {  
            G.arcs[i][j].adj=INFINITY; 
            G.arcs[i][j].info=NULL;  
        }  
        printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔):\n",G.arcnum);  
        for(k=0;k<G.arcnum;++k)  
        {  
            scanf("%s%s%d%",&v1,&v2,&w);
            i=LocateVex(G,v1);  
            j=LocateVex(G,v2);  
            G.arcs[i][j].adj=w;//有向网  
            if(IncInfo)  
            {    printf("请输入该边的相关信息:");  
                 gets(G.arcs[i][j].info);
            }  
        }  
        G.kind=DN;  
        return OK;  
}

//构造无向图
Status CreateUDG(MGraph &G)
{
	int i,j,k,IncInfo,w;   
    VertexType v1,v2;  
    printf("请输入无向图G的顶点数，边数，边是否含有其他信息(是:1,否:0):\n");  
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);  
    printf("请输入顶点的值:\n");  
    for(i=0;i<G.vexnum;i++)//构造顶点向量  
        scanf("%s",G.vexs[i]);  
    for(i=0;i<G.vexnum;++i)//初始化邻接矩阵  
        for(j=0;j<G.vexnum;++j)  
        {  
            G.arcs[i][j].adj=INFINITY;  
            G.arcs[i][j].info=NULL;  
        }   
        for(k=0;k<G.arcnum;++k)  
        {  
            scanf("%s%s%d",&v1,&v2,&w);
            i=LocateVex(G,v1);  
            j=LocateVex(G,v2);  
            G.arcs[i][j].adj=w;//无向图  
            if(IncInfo)  
            {     printf("请输入该边的相关信息:");  
                  gets(G.arcs[i][j].info);
            } 
			G.arcs[j][i]=G.arcs[i][j];
        }  
        G.kind=UDG;  
        return OK;  
}

//构造无向网
Status CreateUDN(MGraph &G)
{
    int i,j,k,IncInfo,w;   
    VertexType v1,v2;  
    printf("请输入无向网G的顶点数，边数，边是否含有其他信息(是:1,否:0):\n"); 
    scanf("%d%d%d",&G.vexnum ,&G.arcnum,&IncInfo);  
    printf("请输入顶点的值:\n"); 
	for(i=0;i<G.vexnum;++i)
		scanf("%s",&G.vexs);
	for(i=0;i<G.vexnum;++i)
		for(j=0;j<G.vexnum;++j)
		{	
			G.arcs[i][j].adj=INFINITY; 
		    G.arcs[i][j].info=NULL;  
		}
		for(k=0;k<G.arcnum;++k)
		{
			scanf("%s%s%d",&v1,&v2,&w);
			i=LocateVex(G,v1);
			j=LocateVex(G,v2);
			G.arcs[i][j].adj =w;
		    if(IncInfo)  
            {     printf("请输入该边的相关信息:");  
                  gets(G.arcs[i][j].info);
            } 
			G.arcs[j][i]=G.arcs[i][j];
		}
	G.kind=UDN;
	return OK;
}//CreateUDN

//1-创建图
Status CreateGraph(MGraph &G)
{
	printf("***********图的创建与实现**************\n");
	printf("1.有向图\n2.有向网\n3.无向图\n4.无向网\n请选择需要创建的图的类型：");
	scanf("%d",&G.kind);
	switch (G.kind-1){
	case DG:return CreateDG(G);
    case DN:return CreateDN(G);
	case UDG:return CreateUDG(G);
	case UDN:return CreateUDN(G);
	default:return ERROR;
	}
}//CreateGraph

//2-销毁图
Status DestroyGraph(MGraph &G)
{
	int i,j;
	if(G.kind<2)//有向
	{	
		for(i=0;i<G.vexnum;i++)//释放相关信息（如果有）
			for(j=0;j<G.vexnum;j++)
				if(G.arcs[i][j].adj==1&&G.kind==0||G.arcs[i][j].adj!=INFINITY&&G.kind==1)//有向图的弧||有向网的弧
					if(G.arcs[i][j].info)//有相关信息
					{
						free(G.arcs[i][j].info);
						G.arcs[i][j].info=NULL;
					}
		}
	else//无向
	{
		for(i=0;i<G.vexnum;i++)//释放相关信息（如果有）
			for(j=i+1;j<G.vexnum;j++)
				if(G.arcs[i][j].adj==1&&G.kind||G.arcs[i][j].adj!=INFINITY&&G.kind==3)//无向图的边||无向网的边
					if(G.arcs[i][j].info)//有相关信息
					{
						free(G.arcs[i][j].info);
						G.arcs[i][j].info=G.arcs[j][i].info=NULL;
					}
	}
	G.vexnum=0;
	G.arcnum=0;
	printf("图销毁成功!");
	printf("\n\n");
	return OK;
}

//3-获取顶点位置
Status LocateVex(MGraph G, VertexType u)
{
	int i;
	for(i=0;i<G.vexnum;++i)
		if(strcmp(u,G.vexs[i])==0)
			return i;
	return FALSE;
}


void main()
{
	MGraph G;
    CreateGraph(G);
}



未完待更新。。。。。。

因为图的结构特点，使得其在存储、遍历也相对复杂一些。
邻接矩阵存储图
最简单的方式就是将图的顶点用一维数组存储进来，然后将边信息存储在二维矩阵中，这两个数组合称为图的邻接矩阵（Adjacency Matrix）。
邻接表存储图
看上图邻接矩阵的结构，可以得知邻接矩阵中的边数组中存在大量为零的空占位，浪费了大量空间，所以就自然而然想到利用链表来进行边的存储，这就是邻接表（Adjacency List）。
有向图邻接表的边表为以弧尾为链表表头进行存储的，这样对于顶点的出度统计较为方便，而有向图逆邻接表则正好与邻接表相反，边表是以弧尾作为链表表头的。
邻接多重表存储无向图
假如对无向图的邻接表进行删除某边操作时需要对相关结点进行遍历找到相应边然后进行删除，比较麻烦，故邻接多重表对其进行改良。
边表结构：
其中，ivex和jvex为某边依附的两顶点在顶点表中的下标，ilink指向依附顶点ivex的下一条边，同理jlink指向依附顶点jvex的下一条边。
十字链表存储有向图
用邻接表存储有向图存在一个问题，对于某一顶点的弧统计还是很麻烦的，邻接表对于顶点作为弧头的弧统计很麻烦，逆邻接表对于顶点作为弧尾的弧统计很麻烦。所以为了对顶点更好的查询，便参考线索二叉树的设计思路，得到了十字链表（Orthogonal List）。
顶点表的结构为：
边表结构为：
其中，tailvex为弧尾在顶点表中的下标，headvex为弧头在顶点表中的下标，headlink指的是入边表指针域，指的是弧头相同的下一条边，taillink指的是出边表指针域，指的是弧尾相同的下一边。
图中实线为邻接表，虚线为逆邻接表。
边集数组存储图
注意和邻接矩阵进行区别。

	

目录
一、图的定义和基本术语(Graph)
(一)图的定义
(二)图的基本术语
一、图的存储结构
(一)邻接矩阵(Adjacency Matrix)
1、无向图的邻接矩阵
2、有向图的邻接矩阵
3、网(即有权图)的邻接矩阵
4、邻接矩阵的存储表示
5、采用邻接矩阵表示法创建无向网
(二)邻接表(链式)表示法(Adjacency List)
1、无向图的邻接表表示
2、有向图的邻接表表示
3、图的邻接表的存储定义
4、采用邻接表表示法创建无向图
5、邻接矩阵与邻接表的比较
(三)十字链表(Orthogonal List)
1、弧结点的结构
2、顶点结点的结构
3、图的结构定义
4、实例
5、有向图G的十字链表
(四)邻接多重表(Adjacent MultiList)
1、边结点的结构
2、顶点结点的结构
3、图的结构定义
4、实例
4、练习：画出无向图G的邻接多重表
一、图的定义和基本术语(Graph)
(一)图的定义
图(Graph)是由一个顶点集V和一个边集E构成的数据结构。
G=(V,E)
V:顶点(数据元素)的又穷非空集合
E:边的又穷集合无向图：每条边都是没有方向的
有向图：每条边都是有方向的，边也称作弧
(二)图的基本术语
设n表示图中顶点的数目，e表示边的数目完全图：任意两个点都有一条边相连稀疏图：如果边或者弧的个数满足e
对无向图来说：邻接点：若顶点v和顶点w之间存在一条边a,则称顶点v和w互为邻接点。边a与顶点v和w相关联。
度：与顶点v关联的边的数目，记为TD(v)
对有向图来说：1、为有向边(弧)，x为有向边的起点(弧尾)，y为有向边的终点(弧头)
2、顶点v的入度是以v为终点的有向边的条数，记作ID(v)
3、顶点v的出度是以v为始点的有向边的条数，记作OD(v)
路径：连续的边构成的顶点序列路径长度：路径上边或者弧的数目简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。
一、图的存储结构
图的存储表示特点：
1、图没有顺序存储结构，但可以借助二维数组来表示图的元素之间的关系
2、以顶点为核心，建立邻接点和弧的关系；
(一)邻接矩阵(Adjacency Matrix)
1、考虑到图是由两个顶点和边或弧两部分组成，合在一起比较困难，可以分为两个结构来存储
2、顶点因为不区分大小，主次，所以可以用一个一维数组来存储，记录各个顶点的信息
3、边或弧是顶点和顶点的关系，用邻接矩阵来存储，表示各个顶点之间的邻接关系。
1、无向图的邻接矩阵
2、有向图的邻接矩阵
3、网(即有权图)的邻接矩阵
4、邻接矩阵的存储表示
/*图的邻接矩阵存储表示法*///用两个数组分别存储顶点表和邻接矩阵#define MaxInt 32767  //表示极大值，即无穷#define MVNum 100  //最大顶点数typedef char VerTexType;  //假设顶点的数据类型为字符型typedef int ArcType;  //假设边的权值类型为整型typedef struct{  VerTexType vexs[MVNum];  //顶点表  ArcType arcs[MVNum][MVNum];  //邻接矩阵  int vexnum, arcnum;  //图的当前顶点数和边数}AMGraph;
5、采用邻接矩阵表示法创建无向网
【算法步骤】
1、输入总顶点数和边数
2、依次输入点的信息存入到顶点表中
3、初始化邻接矩阵，使每个权值初始化为极大值
4、构造邻接矩阵
注意：
1、无向图需要为arcs[i][j]和arcs[j][i]赋值
2、有向图仅需为arcs[i][j]赋值
算法描述：
/*采用邻接矩阵表示法创建无向网*/Status CreateUDN(AMGraph& G){  cin >> G.vexnum >> G.arcnum;//输入总顶点数和总边数  for (int i = 0;i < G.vexnum;++i)    cin >> G.vexs[i];//依次输入顶点的信息  for (int i = 0;i < G.vexnum;++i)//初始化邻接矩阵，边的权值均置为极大值    for (int j = 0;j < G.vexnum;++j)      G.arcs[i][j] = MaxInt;  for (int k = 0;k < G.arcnum;++k)  {    cin >> v1 >> v2 >> w;//输入一条边依附的顶点和权值    i = LocateVex(G, v1);j = LocateVex(G, v2);//确定两个顶点v1和v2在G中的位置    G.arcs[i][j] = w;//边的权值置为w    G.arcs[j][i] = G.arcs[i][j];//置边的对称点的权值也为w  }  return OK;}/*在图中查找顶点的位置LocateVex()函数*/int LocateVex(AMGraph G, VertexType u){//若在图中找到这个元素，则返回它的下标i,否则返回-1  int i;  for (i = 0;i < G.vexnum;++i)    if (u == G.vexs[i])      return i;  return -1;}
(二)邻接表(链式)表示法(Adjacency List)
是图的链式存储结构，基本思想就是只存储图中存在的边的信息，对不相邻的顶点则不保留信息
对图中每个顶点vi建立一个带头结点的单链表，把与vi相邻接的顶点放在这个链表中，一个单链表对应邻接矩阵中的一行，称为边链表。
1、无向图的邻接表表示
2、有向图的邻接表表示
3、图的邻接表的存储定义
分三部分：
1、图的结构定义
2、顶点的头结点结构
3、弧(边)的结点结构
/*图的邻接表的存储定义*///弧的结点结构#define MVNum 100  //最大的顶点数typedef struct ArcNode{  int adjvex;  //该边所指的顶点的位置  struct ArcNode* nextarc;  //指向下一条边的指针  OtherInfo info;  //和边相关的信息}ArcNode;//顶点的结点结构typedef struct VNode{  VertexType data;//顶点信息  ArcNode* firstarc;//指向第一条依附该顶点的边}VNode,AdjList[MVNum];//AdjList表示邻接表类型//AdjList v相当于VNode v[MVNum]//图的结构定义(邻接表)typedef struct{  AdjList vertices;//vertices是vertex的复数  int vexnum, arcnum;//图的当前顶点数和边数}ALGraph;/*说明*/ALGraph G;//定义了邻接表表示的图GG.vexnum = 5;G.arcnum = 6;//图G包含了5个顶点和6条边G.vertices[1].data = 'v2';//图G中第2个顶点是v2p = G.vertices[1].firstarc;//指针p指向顶点v2的第一个边结点p->adjvex = 4;//p指针所指边结点是到下标为4的结点的边
4、采用邻接表表示法创建无向图
【算法步骤】
1、输入总顶点数和总边数
2、建立顶点表
1、依次输入点的信息存入顶点表中
2、使每个表头结点的指针域初始化为NULL
3、创建邻接表
1、依次输入每条边依附的两个顶点
2、确定这两个顶点的序号i和j
3、将此边结点分别插入vi和vj对应的两个边链表的头部
/*采用邻接表表示法创建无向图*/Status CreateUDG(ALGraph& G){//采用邻接表表示法，创建无向图G  cin >> G.vexnum >> G.arcnum;//输入顶点数和弧数  for (int i = 0;i < G.vexnum;++i)  {    cin >> G.vertices[i].data;//输入顶点值    G.vertices[i].firstarc = NULL;//初始化表头结点的指针域为NULL  }  for (int k = 0;k < G.arcnum;++k)//输入各边，构造邻接表，头插法  {    cin >> v1 >> v2;//输入一条边依附的两个顶点    i = LocateVex(G, v1);j = LocateVex(G.v2);    p1 = new ArcNode;//生成一个新的边结点*p1    p1->adjvex = j;//邻结点序号为j    p1->nextarc = G.vertices[i].firstarc;//firstarc为空，所以nextarc也指向空，即最后的一个结点    G.vertices[i].firstarc = p1;//将新结点*p1插入到顶点vi的边表头部    p2 = new ArcNode;//生成一个新的边结点*p2    p2->adjvex = i;    p2->nextarc = G.vertices[j].firstarc;//插入弧结点到单链表    G.vertices[j].firstarc = p2;//将新结点*p2插入到顶点vi的边表头部  }//头插法    return OK;}
5、邻接矩阵与邻接表的比较
练习：画出有向图G的邻接矩阵、邻接表、逆邻接表
(三)十字链表(Orthogonal List)
十字链表是有向图的另一种链式存储结构，可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表
1、弧结点的结构
Tailvex:指示弧尾结点在图中的位置
headtex:指示弧头顶点在图中的位置
hlink:是指向弧头相同的下一条弧的指针
tlink：是指向弧尾相同的下一条弧的指针
Info:指向该弧的相关信息
/*弧结点的结构*/typedef struct ArcBox{  int tailvex, headvex;//该弧的尾和头顶点的位置  struct ArcBox* hlink, * tlink;//分别为弧头相同和弧尾相同的弧的指针域  InfoType* info;//该弧相关信息的指针}ArcBox;
2、顶点结点的结构
每个顶点有一个结点，它相当于出边表和入边表的表头结点。数据成员data存放与该顶点的相关信息。链域firstin指示以该顶点为弧头的第一个弧结点。链域firstout指示以该结点为弧尾的第一个弧结点。
/*顶点结点的结构*/typedef struct VexNode{  VertexType data;  ArcBox* firstin, * firstout;//分别指向该顶点第一条入弧和出弧}VexNode;//ArcBox为弧结点变量
3、图的结构定义
/*图的结构定义*/typedef struct{  VexNode xlist[MAX_VERTEX_NUM];//表头向量  int vexnum, arcnum;//有向图的当前顶点数和弧数}OLGraph;
4、实例
5、有向图G的十字链表
(四)邻接多重表(Adjacent MultiList)
邻接多重表是无向图的另一种链式存储结构，由于用邻接表存储无向图时，虽然容易求出顶点和边的各种信息，但在邻接表中每一条边有两个结点，分别在第i和j个链表中，给图的某些操作带来不便，在邻接多重表中，每一条边只有一个边结点，为有关的处理提供了方便。
1、边结点的结构
mark：为标志域，可用以标记该条边是否被搜索过
ivex和jvex为该边依附的两个顶点在图中的位置
ilink:指向下一条依附于顶点的ivex的边
jlink:指向下一条依附于顶点jvex的边
info:为指向和边相关的各种信息个指针域
/*边结点结构*/typedef struct EBox{  VisitIf mark;//访问标志域  int ivex, jvex;//该边依附的两个顶点在表头数组中的位置  struct Ebox* ilink, * jlink;//分别指向依附于ivex和jvex的下一条边  InfoType* info;}EBox;
2、顶点结点的结构
/*顶点结点的结构*/typedef struct VexBox{  VertexType data;//存与顶点相关的信息  EBox* firstedge;//指向第一条依附于该顶点的边}VexBox;
3、图的结构定义
/*图的结构定义*/typedef struct{  VexBox adjmulist[MAX_VERTEX_NUM];//表头向量  int vexnum, edgenum;//无向图的当前顶点数和弧数}OLGraph;//VexNode为顶点结点变量
4、实例
4、练习：画出无向图G的邻接多重表

线性存储元素时，元素的关系也同时确定了。而非线性数据结构就不同了，需要同时考虑存储数据元素和数据元素的逻辑关系。例如，图这种数据结构的矩阵存储就是用一个顶点向量存储顶点元素，再用一个邻接矩阵存储元素关系。
由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序存储结构，但可以借助二维表来表示元素之间的关系，一般称为邻接矩阵。另一方面，由于图的任意两个顶点间都可能存在关系，因此，用链式存储表示图结构是很自然的事，其中有代表性的一种链式存储称为邻接表。
在图的邻接矩阵表示法中，用邻接矩阵表示顶点间的相邻关系，而用一个顺序表来存储顶点信息。
图的邻接矩阵表示法适用范围广泛，可以用来描述有向图、有向表、无向图、无向表。
邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
则上图的邻接矩阵可以表示为：
若是带权图(网)，则G的邻接矩阵是具有如下性质的n阶方阵：
其邻接矩阵可以表示为：
邻接矩阵表示法表示图一般可抽象如下：
#define MaxInt 32767 // 表示极大值，即∞#define MVNum 100 // 最大顶点数typedef char VerTexType; // 假设顶点的数据类型为字符型typedef int ArcType; // 假设边的权值类型为整型typedef struct{    VerTexType vexs[MVNum]; // 顶点表    ArcType arcsMVNum][MVNum]; // 邻接矩阵    int vexnum,arcnum; // 图的当前顶点数和边数}AMGraph;
图遍历背后的关键思想是在我们第一次访问每个顶点时对其进行标记，并跟踪我们尚未完全探索的内容。尽管面包屑或解开的线被用来标记童话迷宫中参观过的地方，但我们将依赖布尔标志或枚举类型来进行。
每个顶点将以三种状态之一存在：
未发现-顶点处于原始状态。
已发现-顶点已找到，但尚未检查其所有入射边。
已处理–访问所有关联边后的顶点。
显然，一个顶点只有在我们发现它之后才能被处理，所以每个顶点的状态在遍历过程中从未发现到发现再到处理。
我们还必须维护一个包含我们已经发现但尚未完全处理的顶点的结构。最初，只有一个起始顶点被认为是被发现的。为了完全探索一个顶点v，我们必须计算每一条离开v的边。如果一条边转到一个未发现的顶点x，我们标记x 为“已发现”并将其添加到要做的工作列表中。我们要忽略处理过的顶点的边，因为进一步的探索不会告诉我们关于图的任何新的东西。我们还可以忽略到已发现但未处理的顶点的任何边，因为目标已位于要处理的顶点列表中。
BFS(Depth First Search--DFS)和DFS(Breadth First Search--BFS)结果的区别在于它们探索顶点的顺序。此顺序完全取决于用于存储已发现但未处理的顶点的容器数据结构。
Stack–通过将顶点存储在后进先出(last-in，first-out，LIFO)堆栈中，我们通过沿着路径一直前行、访问新邻居(如果有的话)和仅当我们被以前发现的顶点包围时才回退来探索新的顶点。因此，我们的探索很快偏离了起点，定义了深度优先搜索。
一旦发现一个顶点，它就被放置在栈(显式或隐式栈)中。由于我们按后入先出的顺序处理这些顶点，所以最新的顶点将首先展开，这些顶点正是最远离根的顶点。
队列-通过将顶点存储在先进先出(FIFO)队列中，我们首先探索最古老的未探索顶点。因此，我们的探索从起始顶点缓慢地向外辐射，定义了广度优先搜索。
一旦发现一个顶点，它就被放置在队列中。由于我们按先入先出的顺序处理这些顶点，所以最旧的顶点将首先展开，这些顶点正是最接近根的顶点。
深度优先搜索有一个简洁的递归实现，它消除了显式使用堆栈的需要。
我们需要能够对每个入口和出口分别采取行动。
深度优先搜索的另一个重要特性是它将无向图的边划分为两类：tree edges和back edges。tree edges发现新的顶点，并且是在parent关系中编码的顶点。back edges是那些其另一个端点是被展开顶点的ancestor的边，因此它们指向树中。
1 深度优先遍历(先孩子后上一辈的兄弟)
优先向深度探索，一直走到头才回头到路径的上一个相邻顶点，直到回溯到最开始顶点。
如上图的深度优先遍历的顺序：0 1 2 3 4 5 6 8 9 7
如果使用递归，则相当于使用了一个隐式的栈数据结构(编译器对函数递归调用的压栈和回归的出栈操作)。
如果使用抱定代，则需要显式使用一个栈数据结构。
2 广度优先遍历(先兄弟后孩子)
广度优先遍历，也就是从某一个顶点开始，优先访问全部的相邻顶点，按层次辐射，直到全部顶点访问完。
如上图使用广度优先遍历的顺序：0 1 3 2 4 5 6 7 8 9
广度优先遍历需显式使用一个队列的数据结构。广度优先搜索是一种分层的搜索过程，不像深度优先遍历那样有往回退的情况。因此，广度优先遍历不能递归实现，可以使用先进先出的队列来实现。
深度搜索与广度搜索的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。也就是说，广度优先搜索会优先考虑最早被发现的顶点，也就是说离起点越近的顶点优先级越高。深度优先搜索会优先考虑最后被发现的顶点。
在20世纪50年代，广度优先搜索最早由Edward F. Moor在研究迷宫路径问题时发现，深度优先搜索在人工智能方面获得了广泛应用。
#include #include typedef int VertexType;       // 顶点类型应由用户定义typedef int EdgeType;         // 边上的权值类型应由用户定义#define MAXSIZE  15           // 存储空间初始分配量#define MAXEDGE  15#define MAXVEX   10#define INFINITY 65535/* 0-----1  |    /|  |   2 | |  / | | /   4    5---8 |/        /  /  3        7   6--9   */int arc[MAXVEX][MAXVEX]={  // 布尔数组{0,1,0,1,0,0,0,0,0,0},{1,0,1,0,1,0,0,0,0,0},{0,1,0,1,1,0,0,0,0,0},{1,0,1,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,1,1,0},{0,0,0,0,0,1,0,0,1,1},{0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,1,1,0,0,0},{0,0,0,0,0,0,1,0,0,0}};// 0的元素数目远远多于非0元素的数目，称为稀疏矩阵，用链式存储较节省空间typedef struct{    VertexType vexs[MAXVEX];         // 顶点表    EdgeType arc[MAXVEX][MAXVEX];    // 邻接矩阵，可看作边表    int numVertexes, numEdges;       // 图中当前的顶点数和边数 }MGraph;typedef struct             // 循环队列顺序存储结构{    int data[MAXSIZE];    int front;             // 头指针    int rear;              // 尾指针，若队列不空，指向队列尾元素的下一个位置}Queue;void CreateMGraph(MGraph *G){    int i,j;    G->numEdges=15;    G->numVertexes=10;for(i=0; inumVertexes; i++)        // 建立顶点表G->vexs[i] = i;    for (i = 0; i < G->numVertexes; i++)   // 初始化图    {        for (int j = 0; j < G->numVertexes; j++)        {            G->arc[i][j]=arc[i][j];        }    }} bool visited[MAXVEX];         // 访问标志的数组void DFS(MGraph G, int i)     // 邻接矩阵的深度优先递归算法{    visited[i] = true;    printf("%d ", G.vexs[i]); // 打印顶点，也可以其它操作    for(int j=0; jfront=0;    Q->rear=0;    return  true;}bool QueueEmpty(Queue Q){     if(Q.front==Q.rear)    // 队列空的标志        return true;    else        return false;}bool EnQueue(Queue *Q,int e){    if ((Q->rear+1)%MAXSIZE == Q->front)   // 队列满的判断        return false;    Q->data[Q->rear]=e;                    // 将元素e赋值给队尾    Q->rear=(Q->rear+1)%MAXSIZE;           // rear指针向后移一位置，                                           // 若到最后则转到数组头部    return  true;}bool DeQueue(Queue *Q,int *e)           // 删除Q中队头元素，用e返回其值{    if (Q->front == Q->rear)            // 队列空的判断        return false;    *e=Q->data[Q->front];               // 将队头元素赋值给e    Q->front=(Q->front+1)%MAXSIZE;      // front指针向后移一位置，                                        // 若到最后则转到数组头部    return  true;}
无论那种搜索，都是通过对一个线性表进行处理，只不过是先处理头部还是尾部的问题罢了。处理头部优先的时候，也就是先加入的先探索，就是广度优先了，因为，头部的都是兄弟节点；而尾部的则是深度优先，因为放入尾部的都是刚刚生产出来的节点，后加入的先探索——也就是所谓一条路走到死。 同理可以联想到启发式搜索。启发式搜索就是先以你自定义的优先级处理，然后再以广度为优先级处理。 所以，归根结底，所谓的搜索，就是一种定义了优先级的枚举。
－End－