评价网 > 科教论文 > 工学毕业论文 > 通信工程论文 > 正文

通过图的邻接矩阵实现图的搜索实现(一)-通信工(4)

2013-06-25 01:21 ;            //w是有向边的权值（建立一般的有向图时，可输入1）
　　　　printf("input i,j,w:\n");
　　　　scanf("%d%d%d",&i,&j,&w);
　　　　g->edges[i][j]=w;
　　　　if (flag)//构造无向图
　　　　　　g->edges[j][i]=w;
　　　}
　}

dfsm(mgraph *g,int i)
　{//对以邻接矩阵表示的图，以序号为i的顶点为出发点进行深度优先搜索
　　int j;
　　printf("visit vertex:%d ",g->vexs[i]);//访问序号为i的顶点
　　visited[i]=TRUE;//将序号为i的顶点设置访问过标记
　　for(j=0;j<g->n;j++)//扫描邻接矩阵的第i行，做以下操作
　　　if ((g->edges[i][j]!=0)&&(!visited[j]))
　　　　　//寻找序号为i的顶点的未访问过的邻接点(设序号为k),
　　　　dfsm(g,j);//以序号为k的顶点为出发点进行深度优先搜索
　}//end of dfsm

dfstraverse(mgraph *g)
　{//对以邻接矩阵表示的图，进行深度优先搜索
　　int i;
　　for(i=0;i<g->n;i++)//将图的所有顶点设置为未访问过
　　　　visited[i]=FALSE;
　　for(i=0;i<g->n;i++)//对图*g进行深度优先搜索
　　　if(!visited[i])
　　　　dfsm(g,i);
　　printf("\n");
　}//end of dfstraverse

bfsm(mgraph *g,int k)
　{//对以邻接矩阵表示的图，以序号为k的顶点作为出发点进行广度优先搜索
　　int i,j;
　　cirqueue *q;
　　q=(cirqueue *)malloc(sizeof(cirqueue));//申请循环队列空间*q
　　q->rear=q->front=q->count;//将循环队列*q设置为空队列
　　printf("visit vertex:%d ",g->vexs[k]);//访问序号为k的顶点
　　visited[k]=TRUE;//将序号为k是结点设置为已访问过
　　q->data[q->rear]=k;q->rear=(q->rear+1)%queuesize;q->count++;//将序号为k的顶点入队

　　while(q->count){//若队列不为空，则做以下操作
　　　　i=q->data[q->front];q->front=(q->front+1)%queuesize;q->count--;
　　　　　//将队首元素(序号为i的顶点)出队
　　for(j=0;j<g->n;j++)//寻找序号为i顶点的邻接点，并做如下处理
　　　if((g->edges[i][j]!=0)&&(!visited[j])){//若序号为i的顶点有未访问过邻接点
　　　　　printf("visit vertex:%d ",g->vexs[j]);//访问序号为j的顶点
　　　　　visited[j]=TRUE;//设置序号为j的顶点访问过标记
　　　　　q->data[q->rear]=j;q->rear=(q->rear+1)%queuesize;q->count++;
　　　　　　//将序号为j的顶点入队
　　　　}//end of if
　　　}//end of for
　}//end of bfsm

bfstraverse(mgraph *g)
　{//对以邻接矩阵表示的图，进行广度优先搜索
　　int i;
　　for(i=0;i<g->n;i++)//将所有顶点设置为未访问过
　　　　visited[i]=FALSE;
　　for(i=0;i<g->n;i++)//对邻接矩阵表示的图进行广度优先搜索
　　　if(!visited[i])
　　　　bfsm(g,i);
　　printf("\n");
　}//end of bfstraverse