计算机应用 | 古代文学 | 市场营销 | 生命科学 | 交通物流 | 财务管理 | 历史学 | 毕业 | 哲学 | 政治 | 财税 | 经济 | 金融 | 审计 | 法学 | 护理学 | 国际经济与贸易
计算机软件 | 新闻传播 | 电子商务 | 土木工程 | 临床医学 | 旅游管理 | 建筑学 | 文学 | 化学 | 数学 | 物理 | 地理 | 理工 | 生命 | 文化 | 企业管理 | 电子信息工程
计算机网络 | 语言文学 | 信息安全 | 工程力学 | 工商管理 | 经济管理 | 计算机 | 机电 | 材料 | 医学 | 药学 | 会计 | 硕士 | 法律 | MBA
现当代文学 | 英美文学 | 通讯工程 | 网络工程 | 行政管理 | 公共管理 | 自动化 | 艺术 | 音乐 | 舞蹈 | 美术 | 本科 | 教育 | 英语 |

通过图的邻接矩阵实现图的搜索实现(一)-通信工(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 *
;            //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的顶点入队

(科教作文网http://zw.ΝsΕac.cOM编辑)

  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 
 

上一篇:DDS的杂散对比与级联方案的研究(一)-通信工程毕 下一篇:研究通讯卫星上的开关设置问题(一)-通信工程毕