C语言实现广度/深度优先算法

首先打开VC++6.0

选择文件，新建

选择C++ source file 新建一个空白文档

首先声明头文件和一些常量#include #include #define MAX_VEXTEX_NUM 9 /* 图中顶点数 */#define ARC_NUM 12       /* 图中弧数 */#define MAX_QUEUEMEM (MAX_VEXTEX_NUM+1)

定义数组，因为是排序，必须有数据/* 定义描述图的顶点之间连接信息的数组 */int GraphEdge[ARC_NUM * 2][2] = {{0,1},{1,0},{1,2},{2,1},{2,3},{3,2},{3,4},{4,3},{4,5},{5,4},{5,0},{0,5},{0,6},{6,0},{6,8},{8,6},{6,7},{7,6},{7,8},{8,7},{7,3},{3,7},{8,4},{4,8}};/*定义数组visited用来标示一个顶点是否被访问过*/int visited[MAX_VEXTEX_NUM]={0,0,0,0,0,0,0,0,0};/*定义表结点，即每条弧对应的结点 */

定义三个结构体，分别是指针，顶点信息，图的结构typedef struct ArcNode{  int adjvex;                 /* 该弧所指向的顶点的位置 */  struct ArcNode * nextarc;   /* 指向下一条弧的指针 */}ArcNode; /* 定义头结点 */typedef struct VNode{  int data;                    /* 顶点信息 */  struct ArcNode * firstarc;   /* 指向第一条依附该顶点的弧的指针 */}VNode,AdjList[MAX_VEXTEX_NUM];  /* 定义图的结构 */typedef struct {VNode vertices[MAX_VEXTEX_NUM];/* 定义表头数组 */int vexnum;      /* 定义图中顶点数 */int arcnum;      /* 定义图中弧数 */}ALGraph;

现在要建立一个使用邻接表存储的图void CreateGraph(ALGraph * alGraph){int i,j;ArcNode * newnode;ArcNode * vexNode;alGraph->vexnum = MAX_VEXTEX_NUM;alGraph->arcnum = ARC_NUM;/* 初始化表头 */for(i=0;ivertices[i].data = i;alGraph->vertices[i].firstarc = NULL;}for(j=0;j<2*ARC_NUM;j++){i = GraphEdge[j][0];if(alGraph->vertices[i].firstarc==NULL){  newnode = ( ArcNode * ) malloc (sizeof(ArcNode));  newnode->adjvex = GraphEdge[j][1];  newnode->nextarc = NULL;  alGraph->vertices[i].firstarc = newnode;}else{  vexNode = alGraph->vertices[i].firstarc;  while(vexNode->nextarc != NULL)  {vexNode = vexNode->nextarc;  }  newnode = ( ArcNode * ) malloc (sizeof(ArcNode));  newnode->adjvex = GraphEdge[j][1];  newnode->nextarc = NULL;  vexNode->nextarc = newnode;}}}

输出次图的函数 void OutputGraph(ALGraph * alGraph){int i;ArcNode * vexNode;printf('The graph dedicated by adjacency list is:\n');for(i=0;i ',alGraph->vertices[i].data);vexNode = alGraph->vertices[i].firstarc;while(vexNode != NULL){  printf('[%d] -> ',vexNode->adjvex);  vexNode=vexNode->nextarc;}printf('[END]\n');}}

递归实现DFSvoid DFS(ALGraph * alGraph,int v){int w;ArcNode * vexNode;visited[v] = 1;printf('[%d] -> ',v);vexNode = alGraph->vertices[v].firstarc;while(vexNode != NULL){w = vexNode->adjvex;if(visited[w]==0)  DFS(alGraph,w);vexNode = vexNode->nextarc;}}

图的深度优先遍历 void DFSTraverse(ALGraph * alGraph){int i;/*访问标志数组初始化*/for(i=0;i

为了实现广度优先遍历，需要借助一个队列 typedef struct{  int queuemem[MAX_QUEUEMEM];  int header;  int rear;}QUEUE;void InitQueue(QUEUE *queue){queue->header = 0;queue->rear = 0;}void EnQueue(QUEUE *queue,int v){queue->queuemem[queue->rear] = v;queue->rear++;}int DelQueue(QUEUE *queue){    return queue->queuemem[queue->header++];}int EmptyQueue(QUEUE *queue){   if(queue->header == queue->rear)     return 1;   return 0;}

广度优先遍历 void BFSTraverse(ALGraph * alGraph){int i;int w;ArcNode * vexNode;QUEUE queue;InitQueue(&queue);/*访问标志数组初始化*/for(i=0;i ',i);        EnQueue(&queue,i);        while(!EmptyQueue(&queue))        {          w = DelQueue(&queue);          vexNode = alGraph->vertices[w].firstarc;          while(vexNode != NULL)          {        w = vexNode->adjvex;        if(visited[w]==0)        {          visited[w] = 1;              printf('[%d] -> ',w);          EnQueue(&queue,w);        }        vexNode = vexNode->nextarc;          }        }}}printf('[end]\n'); }

一大堆的函数，主函数就几句话。。int main(){/*定义图结点*/    ALGraph alGraph;        /*建立图的邻接表*/    CreateGraph(&alGraph);    /*输出图的邻接表*/    OutputGraph(&alGraph);    /*深度优先遍历*/    DFSTraverse(&alGraph);    /*广度优先遍历*/    BFSTraverse(&alGraph);    getch();    return 0;}

执行结果