| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 433 人关注过本帖
标题:红字部分
只看楼主 加入收藏
chan320799
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2011-11-17
收藏
 问题点数:0 回复次数:0 
红字部分
a#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100     //定义最大顶点数
typedef struct{
    char vexs[MaxVertexNum];        //顶点表
    int edges[MaxVertexNum][MaxVertexNum];   //邻接矩阵,可看作边表
    int n,e;          //图中的顶点数n和边数e
}MGraph;              //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
     int i,j,k;
     char a;
     printf("Input VertexNum(n) and EdgesNum(e): ");
     scanf("%d,%d",&G->n,&G->e);         //输入顶点数和边数
     scanf("%c",&a);            
     printf("Input Vertex string:");
     for(i=0;i<G->n;i++)   
     {
     scanf("%c",&a);
     G->vexs[i]=a;             //读入顶点信息,建立顶点表
     }
     for(i=0;i<G->n;i++)
        for(j=0;j<G->n;j++)
                G->edges[i][j]=0;    //初始化邻接矩阵
     printf("Input edges,Creat Adjacency Matrix\n");
     for(k=0;k<G->e;k++) {       //读入e条边,建立邻接矩阵  
     scanf("%d%d",&i,&j);        //输入边(Vi,Vj)的顶点序号
     G->edges[i][j]=1;   
     G->edges[j][i]=1; //若为无向图,矩阵为对称矩阵;若建立有向图,去掉该条语句
     }
}
//=========定义标志向量,为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS:深度优先遍历的递归算法======
void DFSM(MGraph *G,int i)
{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索,邻接矩阵是0,1矩阵
    int j;
    printf("%c",G->vexs[i]);     //访问顶点Vi
    visited[i]=TRUE;             //置已访问标志
    for(j=0;j<G->n;j++)          //依次搜索Vi的邻接点
    if(G->edges[i][j]==1 && ! visited[j])
        DFSM(G,j);              //(Vi,Vj)∈E,且Vj未访问过,故Vj为新出发点
}
void DFS(MGraph *G)
{  
    int i;
    for(i=0;i<G->n;i++)
    visited[i]=FALSE;            //标志向量初始化
    for(i=0;i<G->n;i++)
    if(!visited[i])              //Vi未访问过
        DFSM(G,i);               //以Vi为源点开始DFS搜索
}
//===========BFS:广度优先遍历=======
void BFS(MGraph *G,int k)
{                //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索
    int i,j,f=0,r=0;
    int cq[MaxVertexNum];        //定义队列   
    for(i=0;i<G->n;i++)
    visited[i]=FALSE;             //标志向量初始化
    for(i=0;i<G->n;i++)
    cq[i]=-1;                    //队列初始化
    printf("%c",G->vexs[k]);     //访问源点Vk
    visited[k]=TRUE;
    cq[r]=k;          //Vk已访问,将其入队。注意,实际上是将其序号入队
    while(cq[f]!=-1) {          //队非空则执行
         i=cq[f]; f=f+1;             //Vf出队
         for(j=0;j<G->n;j++)         //依次Vi的邻接点Vj
             if(G->edges[i][j]==1 && !visited[j]) {  //Vj未访问
                 printf("%c",G->vexs[j]);         //访问Vj
                 visited[j]=TRUE;                  r=r+1; cq[r]=j;          //访问过Vj入队
             }
    }
}
//==========main=====
void main()
{
    int i;
    MGraph *G;
    G=(MGraph *)malloc(sizeof(MGraph));   //为图G申请内存空间
    CreatMGraph(G);          //建立邻接矩阵
    printf("Print Graph DFS: ");
    DFS(G);                  //深度优先遍历
    printf("\n");
    printf("Print Graph BFS: ");
    BFS(G,3);             //以序号为3的顶点开始广度优先遍历
    printf("\n");
}
搜索更多相关主题的帖子: include 
2011-11-22 11:33
快速回复:红字部分
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016066 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved