学习目标：

复习俩这玩意

邻接表相当于图的压缩存储，遍历和图思路一样.

最小生成树算法与单源最短路径算法仅差两行代码.

学习任务：

1. 抄写代码

2. 学习成果目录

   1数据结构 C 代码 7.2: 邻接表及广度优先遍历

   1.1全部代码

   1.2测试结果

   27.3: Prim 算法与 Dijkstra 算法

   2.1全部代码

   2.2测试结果

   2.3图解

   ---

代码说明：

  （一） 邻接表及广度优先遍历

1. 队列方面的代码是从 7.1 中拷贝而来.
2. 构建图的代码也是现成的.
3. 将矩阵形式转成了邻接表形式.
4. 遍历邻居的时候用了 for, 它实质上是一个 while.

  （二）Prim 算法与 Dijkstra 算法

1. 图与网络的存储都可以用矩阵. 前者存的是 boolean 值, 后者存的是权值.
2. Prim 是做最小生成树, 即对应于道路构建; Dijkstra 算法是做单源最短路径, 应用于地图寻径.
3. O(n2) 的时间复杂度由贪心选择策略, 以及精巧的预处理获得.
4. 如果用邻接表来做, 速度会更快.
5. 实际上, 时间复杂度可以优化到 O(nlogn), 参见  张星移的博客.

学习时间：

2022.5.19

1数据结构 C 代码 7.2: 邻接表及广度优先遍历

1.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;

typedef struct AdjacencyNode
{
	int column;
	struct AdjacencyNode* next;
}*AdjacencyNodePtr;

typedef struct AdjacencyList
{
	int numNodes;
	struct AdjacencyNode* headers;
}*AdjacencyListPtr;

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(AdjacencyListPtr paraPtr)
{
	int i;
	visited = (int*)malloc(paraPtr->numNodes * sizeof(int));
	
	for(i = 0;i < paraPtr->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;
}

AdjacencyListPtr graphToAdjacency(graphPtr paraGraph)
{
	int i,j;
	int tempNodes = paraGraph->numNodes;
	//分配空间 
	AdjacencyListPtr resultList = (AdjacencyListPtr)malloc(sizeof(struct AdjacencyList));
	resultList->numNodes = tempNodes;
	resultList->headers = (AdjacencyNodePtr)malloc(tempNodes * sizeof(struct AdjacencyNode));
	
	 
	AdjacencyNodePtr p,q;
	
	for(i = 0;i < tempNodes;i ++)
	{
		//每一次都指向下一个元素，即下一个链表的头结点 
		p = &(resultList->headers[i]);
		p->column = -1;
		p->next = NULL;
		
		for(j = 0;j < tempNodes;j ++)
		{
			if(paraGraph->connections[i][j] == 1)
			{
				q = (AdjacencyNodePtr)malloc(sizeof(struct AdjacencyNode));
				q->column = j;
				q->next = NULL;
				
				//链接过去，并让p跟踪 
				p->next = q;
				p = q;
			}
		}
	}
	
	return resultList;
}

void printAdjacencyList(AdjacencyListPtr paraList)
{
	printf("打印邻接列表:n");
	//用p来跟踪，一个一个打印就好
	AdjacencyNodePtr p;
	int i;
	for(i = 0; i < paraList->numNodes;i ++)
	{
		//当p跟踪玩当前链表后，记得要把p指向下一个链表头结点的next
		p = paraList->headers[i].next;
		while(p != NULL)
		{
			printf("%d ",p->column);
			p = p->next;
		}
		printf("n");
	}
}

void wideTranverse(AdjacencyListPtr paraList,int paraNum)
{
	printf("邻接列表的广度优先搜索:n");
	int temp;
	//初始化visited 
	visitedInit(paraList);
	//创建队列 
	graphQueuePtr tempQueue = queueInit();
	enqueue(tempQueue,paraNum);
	visited[paraNum] = 1;
	printf("%d ",paraNum);
	
	//还是用p跟踪 
	AdjacencyNodePtr p;
	while(tempQueue->front != tempQueue->rear)
	{
		temp = dequeue(tempQueue);
		//出队了就让p指向对应的这个链表的头部的next 
		p = paraList->headers[temp].next;
		//p == NULL就代表这个链表循环完了 
		while(p != NULL)
		{
			//如果没被访问过，就直接入队 
			if(visited[p->column] == 0)
			{
				enqueue(tempQueue,p->column);
				printf("%d ",p->column);
				visited[p->column] = 1;
			}
			
			//注意这个要写在外面，无论是否被访问了都要往后走 
			p = p->next;
		}
	}
	
}

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("准备完毕rn");
	
	graphPtr tempGraphPtr = graphInit(tempPtr,5);
	AdjacencyListPtr tempListPtr = graphToAdjacency(tempGraphPtr);
	
	printAdjacencyList(tempListPtr);
	
	wideTranverse(tempListPtr, 4);
}

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

1.2测试结果

准备数据
准备完毕
打印邻接列表:
1 3
0 2 4
1 3 4
0 2
1 2
邻接列表的广度优先搜索:
4 1 2 0 3

27.3: Prim 算法与 Dijkstra 算法

2.1全部代码

#include 
#include 

//表示无穷 
#define MAX 100000

typedef struct net
{
	int **weights;
	int numNode;
}*netPtr;


netPtr netInit(int paraNodes,int **paraArray)
{
	int i,j;
	
	//全是动态的，都要malloc 
	netPtr resultNet = (netPtr)malloc(sizeof(struct net));
	resultNet->weights = (int**)malloc(paraNodes*sizeof(int*));
	for(i = 0;i < paraNodes;i ++)
	{
		resultNet->weights[i] = (int*)malloc(paraNodes*sizeof(int));
	}
	
	//纯纯拷贝 
	resultNet->numNode = paraNodes;
	for(i = 0;i < paraNodes;i ++)
		for(j = 0;j < paraNodes;j ++)
			resultNet->weights[i][j] = paraArray[i][j];
	
	return resultNet;
}


void PrimOrDijkstra(netPtr paraNet,int paraAlgorithm)
{
	int i,j,tempBestNode,minDistance,resultCost;
	int *visited,*parent,*distant;
	int numNodes = paraNet->numNode;
	
	//这里是用来存放是否访问过、父节点、最短距离的数组 
	visited = (int*)malloc(sizeof(int) * paraNet->numNode);
	parent = (int*)malloc(sizeof(int) * paraNet->numNode);
	distant = (int*)malloc(sizeof(int) * paraNet->numNode);
	
	//我们默认起始点为0开始构建。 
	int source = 0;
	
	//初始化
	for(i = 0;i < paraNet->numNode;i ++)
	{
		visited[i] = 0;
		parent[i] = source;
		distant[i] = paraNet->weights[source][i];
	}
	
	distant[source] = 0;
	visited[source] = 1;
	parent[source] = -1;
	
	//算法开始，第一个结点已经在网中了，我们只需循环n-1次 
	for(i = 0;i < numNodes-1;i ++)
	{
		
		minDistance = MAX;
		for(j = 0;j < numNodes;j ++)
		{
			if(distant[j] < minDistance && visited[j] == 0)
			{
				minDistance = distant[j];
				tempBestNode = j;
			}
		}
		//找到之后就表示他以及被放问过了，即已经入网了 
		visited[tempBestNode] = 1;
		
		
		for(j = 0;j < numNodes;j ++)
		{
			//在网中直接下一个 
			if(visited[j] == 1)
			{
				continue;
			}
			
			 
			if(paraNet->weights[tempBestNode][j] >= MAX)
			{
				continue; 
			}
			
			//这里算法出现一点点分支 0是最短路径，1是最小生成树 
			if(paraAlgorithm == 0)
			{
				 
				for(j = 0;j < numNodes;j ++) 
				{
					if(distant[tempBestNode] + paraNet->weights[tempBestNode][j] < distant[j])
					{
						distant[j] = paraNet->weights[tempBestNode][j] + distant[tempBestNode];
						parent[j] = tempBestNode;
					}
				}
			}
			
			if(paraAlgorithm == 1)
			{
				 
				for(j = 0;j < numNodes;j ++) 
				{
					if(paraNet->weights[tempBestNode][j] < distant[j])
					{
						distant[j] = paraNet->weights[tempBestNode][j];
						parent[j] = tempBestNode;
					}
				}
			}
			
		}
	}
	
	printf("所有节点的父节点依次为: n");
	//打印父节点 
	for(i = 0; i < numNodes; i++) 
	{
		printf("%d ", parent[i]);
	}
	printf("n");
	
	
	if(paraAlgorithm == 0) 
	{
		 
		printf("所有节点的路径长度依次为：n ");
		for(i = 0; i < numNodes; i++) 
		{
			printf("%d ", distant[i]);
		}
	} 
	if(paraAlgorithm == 1) 
	{
		 
		resultCost = 0;
		for(i = 0; i < numNodes; i++) 
		{
			resultCost += distant[i];
			printf("节点%d 的路径长度为 %d , 总路径长度为 %dn", i, distant[i], resultCost);
		}
		printf("最后，总路径长度为 %d.n ", resultCost);
	}
	
	printf("rn");
	
}

netPtr constructSampleNet() 
{
	int i, j;
	int myGraph[6][6] = 
	{ 
	{0, 6, 1, 5, 0, 0},
	{6, 0, 5, 0, 3, 0}, 
	{1, 5, 0, 5, 6, 4}, 
	{5, 0, 5, 0, 0, 2}, 
	{0, 3, 6, 0, 0, 6},
	{0, 0, 4, 2, 6, 0}
	};
	int** tempPtr;
	int numNodes = 6;
	printf("准备数据n");
	
	tempPtr = (int**)malloc(numNodes * sizeof(int*));
	for (i = 0; i < numNodes; i ++) 
	{
		tempPtr[i] = (int*)malloc(numNodes * sizeof(int));
	}
	
	for (i = 0; i < numNodes; i ++) 
	{
		for (j = 0; j < numNodes; j ++) 
		{
			if (myGraph[i][j] == 0) 
			{
				tempPtr[i][j] = MAX;
			}
			else 
			{
				tempPtr[i][j] = myGraph[i][j];
			}
		}
	}
	
	printf("准备完毕n");
	
	netPtr resultNetPtr = netInit(numNodes, tempPtr);
	return resultNetPtr;
}

void testPrim() 
{
	netPtr tempNetPtr = constructSampleNet();
	printf("=====Dijkstra 算法=====n");
	PrimOrDijkstra(tempNetPtr, 0);
	printf("=====  Prim 算法  =====n");
	PrimOrDijkstra(tempNetPtr, 1);
}
int main()
{
	testPrim();
} 

2.2测试结果

准备数据
准备完毕
=====Dijkstra 算法=====
所有节点的父节点依次为:
-1 0 0 0 2 2
所有节点的路径长度依次为：
 0 6 1 5 7 5
=====  Prim 算法  =====
所有节点的父节点依次为:
-1 2 0 5 1 2
节点0 的路径长度为 0 , 总路径长度为 0
节点1 的路径长度为 5 , 总路径长度为 5
节点2 的路径长度为 1 , 总路径长度为 6
节点3 的路径长度为 2 , 总路径长度为 8
节点4 的路径长度为 3 , 总路径长度为 11
节点5 的路径长度为 4 , 总路径长度为 15
最后，总路径长度为 15.

2.3图解

好图我用[doge]

1.Dijkstra 算法里面的距离数组就是0到每个结点的最短路径长度

2.  Prim 算法  里面的距离数组就是这个结点到父节点的路径长度