（十二）图的遍历
深度优先搜索
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G)
{
// 访问函数为visit()
for(v = 0; v < G.vexnum; v++) {
visited[v] = false; // 初始化标记数组
}
for(v = 0; v < G.vexnum; v++) {
if(!visited[v]) DFS(G, v); // 如果v没有被访问过，则下一次从v结点开始深搜
}
}
// 深搜
void DFS(Graph G, int v)
{
// 从顶点v开始进行深搜
visit(v);
visited[v] = true; // 修改已访问结点的标记位
for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
if(!visited[w]) DFS(G, w); // 递归深搜
}
}
广度优先搜索
bool visited[MAX_VERTEX_NUM]; // 访问标记数组
void BFSTraverse(Graph G)
{
// 广搜，访问函数为visit()
for(int i = 0; i < G.vexnum; i++) {
visited[i] = false; // 初始化visited数组，开始的时候所有的结点均未被访问false
InitQueue(Q); // 队列初始化
for(int i = 0; i < G.vexnum; i++) {
if(!visited[i]) BFS(G, i); // 如果vi未被访问，从vi开始bfs广搜
}
}
}
// 广搜
void BFS(Graph G, int v)
{
// 从顶点v开始进行广搜
visit(v); //访问开始搜索的结点
visited[v] = true; // 结点访问后修改访问标记
Enqueue(Q, v); // 顶点v入队
while(!IsEmpty(Q)) {
Dequeue(Q, v); // 顶点v出队
for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
// 检测所有与v相邻的结点
if(!visited[w]) {
visit(w);
visited[w] = true;
Enqueue(Q, w); // 访问后的结点w入队
}
}
}
}
示例：
广搜示例
上图广搜遍历结果为：abcdefgh
BFS算法求解非带权图单源最短路径算法：
void BFS_MIN_Distance(Graph G, int u)
{
// d[i] 表示从u到i结点的最短路径
for(int i = 0; i < G.vexnum; i++) {
d[i] = ∞; // 初始化路径长度
}
visited[u] = true; d[u] = 0;
Enqueue(Q, u);
while(!IsEmpty(Q)) {
Dequeue(Q, u); // 队头元素u入队
for(w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)) {
if(!visited[w]) {
visited[w] = true;
d[w] = d[u] + 1; // 路径长度加1
Enqueue(Q, w); // 下一顶点w入队
}
}
}
}
（十三）最小生成树
感觉prime算法和kruskal算法的代码应该不会考，应该会考个构造思想。
（十四）最短路径
Dijkstra算法求单源最短路径
［注］单源最短路径是图中某一顶点到其他各顶点的最短路径
讲解示例：https://blog.csdn.net/qq_35644234/article/details/60870719
bool vis[VEXNUM];
int d[VEXNUM];
int w[VEXNUM][VEXNUM];
void dijkstra(int start)
{
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++) {
d[i] = (i == start ? 0 : inf);
}
vis[1] = 1; // 起始结点标记
for(int i = 1; i <= n-1; i++) {
int x, mini = inf;
for(int y = 1; y <= n; y++) {
if(!vis[y] && d[y] <= mini) {
mini = d[y];
x = y;
}
}
vis[x] = 1; // 找到的结点被访问修改标记数组
for(int y = 1; y <= n; y++) {
d[y] = min(d[y], d[x] + w[x][y]);
}
}
}
Floyd算法求解多源最短路
初始数组为A（k）[i][j]和arcs[i][j]，其中第一个数组为经过k由i到j的路径长度，arcs是图中由i直接到j的路径长度
迭代过程就一个式子A(k)[i][j]=Min{A(k-1)[i][j], A(k-1)[i][k] + A(k-1)[k][j]}, k=0,1,...n-1。迭代n次后得到A(n-1)[i][j]就是vi到vj的最短路径长度。
// 结构定义
#define Max 100
typedef struct graph *Graph;
typedef struct graph
{
int e , n;
int data[Max][Max];
}graph;
// Floyd算法
void Floyd(Graph g , int Path[][Max])
{
int i , j , k;
int A[Max][Max];
for(i = 0 ; i < g->n ; i++)
{
for(j = 0 ; j < g->n ; j++)
{
A[i][j] = g->data[i][j];
Path[i][j] = -1;
}
}
for(i = 0 ; i < g->n ; i++)
{
for(j = 0 ; j < g->n ; j++)
{
for(k = 0 ; k < g->n ; k++)
{
if(A[j][k] > A[j][i] + A[i][k])
{
A[j][k] = A[j][i] + A[i][k];
Path[j][k] = i;
}
}
}
}
}
// 打印路径代码
void showPath(int Path[][Max] , int res , int des)
{
if(Path[res][des] != -1)
{
printf("%d ",Path[res][des]);
int mid = Path[res][des];
// showPath(Path,res,mid);
showPath(Path,mid,des);
}
else
{
printf("%d",des);
}
}
（十五）拓扑排序
bool TopologicalSort(Graph G) {
InitStack(S); // 初始化栈，存储入度为0的顶点
for(int i = 0; i < G.vexnum; i++) {
if(indegree[i] == 0) Push(S, i);
}
int count = 0; // 记录当前已经输出的顶点数
while(!IsEmpty(S)) {
Pop(S, i); // 栈顶元素出栈
print[count++] = i; // 输出顶点i
for(p = G.vertices[i].firstarc; p; p = nextarc) {
// 将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
v = p -> adjvex;
if(!(--indegree[v])) Push(S,v); // 入度为0，则入栈
}
}
if(count < G.vexnum) return false; // 排序失败
else return true;
}
拓扑排序也可使用深度优先遍历实现
（十七）堆排序
在元素个数为n的序列上建堆，时间复杂度为O(n)。说明可以在线性时间内，将一个无序数组建成一个大顶堆。
向上调整操作如图
// 17. 堆排序，最大堆调整算法
#-*-coding:utf8;-*-
#qpy:3
#qpy:console
# 堆排序
def buildMaxHeap(A,n):
for i in range(n//2,0,-1):
adjustDown(A,i,n)
def adjustDown(A,k,n):
A[0]=A[k] # 将元素k向下调整
i=2*k
while i<=n:
if i<n and A[i]<A[i+1]: # 找出左右孩子中较大的值
i+=1
if A[0]>=A[i]: # 父结点的值大于孩子结点的最大值，则结束
break
else:
A[k]=A[i] # 将A［i］的值调整到父结点上
k=i # 修改k值，继续向下筛选
i*=2
A[k]=A[0] # 将被筛选的元素放入最终位置
def heapsort(A,n):
# 初始建堆
for idx in range(n,1,-1):
# 输出堆顶元素
tmp=A[1]
A[1]=A[idx] # 将堆底元素调整到堆顶
A[idx]=tmp
print('idx=',idx,'调整前对应序列',A[1:])
adjustDown(A,1,idx-1)
print('idx=',idx,'调整后对应序列',A[1:])
if __name__ == '__main__':
A=[0,1,2,3,4,5]
# 建立最大堆
buildMaxHeap(A,len(A)-1)
print('初始序列：',A[1:])
heapsort(A,len(A)-1)
print('res:',A[1:])
print('堆排结束...')
删除堆顶元素时，先将堆的最后一个元素与堆顶元素交换，由于此时堆的性质被破坏，需对此时的根结点进行向下调整；对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点执行向上调整。
（十八）快速排序
void QuickSort(int A[], int low, int high)
{
if(low < high) { // 递归跳出的条件
// Partition() 划分操作，分成两个子序列
int pivotpos = Partition(A, low, high);
QuickSort(A, low, pivotpos-1);
QuickSort(A, pivotpos+1, high);
}
}
// 划分子序列两个子序列函数，找到分割点
int Partition(int A[], int low, int high)
{
int pivot = A[low];
while(low < high) {
while(low < high && A[high] >= pivot) -- high; // 找到第一个比第一位小的元素
A[low] = A[high]; // 将比枢轴值小的元素移到左端
while(low < high && A[low] <= pivot) ++low; // 找到第一个比枢轴值大的元素
A[high] = A[low]; // 将比枢轴值大的元素移到右端
}
A[low] = pivot; // low和high指针指向同一位置，将枢轴值放到最终位置
return low; // 返回分割点的位置
}
［注］当每一趟序列能够分成两个长度相近的序列时，快排效率越高。
