图（二）——图的遍历-创新互联

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

  算法思想：

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#include#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; iarcs[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。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧