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

1、首先打开VC++6.0

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

5、定义数组，因为是排序，必须有数据/* 定义描述图的顶点之间连接信息的数组 */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};/*定义表结点，即每条弧对应的结点 */

7、现在要建立一个使用邻接表存储的图void CreateGraph(ALGraph * alGraph){int i,j;ArcNode * newnode;ArcNode * v髫潋啜缅exNode;alGraph->vexnum = MAX_VEXTEX_NUM;alGraph->arcnum = ARC_NUM;/* 初始化表头 */for(i=0;i<MAX_VEXTEX_NUM;i++){alGraph->vertices[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;}}}

9、递归实现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;}}

11、为了实现广度优先遍历，需要借助一个队列 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;}

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