算法读书笔记第4章
图的这一章我主要学习了广度优先搜索（BFS）和深度优先搜索（DFS），这两种算法主要用于求取路径问题
bfs.c
/**
Name: bfs--借助队列实现
Author: Bryant_xw
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct graph
{ int nVertex; int nEdge; int *pMatrix;
}Graph;
typedef struct node
{ int nValue; struct node *pNext;
}MyQueue;
//定义队列
typedef struct queue
{ int nCount; MyQueue *pHead; MyQueue *pTail;
}Queue;
void q_Init(Queue **pQueue)
{ *pQueue = (Queue*)malloc(sizeof(Queue)); (*pQueue)->nCount = 0; (*pQueue)->pHead = NULL; (*pQueue)->pTail = NULL;
}
void q_Push(Queue *pQueue,int nNum)
{ if(pQueue == NULL)return; MyQueue *pTemp = NULL; pTemp = (MyQueue*)malloc(sizeof(MyQueue)); pTemp->nValue = nNum; pTemp->pNext = NULL; if(pQueue->pHead == NULL) { pQueue->pHead = pTemp; } else { pQueue->pTail->pNext = pTemp; } pQueue->pTail = pTemp; pQueue->nCount++;
}
int q_Pop(Queue*pQueue)
{ if(pQueue == NULL || pQueue->nCount == 0)return -1; MyQueue *pDel = NULL; int nNum; pDel = pQueue->pHead; nNum = pDel->nValue; pQueue->pHead = pQueue->pHead->pNext; free(pDel); pDel = NULL; pQueue->nCount--; if(pQueue->nCount == 0) { pQueue->pTail=NULL; } return nNum;
}
Graph *CreateGraph()
{ Graph *pGraph = NULL; pGraph = (Graph*)malloc(sizeof(Graph)); int nV; int nE; printf("请输入顶点个数与边的条数:\n"); scanf("%d%d",&nV,&nE); pGraph->nVertex = nV; pGraph->nEdge = nE; //申请矩阵 pGraph->pMatrix = (int*)malloc(sizeof(int)*nV*nV); memset(pGraph->pMatrix,0,sizeof(int)*nV*nV); int v1,v2; int i; for(i = 0;i<nE;i++) { printf("请输入两个顶点确定一条边:\n"); scanf("%d%d",&v1,&v2); //顶点在合理范围之内 且对应位置未被放置 if(v1 >= 1 && v1 <= nV && v2 >= 1 && v2 <= nV && pGraph->pMatrix[(v1-1)*nV + (v2-1)] == 0) { pGraph->pMatrix[(v1-1)*nV+(v2-1)] = 1; pGraph->pMatrix[(v2-1)*nV+(v1-1)] = 1; } else { i--; } } return pGraph;
}
void BFS(Graph *pGraph,int nBegin)
{ if(pGraph == NULL || nBegin <= 0|| nBegin > pGraph->nVertex)return; //申请辅助队列 Queue *pQueue = NULL; q_Init(&pQueue); //标记数组 int *pMark = NULL; pMark = (int*)malloc(sizeof(int)*pGraph->nVertex); memset(pMark,0,sizeof(int)*pGraph->nVertex); //起始顶点入队 q_Push(pQueue,nBegin); pMark[nBegin-1] = 1; while(pQueue->nCount != 0) { //弹出 打印 nBegin = q_Pop(pQueue); printf("%d ",nBegin); //遍历 int i; for(i = 0;i<pGraph->nVertex;i++) { //与其有关的且未被打印过的 if(pGraph->pMatrix[(nBegin-1)*pGraph->nVertex+i] == 1 && pMark[i] == 0) { //入队 标记 q_Push(pQueue,i+1); pMark[i] = 1; } } }
}
int main()
{ Graph *pGraph = NULL; pGraph = CreateGraph(); BFS(pGraph,4); return 0; }
dfs.c
/**
Name: dfs
Author: Bryant_xw
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct graph
{ int nVertex; int nEdge; int *pMatrix;
}Graph;
Graph *CreateGraph()
{ Graph *pGraph = NULL; pGraph = (Graph*)malloc(sizeof(Graph)); int nV; int nE; printf("请输入顶点个数与边的条数:\n"); scanf("%d%d",&nV,&nE); pGraph->nVertex = nV; pGraph->nEdge = nE; //申请矩阵 pGraph->pMatrix = (int*)malloc(sizeof(int)*nV*nV); memset(pGraph->pMatrix,0,sizeof(int)*nV*nV); int v1,v2; int i; for(i = 0;i<nE;i++) { printf("请输入两个顶点确定一条边:\n"); scanf("%d%d",&v1,&v2); //顶点在合理范围之内 且对应位置未被放置 if(v1 >= 1 && v1 <= nV && v2 >= 1 && v2 <= nV && pGraph->pMatrix[(v1-1)*nV + (v2-1)] == 0) { pGraph->pMatrix[(v1-1)*nV+(v2-1)] = 1; pGraph->pMatrix[(v2-1)*nV+(v1-1)] = 1; } else { i--; } } return pGraph;
}
void MyDFS(Graph *pGraph,int nBegin,int *pMark)
{ //打印 标记 printf("%d ",nBegin); pMark[nBegin-1] = 1; //遍历 int i; for(i = 0;i<pGraph->nVertex;i++) { //找到与当前顶点有关的 且未被打印过的 if(pGraph->pMatrix[(nBegin-1)*pGraph->nVertex + i] == 1 && pMark[i] == 0) { MyDFS(pGraph,i+1,pMark); } }
}
void DFS(Graph *pGraph,int nBegin)
{ if(pGraph == NULL || nBegin <= 0 ||nBegin > pGraph->nVertex)return; //标记数组 int *pMark = NULL; pMark = (int*)malloc(sizeof(int)*pGraph->nVertex); memset(pMark,0,sizeof(int)*pGraph->nVertex); MyDFS(pGraph,nBegin,pMark);
}
int main()
{ Graph *pGraph = NULL; pGraph = CreateGraph(); DFS(pGraph,5); return 0;
}
查看5道真题和解析
