图的表示及优先遍历

图的存储结构
1.邻接矩阵(无向图,有向图)
该结构实际上就是用一个二维数组（邻接矩阵）来存储
顶点的信息和顶点之间的关系（有向图的弧或无向图的边）
描述形式:
#define MAX_NUM 10
enum GraphKind{GY,GN};//{有向图,无向图}
typedef struct
{
VRType adj;// 顶点关系类型。对无权图，用1(是)或0(否)表示是否相邻；对带权图，则为权值
InfoType *info; // 与该弧或边相关信息的指针(可无)
}ArcCell,AdjMatrix[MAX_NUM][MAX_NUM];

typedef struct
{
VertexType vexs[MAX_NUM];// 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum ,arcnum;// 图的当前顶点数和弧（边）数
GraphKind kind;// 图的种类标志
}Glaph;
邻接矩阵所占用的存储空间与图的边数或弧数无关，
因此适用于边数或弧数较多的稠密图。
2.邻接表(无向图,有向图)
在邻接表中，用一个一维数组存储图中的每个顶点的信息，
同时为每个顶点建立一个单链表，
链表中的节点保存依附在该顶点上的边或弧的信息。
描述形式;
#define MAX_NUM 10// 最大顶点个数
enum GraphKind{GY,GN};// {有向图,无向图}
typedef struct{
int adjvex;// 该弧所指向的顶点或边的另一个顶点的位置
ArcNode *nextarc;// 指向下一条弧或边的指针
InfoType *info;// 与弧或边相关信息的指针（可无
}ArcNode;// 表结点

typedef struct
{
VertexType data;// 顶点信息
ArcNode *firstarc;// 第一个表结点的地址,指向第一条依附该顶点的弧或边的指针

}VNode,AdjList[MAX_NUM]; // 头结点
struct
{
AdjList vertices;
int vexnum,arcnum;// 图的当前顶点数和弧（边）数
GraphKind kind; // 图的种类标志
}Graph;
邻接表所占用的存储空间与图的边数或弧数有关，
因此适用于边数或弧数较少的稀疏图

3.十字链表
十字链表也是一种链式存储结构，用来表示有向图，
它在有向图邻接表的基础上加入了指向弧尾的指针

#define MAX_NUM 10
typedef struct// 弧结点
{
int tailvex,headvex; // 该弧的尾和头顶点的位置
ArcBox *hlink,*tlink;// 该弧相关信息的指针，可指向权值或其他信息（可无
InfoType *info;
}ArcBox;
typedef struct// 顶点结点
{
VertexType data;
ArcBox *firstin,*firstout; // 分别指向该顶点第一条入弧和出弧

}VexNode;
struct
{
VexNode xlist[MAX_NUM]; // 表头向量(数组
int vexnum,arcnum;// 有向图的当前顶点数和弧
}Graph;

4.邻接多重表
邻接多重表也是一种链式存储结构，
用来表示无向图，与有向图的十字链表相似

描述形式:
#define MAX_NUM 10
typedef struct
{
visitIf mark;// 访问标记
int ivex,jvex;// 该边依附的两个顶点的位置
EBox *ilink,*jlink;// 分别指向依附这两个顶点的下一条边
InfoType *info; // 该边信息指针，可指向权值或其他信息

}EBox;
typedef struct
{
VertexType data;
EBox *firstedge;// 指向第一条依附该顶点的边
}VexBox;
typedef struct
{
VexBox adjmulist[MAX_NUM];
int vexnum,edgenum;
// 无向图的当前顶点数和边数
}Graph;
6.图的遍历
设置一个辅助数组visited[]来标记某个节点是否已经被访问过。
图的遍历通常有两种方法：深度优先遍历（BFS）和广度优先遍历（DFS）
#define MAX_NUM 10
/*
用邻接表作为图的存储结构
在邻接表中，用一个一维数组存储图中的每个顶点的信息，
同时为每个顶点建立一个单链表，链表中的节点保存依附在该顶点上的边或弧的信息
*/
typedef struct node
{ //链表中的每个节点，保存依附在该节点上的边或弧的信息
int vertex;//在有向图中表示该弧所指向的顶点（即弧头）的位置，
//在无向图中表示依附在该边上的另一个顶点的位置
struct node *pNext;//指向下一条依附在该顶点上的弧或边
}Node;
typedef struct
{//数组中的每个元素，保存图中每个顶点的相关信息
char data;//顶点的数据域

Node *firet;//在有向图中，指向以该顶点为弧尾的第一条弧
//在无向图中，指向依附在该顶点上的第一条边
}Head,*Graph; //动态分配数组保存每个顶点的相关信息
7. 深度优先搜索
深度优先搜索（DFS）类似于树的先序遍历
其基本思想是：从图中某个顶点v出发，遍历该顶点，
而后依次从v的未被访问的邻接点出发深度优先遍历图中，
直到图中所有与v连通的顶点都已被遍历。
如果当前图只是需要遍历的非连通图的一个极大连通子图，
则另选其他子图中的一个顶点，重复上述遍历过程，
直到该非连通图中的所有顶点都被遍历完。
很明显，这里要用到递归的思想
深度优先搜索的代码
/*
从序号为begin的顶点出发，递归深度优先遍历连通图Gp
*/
void DFS(Graph Gp,int begin)
{
//遍历输出序号为begin的顶点的数据域，并保存遍历信息
printf("%c",Gp[begin].data);
visited[begin]=true;

//循环访问当前节点的所有邻接点（即该节点对应的链表）
int i;
for(i=first_vertex(Gp,begin);i>=0;i=next_vertex(Gp,begin,i))
{
if(!visited[i])
DFS(Gp,i); //对于尚未遍历的邻接节点，递归调用DFS
}
}
/*
从序号为begin的节点开始深度优先遍历图Gp，Gp可以是连通图也可以是非连通图
*/
void DFS_traverse(Graph Gp,int begin)
{
int i;
for(i=0;i<MAX_NUM;i++)//初始化遍历标志数组
visited[i]=false;


//先从序号为begin的顶点开始遍历对应的连通图
DFS(Gp,begin);
//如果是非连通图，该循环保证每个极大连通子图中的顶点都能被遍历到
for(i=0;i<MAX_NUM;i++){
if(!visited[i])
DFS(Gp,i);
}
}
/*
返回图Gp中pos顶点（序号为pos的顶点）的第一个邻接顶点的序号，如果不存在，则返回-1
*/
int first_vertex(Graph Gp,int pos)
{
if(Gp[pos].first)
return Gp[pos].first->vertex;
else
return -1;
}
/*
cur顶点是pos顶点（cur和pos均为顶点的序号）的其中一个邻接顶点，
返回图Gp中，pos顶点的（相对于cur顶点）下一个邻接顶点的序号,如果不存在，则返回-1
*/

int next_vertex(Graph Gp,int pos,int cur)
{
Node *p=Gp[pos].first;//p初始指向顶点的第一个邻接点
//循环pos节点对应的链表，直到p指向序号为cur的邻接点
while(p->vertex!=cur)
p=p->pNext;
//返回下一个节点的序号
if(p->pNext)
return p->pNext->vertex;

else
return -1;
}

8.广度优先搜索
广度优先搜索（BFS）类似于树的层序遍历.其基本思想是：
从头图中某个顶点v出发，访问v之后，
依次访问v的各个未被访问的邻接点，
而后再分别从这些邻接点出发，依次访问它们的邻接点，
直到图中所有与v连通的顶点都已被访问。
如果当前图只是需要遍历的非连通图的一个极大连通子图，
则另选其他子图中的一个顶点，重复上述遍历过程，
直到该非连通图中的所有顶点都被遍历完。
很明显，跟树的层序遍历一样，图的广度优先搜索要用到队列来辅助实现

/*
从序号为begin的顶点开始，广度优先遍历图Gp，Gp可以是连通图也可以是非连通图
*/
void BFS_traverse(Graph Gp,int begin)
{
int i;
for(i=0;i<MAX_NUM;i++) //初始化遍历标志数组
visited[i]=false;
//先从序号为begin的顶点开始遍历对应的连通图
BFS(Gp,begin);
//如果是非连通图，该循环保证每个极大连通子图中的顶点都能被遍历到
for(i=0;i<MAX_NUM;i++)
{
if(!visited[i])
BFS(Gp,i);
}
}

/*
从序号为begin的顶点开始，广度优先遍历连通图Gp
*/
void BFS(Graph Gp,int begin)
{
//遍历输出序号为begin的顶点的数据域，并保存遍历信息
printf("%c",Gp[begin].data);
visited[begin]=true;

int i;
int pVertex; //用来保存从队列中出队的顶点的序号
PQUEUE queue=create_queue(); //创建一个空的辅助队列
en_queue(queue,begin);//首先将序号为begin的顶点入队

while(!is_empty(queue))
{
de_queue(queue,&pVertex);
//循环遍历，访问完pVertex顶点的所有邻接顶点,并将访问后的邻接顶点入队
for(i=first_vertex(Gp,pVertex);i>=0;i=next_vertex(Gp,pVertex,i))
{
if(!visited[i])
{
printf("%c",Gp[i].data);
visited[i]=true;

en_queue(queue,i);
}
}
}
//销毁队列，释放其对应的内存
destroy_queue(queue);
}