算法读书笔记第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;
}