数据结构 C 代码 7.1: 图的遍历

学习目标：图是我们学习的最复杂数据结构，一定要弄明白！

学习任务：

1. 抄写代码

2. 目录

   1全部代码

   2测试结果

   3遍历的异同

   2.1图的深度优先搜索和二叉树的先序遍历算法相似。

   2.2图的广度优先搜素与二叉树的层次遍历算法相似。

   2.3图解，简单来说

   ---

代码说明：

1. 深度优先用递归.
2. 广度优先用栈, 其实和二叉树的遍历很像, 队列也是从那边抄过来改巴改巴就可以了.

学习时间：

2022.6.5

1全部代码

#include 
#include 

#define MAXSIZE 10


int* visited;  

 
typedef struct graph
{
	int** connections;
	int numNodes;
}*graphPtr;


typedef struct graphQueue
{
	int *node;
	int front;
	int rear;
}*graphQueuePtr;

graphQueuePtr queueInit()
{
	graphQueuePtr resultQueue = (graphQueuePtr)malloc(sizeof(struct graphQueue));
	resultQueue->node = (int*)malloc(MAXSIZE * sizeof(int));
	
	resultQueue->front = 0;
	resultQueue->rear = 0;
	return resultQueue;
}

void enqueue(graphQueuePtr paraQueue,int paraData)
{
	if((paraQueue->rear + 1) % MAXSIZE == (paraQueue->front) % MAXSIZE)
	{
		printf("队列满了，无法入队！n");
		return ;
	}
	
	paraQueue->node[(paraQueue->rear) % MAXSIZE] = paraData;
	paraQueue->rear = (paraQueue->rear + 1) % MAXSIZE;
}

int dequeue(graphQueuePtr paraQueue)
{
	if(paraQueue->front == paraQueue->rear)
	{
		printf("队列为空，无法出队！n");
		return 0;
	}
	
	int temp =  paraQueue->node[(paraQueue->front) % MAXSIZE];
	paraQueue->front = (paraQueue->front + 1) % MAXSIZE;
	
	return temp;
}


void visitedInit(graphPtr paraGraph)
{
	int i;
	visited = (int*)malloc(paraGraph->numNodes * sizeof(int));
	
	for(i = 0;i < paraGraph->numNodes;i ++)
	{
		visited[i] = 0;
	}
}


graphPtr graphInit(int **paraConnections,int paraNumNodes)
{
	int i,j;
	graphPtr resultGraph = (graphPtr)malloc(sizeof(struct graph));
	resultGraph->numNodes = paraNumNodes;
	
	//这里如何给二维数组动态分配空间如果不明白可以参考我以前的二维数组文章 
	resultGraph->connections = (int**)malloc(resultGraph->numNodes * sizeof(int*));
	for(i = 0;i < resultGraph->numNodes;i ++)
	{
		resultGraph->connections[i] = (int*)malloc(resultGraph->numNodes * sizeof(int));
	}
	
	for(i = 0;i < resultGraph->numNodes;i ++)
		for(j = 0;j < resultGraph->numNodes;j ++)
	{
		resultGraph->connections[i][j] = paraConnections[i][j];
	}
	
	return resultGraph;
}


void depthTranverse(graphPtr paraGraph,int paraNum)
{
	int i;
	visited[paraNum] = 1;
	printf("%d ",paraNum);
	
	for(i = 0;i < paraGraph->numNodes;i ++)
	{
		 
		if(visited[i] == 0 && paraGraph->connections[paraNum][i] == 1)
		{
			depthTranverse(paraGraph,i);
		}
	}
}


void wideTranverse(graphPtr paraGraph,int paraNum)
{
	int i;
	int temp;
	//建立队列 
	graphQueuePtr tempQueue = queueInit();
	visited[paraNum] = 1;
	//入队的时候就打印出来 
	enqueue(tempQueue,paraNum);
	printf("%d ",paraNum);
	
	//循环结束条件就是队列为空 
	while(tempQueue->front != tempQueue->rear)
	{
		temp = dequeue(tempQueue);
		//出队一个元素就要入队与他连通且没有被访问过的元素
		for(i = 0;i < paraGraph->numNodes;i ++)
		{
			if(visited[i] == 0 && paraGraph->connections[temp][i] == 1)
			{
				visited[i] = 1;
				enqueue(tempQueue,i);
				printf("%d ",i);
			}
		}
	}
	
}

void testGraphTranverse() 
{
	int i, j;
	int myGraph[5][5] = 
	{ 
	{0, 1, 0, 1, 0},
	{1, 0, 1, 0, 1}, 
	{0, 1, 0, 1, 1}, 
	{1, 0, 1, 0, 0}, 
	{0, 1, 1, 0, 0}
	};
	int** tempPtr;
	printf("正在准备数据n");
	
	tempPtr = (int**)malloc(5 * sizeof(int*));
	for (i = 0; i < 5; i ++) 
	{
		tempPtr[i] = (int*)malloc(5 * sizeof(int));
	}
	
	for (i = 0; i < 5; i ++) 
	{
		for (j = 0; j < 5; j ++) 
		{
			tempPtr[i][j] = myGraph[i][j];
		}
	}
	
	printf("数据准备完毕n");
	
	graphPtr tempGraphPtr = graphInit(tempPtr,5);
	printf("节点个数为 %d n", tempGraphPtr -> numNodes);
	printf("图已被初始化n");
	
	printf("深度优先访问:n");
	visitedInit(tempGraphPtr);
	depthTranverse(tempGraphPtr, 4);
	
	printf("n广度优先访问:rn");
	visitedInit(tempGraphPtr);
	wideTranverse(tempGraphPtr, 4);
}

int main()
{
	testGraphTranverse();
	return 0;
}

2测试结果

正在准备数据
数据准备完毕
节点个数为 5
图已被初始化
深度优先访问:
4 1 0 3 2
广度优先访问:
4 1 2 0 3

3遍历的异同

1，相同点：都是对图的遍历，都是一行一行的来，从第四行开始，输出值为1的点所的列

2，不同点：

2.1图的深度优先搜索和二叉树的先序遍历算法相似。

它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

显然，深度优先搜索是一个递归的过程

深度优先遍历特点是，选定一个出发点后进行遍历，能前进则前进，若不能前进，回退一步再前进，或再回退一步后继续前进。依此重复，直到所有与选定点相通的所有顶点都被遍历。

2.2图的广度优先搜素与二叉树的层次遍历算法相似。

它的思想：首先从起始顶点v出发，访问顶点v，并将其入队；顶点v出队，依次访问与v相邻接未被访问过的顶点w1,w2,…,wi，并将其依次入队；然后顶点w1出队，依次访问与w1相邻接未被访问的顶点，并将其入队；然后顶点w2出队，依次访问与w2相邻接未被访问的顶点，并将其入队；直到图中所有顶点均被访问过为止。

2.3图解，简单来说

深度优先搜索（优先行）就是遍历列时有值为1，就跳到那一列遍历

广度优先搜索（优先列）就是遍历完整列，才跳到值为1的下一列遍历

	int myGraph[5][5] = 
	{ 
	{0, 1, 0, 1, 0},
	{1, 0, 1, 0, 1}, 
	{0, 1, 0, 1, 1}, 
	{1, 0, 1, 0, 0}, 
	{0, 1, 1, 0, 0}
	};