图（二）——图的遍历_给定一个无向图,输出指定顶点出发的深度优先遍历序列。在深度优先遍历的过程中,如

目录

→ 图的遍历

→ 深度优先搜索遍历

↓ 基本思想：

↓ → 递归深度优先搜索遍历

↓    算法思想：

↓ →非递归深度优先搜索遍历

↓  算法思想：

→  广度优先搜索遍历

↓  基本思想：

→  算法实现的综合应用：（无向图为例）                                

 ↓ 运行结果：

 ↓ 算法实现：

 ↓  → 算法实现过程中的注意点及解决方法：

  ↓  注意点一：

  ↓  解决方法：

  ↓  注意点二：

  ↓  解决方法：

---

图的遍历

    图的遍历是从图中某个顶点出发，访遍图中其余顶点，且都访问一次的过程。

    图与树类似，不同的是图的每个顶点都有可能与其余所有顶点邻接，为避免重复访问同一个顶点，在遍历的过程中应标记该顶点访问过。

思考：

      对于图中有回路，对于连通图，如何实现遍历只访问每个顶点一次，也就是遇到回退的情况或图中顶点都已完成访问时如何确保不会再次访问顶点？

      设置一个标志数组 Visited【】实现，此数组用于标记所有顶点是否访问过，初始值为0，如果访问过，更新此顶点的标志为1，这样遇到上述情况时，判断顶点的标志数组是否为1即可解决。

      图的遍历方法有：深度优先搜索遍历和广度优先搜索遍历，两种遍历方法对无向图，有向图都适用。通过图的遍历可以知道图是否为连通图。

---

深度优先搜索遍历

深度优先搜索遍历和二叉树的先序遍历类似，尽可能先对纵深方向进行搜索。

基本思想：

    先从图的某个顶点 V0 出发，访问顶点，然后依次从V0 各个未访问的邻接点出发深度优先搜索遍历，直到所有和 V0 相通的顶点都被访问到。如果是非连通图，上述操作结束后，需要再选另一个图中未被访问的顶点作为新的出发点，重复上述操作。

                              

   深度优先搜索遍历的结果为：A B D F C G E H I 。

  一个顶点可能会有多个邻接点，访问次序不同，所以图的遍历的序列不唯一。

  对于邻接矩阵存储结构的图，适合稠密图 ，遍历时，需要检查n^2个元素，时间复杂度为O（n^2）。

  邻接表存储结构的图，适合稀疏图,找邻接点只需在边表中所有边结点检查一遍，时间为O（e），时间复杂度为O（n+e）。

---

递归深度优先搜索遍历

   采用递归的方式遍历，如果访问到顶点A1，根据判断条件知其没有邻接点(无法深度优先搜索遍历)，需要回退到上一个顶点A，继续查找A的其余邻接点A2，，，

    算法思想：

                   从一个顶点v出发

                  1、访问顶点，标记此顶点访问过

                  2、从邻接矩阵中找到顶点位置，依次选择其邻接点且并判断是否访问过，进行深度遍历。

     遍历伪代码：

void DFS(Graph g,int v0)
{
    visit(vo);            //访问顶点
    visited[v0]=1;        //标记访问过顶点
    w=FirstAdjVex(g,vo);   //查找vo的第一个邻接点
    while(w!=-1)          // 邻接点存在
         {
             if(!visited[w])     //邻接点未访问过
                DFS(g,w);
             w=NextAdjVex(g,vo,w);  //  vo的下一个邻接点
          }
}
void TraverseG(Graph g)
{
     for(v=0;v<g.vexnum;v++)  //对标记数组进行初始化为0，
         vistied[v]=0;
     for(v=0;v<g.vexnum;v++)
        {
            if(!visited[v])
               DFS(G,v);
         }
}
               

---

非递归深度优先搜索遍历

二叉树遍历时已经知道，对于递归遍历可以通过栈转化为非递归遍历的形式。

  算法思想：

                 1、栈初始化

                 2、访问顶点，标记访问过，该顶点入栈

                 3、当栈不为空时：

                              1 、取栈顶顶点的位置，存在未被访问的邻接点w

                              2、访问顶点w，标记访问，w顶点入栈（便于查找w顶点的其他邻接点）然后在栈不为空的条件下重复上述操作。

                              3、否则，当前顶点出栈，（表明顶点的邻接点都访问过，或该栈顶顶点没有邻接点，出栈，继续寻找现在栈顶顶点的邻接点）。

---

广度优先搜索遍历

基本思想：

   广度优先搜索遍历与二叉树的层次遍历类似，从某个顶点出发开始访问，先访问该顶点的所有邻接点，然后根据其邻接点的访问顺序再访问各自的所有邻接点，直到所有与顶点路径相通的顶点都被访问到。图中若有未被访问到，另选该顶点作为出发点。

                         

广度优先搜索遍历的结果为：A B C D E F G H I 。

 算法思想：

    根据队列的特点，先进先出，访问顶点时入队，并标记访问过，然后出队，队头元素出队时，依次将其未被访问到的顶点访问并入队，每个顶点都入队一次。

    从V0顶点出发

    1、队初始化

    2、访问V0顶点，标记访问过，并入队

    3、当队不为空时：

                        出队；

                        将出队的顶点所有未被访问过的顶点访问，标记并入队。

---

算法实现的综合应用：（无向图为例）       

---

                        

运行结果：

                                                

                      

---

算法实现：

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 20
typedef struct
{
	int arcs[MAXVEX][MAXVEX];
	char vex[MAXVEX];
	int vexnum;
	int arcnum;
}AdjMatrix;
//对图的顶点初始化
AdjMatrix* Init()
{
	AdjMatrix* G = (AdjMatrix*)malloc(sizeof(AdjMatrix));
	if (G == NULL)
		printf("申请内存错误");
	for (int i = 0; i <MAXVEX; i++)        //对矩阵初始化为0
	{
		for (int j = 0; j < MAXVEX; j++)
			G->arcs[i][j] = 0;
	}
	for (int i = 0; i < MAXVEX; i++)
		G->vex[i] = 0;
	G->vexnum = 0;
	G->arcnum = 0;
	return G;
}
//===================================  邻接矩阵存储结构创建图  =========================
//查找匹配的顶点在矩阵中的位置
int LocateVex(AdjMatrix* G, char v)
{
	int i;
	for (i = 1; i <= G->vexnum; i++)
	{
		if (G->vex[i] == v)
			return i;
	}
	return 0; 
}
AdjMatrix* Create()  
{    
	AdjMatrix* G=Init();
	int i, j, k;
	char vex1, vex2;
	printf("----输入图的顶点数与边数-----\n");
	scanf("%d%d", &G->vexnum, &G->arcnum);
	printf("-----依次输入图中%d个顶点------\n", G->vexnum);
	for (i = 1; i <=G->vexnum; i++)
	{
		scanf(" %c",&(G->vex[i]));           //注意点一：
	}
	printf("-----输入图中%d条边-----\n", G->arcnum);
	for (k = 1; k <= G->arcnum; k++)
	{
		printf("第%d条边：\n ", k);
		scanf(" %c", &vex1);
		scanf(" %c", &vex2);
		i = LocateVex(G, vex1);
		j = LocateVex(G, vex2);
		G->arcs[i][j] = 1;
		G->arcs[j][i] = 1;
	}
	printf("=================》邻接矩阵建立图完成  ================《\n");
	return G;
}
//====================================  邻接矩阵递归深度搜索遍历  ======================
void DFS(AdjMatrix*G, int v)      
{
	int i = 0;
	static int visited[20];          //注意点二：
	printf("%c ", G->vex[v]);
	visited[v] = 1;
	for (i = 1; i <= G->vexnum; i++)
	{
		if (G->arcs[v][i] != 0 && visited[i] != 1)
			DFS(G, i);
	}
}
//========================================  栈  =======================================
//定义结点结构
typedef struct Node
{
	char data;
	struct Node* next;
}Slstacktype;
//初始化栈头指针
Slstacktype* Initstack()
{
	Slstacktype* top = (Slstacktype*)malloc(sizeof(Slstacktype));
	top->next = NULL;
	return top;
}
//进栈
Slstacktype* Push(Slstacktype* top,char vex)
{
	Slstacktype* p=(Slstacktype*)malloc(sizeof(Slstacktype));
	if (p == NULL)
		return NULL;
	p->data = vex;
	p->next = top->next;
	top->next = p;
	return top;
}
//出栈
Slstacktype* Pop(Slstacktype* top)
{
	Slstacktype* q;
	if (top->next == NULL)  //判断栈是否为空
		return NULL;
	q = top->next;
	top->next = q->next;
	free(q);
	return top;
}
//===================================  非递归邻接矩阵存储结构的深度搜索遍历  =============
//取栈顶顶点的位置
int include_stack(AdjMatrix* G, Slstacktype* top)  
{
	int i;
	for (i = 1; i <= G->vexnum; i++)
	{
		if (G->vex[i] == top->next->data)
			return i;
	}
	return 0;
}
void DFS_stack(AdjMatrix*G,int v)
{
	int i;
	Slstacktype* top = Initstack(); //栈的初始化
	static int visited[20];         //定义静态的标志数组
	printf("%c ", G->vex[v]);
	visited[v] = 1;
	Push(top, G->vex[v]);
	while (top->next != NULL)
	{
		v = include_stack(G, top);
		for (i = 1; i <= G->vexnum; i++)
		{
			if (G->arcs[v][i] != 0 && visited[i] != 1)
			{
				printf("%c ", G->vex[i]);
				visited[i] = 1;
				Push(top, G->vex[i]);
				break;
			}
		}
		if (i > G->vexnum)         //顶点的邻接点都访问过，或没有邻接点时退栈顶结点
		{
		top = Pop(top);
		}
	}
}
 
//===========================================  队列 ======================================
typedef struct Node2
{
	char data;
	struct Node2* next;
}QNode;
typedef struct
{
	QNode* front;
	QNode* rear;
}LQNode;
//队的初始化
LQNode* Init_Q()
{
	LQNode* p = (LQNode*)malloc(sizeof(LQNode));
	QNode* q = (QNode*)malloc(sizeof(QNode));
	p->front = p->rear = q;
	q->next = NULL;
	return p;
}
//入队
void Push_Q(LQNode* p, char vex)
{
	QNode* q = (QNode*)malloc(sizeof(QNode));
	if (q == NULL)
		printf("申请空间错误");
	q->data = vex;
	q->next = NULL;
	p->rear->next = q;
	p->rear = q;
}
//出队
char Pop_Q(LQNode* p)
{
	char vex;
	QNode* q;
	if (p->front == p->rear)
		return ;
	q = p->front->next;
	p->front->next = q->next;
	vex = q->data; 
	if (p->front->next == NULL)
		p->rear = p->front;
	free(q);
	return vex;
}
//========================================== 邻接矩阵的广度优先搜素遍历 ====================
int include_Q(AdjMatrix* G, char vex)   //取出队顶点在邻接矩阵中的位置
{
	for (int i = 1; i <= G->vexnum; i++)
	{
		if (G->vex[i] == vex)
			return i;
	}
	return 0;
}
void BFS(AdjMatrix* G, int v)
{
	static visited[20];
	LQNode* p = Init_Q();
	printf("%c ", G->vex[v]);
	visited[v] = 1;
	Push_Q(p, G->vex[v]);
	while (p->front->next!=NULL)
	{
		int i;
		v = include_Q(G,Pop_Q(p));
		for (i = 1; i <= G->vexnum; i++)
		{
			if (G->arcs[v][i] != 0 && visited[i] != 1)
			{
				printf("%c ", G->vex[i]);
				visited[i] = 1;
				Push_Q(p, G->vex[i]);
			}
		}
	}
}
//========================================   打印邻接矩阵  ==============================
void print(AdjMatrix* G)
{
	for (int i = 1; i <= G->vexnum; i++)
	{
		for (int j = 1; j <= G->vexnum; j++)
		{
			printf("%d ", G->arcs[i][j]);
		}
		printf("\n");
	}
}
main()
{
	int v;
	printf("==============》 邻接矩阵存储结构创建图 《===========\n");
	AdjMatrix* G = Create();  
	printf("==============》  打印邻接矩阵 《============\n");
	print(G);
	printf("\n");
	printf("----输入遍历起始位置-----\n");
	scanf("%d", &v);
	printf("==============》  递归 深度搜索遍历  《========== \n");
	DFS(G, v);
	printf("\n");
	printf("==============》 非递归 深度搜索遍历 《========== \n");
	DFS_stack(G, v);
	printf("\n");
	printf("==============》  广度优先搜索遍历   《==============\n ");
	BFS(G, v);
	printf("\n");
}

---

算法实现过程中的注意点及解决方法：

   注意点一：

      再多次用scanf（）函数输入值时，输入的是字符类型的值时，需要考虑scanf函数的问题

  解决方法：

      可以在 %c前面空格用于接收留在缓冲区中的空格、回车等符号

   注意点二：

       定义的标志数组，需要初始化为0，每次访问过后需要更新为1，然而在递归函数中，每一次调用都会重新初始化数组，然后就会造成死循环的情况（可以试试写写，印象更深）。

    解决方法：

      可以定义一个大一点的数组，利用静态数组未初始化就会给所有的数组元素赋初值0，就很好的解决这个问题。

       静态数组：静态数组的长度是预先定义好的,在整个程序中,一旦给定大小后就无法改变。 静态数组在内存中位于静态存储区,,在运行时这个大小不能改变,在函数执行完以后,系统自动销毁; 如:int a[10]; 虽然c语言规定,只有静态存储的数组才能初始化,但一般的c编译系统都允许对动态存储的数组赋初值。静态存储的数组如果没有初始化,系统自动给所有的数组元素赋0。