图的遍历算法详解

         图是一种比较重要的数据结构，无论多复杂的图都是由顶点和边构成的，图有两种常用的存储结构为邻接矩阵和邻接表。本篇博客将使用邻接表存储图，邻接表是一种顺序分配和链式分配相结合的存储方式。邻接表是表示图的标准方法，尤其对于稀疏图节省很多存储空间，空间复杂度是O(|E|+|V|). 对于每个顶点，使用一个表存放所有邻接的顶点。

        我们要操作的有向图如下：

通过图我们可以轻松画出此有向图的邻接表

 下面我们通过代码来实现图的邻接表存储结构。

 

邻接表存储

定义所需的结构体：

 

//定义邻接表结点的结构
struct node
{
	int data;//结点名
	int weight;//权值
	node * next;//下一个结点的指针
	node()
	{
		next=NULL;
	}
};

//定义邻接表的表头
struct Head
{
	int data;//结点名
	node * first;//执行第一个结点
	Head()
       {
		first=NULL;
	}
};

 

 

定义一个宏表示图的总结点数：

 

#define MAXSIZE 5  //定义图的结点数

 定义表头指针数组

 

 

Head * head[MAXSIZE];//表头指针数组

 

 

有了上面的准备我们可以开始书写存储邻接表的函数了

具体代码如下：

 

//建立邻接表
void Create(Head * & head)
{
	
	while(true)
	{
		int name,wg;
		cin>>name;//输入结点
		if(name==-1)//输入-1表示链表结束
			break;
		cin>>wg;//输入权值
		node * temp=new node;//定义表结点
		temp->data=name;
		temp->weight=wg;
		//把表结点插入到head后面
		if(head->first==NULL)
			head->first=temp;
		else
		{
			temp->next=head->first;
			head->first=temp;
		}


	}

}

 到此我们就可以通过输入把图的信息存储到邻接表里，我们已经把图数据化了，下面就可以对图进行遍历了

 

首先我们要明白图的遍历的定义。

    从给定图中任意指定的顶点(称为起始点)出发，按照某种搜索方式沿着图的边访问图中所有的顶点，使每一个顶点仅被访问一次，这个过程就是图的遍历

 

深度优先搜索算法

     深度优先搜索算法的过程是：从图中某一个初始顶点v出发，首先访问初始顶点v，然后选择一个与顶点v相邻且没被访问过的顶点w为起始顶点，再从w出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。这里面涉及到回溯。

     根据此方法的过程，可以写出其代码

 

//递归深度优先搜索
void DFS_DG(Head *head[],int v,int visited[])//head[]-头指针数组，v-起始顶点，visited[]--标记数组
{
	node * p;//表结点
	visited[v]=1;
	cout<<v;
	p=head[v]->first;//获取第一个表结点
	while(p!=NULL)
	{
		if(visited[p->data]==0)//还没访问
			DFS_DG(head,p->data,visited);
		p=p->next;
	}
}

 

 

广度优先搜索算法

 

广度优先算法里面我们使用到队列，首先学习下队列。

 

队列

    队列也是一种运算受限的线性表。在这种线性表上，插入限定在表的某一端进行，删除限定在表的另一端进行。允许插入的一端称为队尾（Rear)，允许删除的一端称为队头（Front)。

    特点：队列中数据元素的入队和出队过程是按照“先进先出”的原则进行的。因此，队列又称为“先进先出”的线性表，简称FIFO表。

 这里我们使用顺序队列，为了充分的使用数组中的存储空间，把数组的前端和后端连接起来，形成一个环形的顺序表。下面我们将来介绍顺序队列

 

队空的条件

rear==front

 

队满的条件

(rear+1)%MAXSIZE==front//MAXSIZE队的容量

 

初始化队列很简单：

int queue[MAXSIZE],front=0,rear=0;//顺序队列，front是头，rear是尾，队列是插尾删头，先进先出

 

在队列不满的时候入队：

if((rear+1)%MAXSIZE==front)//即队满了
      return；
//入队
rear=(rear+1)%MAXSIZE；
queue[rear]=data;

 

在队不为空的时候出队

if(rear==front)//空队
    return;
//入队
front=(front+1)%MAXSIZE;
data=queue[front];

 

有了上面的队列知识，我们可以开始学习广度优先搜索了。

 

广度优先搜索算法过程是：广度优先搜索是从图的某个顶点v₀出发，在访问v₀之后，依次搜索访问v₀的各个未被访问过的邻接点w₁，w₂，…。然后顺序搜索访问w₁的各未被访问过的邻接点，w₂的各未被访问过的邻接点，…。以此类推，直到图中所有和初始点v有路径想通的顶点都被访问完为止。

 

其代码为：

//广度优先搜索遍历--使用队列
void BFS(Head *head[],int v)
{
	node *p;//表结点指针
	
	int queue[MAXSIZE],front=0,rear=0;//顺序队列，front是头，rear是尾，队列是插尾删头，先进先出
	int visited[MAXSIZE]={0};//访问标志数组初始化为0

	//开始访问
	cout<<v;
	visited[v]=1;
	rear=(rear+1)%MAXSIZE;
	queue[rear]=v;//入队

	int ok;
	while(front!=rear)//队列不为空
	{
		front=(front+1)%MAXSIZE;
		ok=queue[front];//出队
		p=head[ok]->first;//获取第一个表结点
		while(p!=NULL)//循环遍历其表结点
		{
			if(visited[p->data]==0)//该表结点没有访问过
			{
				cout<<p->data;
				visited[p->data]=1;
				rear=(rear+1)%MAXSIZE;
				queue[rear]=p->data;//入队
			}
			p=p->next;//找下一个结点
		}
	}
}

 

附上源码地址：https://github.com/longpo/algorithm/tree/master/Graph