Adjacency-matrix-traversal.zip_遍历矩阵_邻接矩阵

#include <stdio.h> #define maxvertexnum 100//设置邻接矩阵的最大阶数 #define queuesize 100//设置循环队列的最大空间 typedef struct{ int front,rear,count,data[queuesize]; }cirqueue;//循环队列结构定义 typedef int vertextype;//设置图的顶点信息为整型 typedef int edgetype;//设置边上权值为整型 typedef struct{ vertextype vexs[maxvertexnum];//图的顶点信息表 edgetype edges[maxvertexnum][maxvertexnum];//图的邻接矩阵 int n,e;//图的顶点数和边数 }mgraph;//图的邻接矩阵表示结构定义 typedef enum{FALSE,TRUE}boolean; boolean visited[maxvertexnum];//顶点访问标记向量 main()//主函数 {//建立用邻接矩阵表示的图,并进行深度优先搜索和广度优先搜索 int i,j; mgraph *g; g=(mgraph*)malloc(sizeof(mgraph));//申请图g的邻接矩阵表示空间 printf("***********************************\n"); createmgraph(g);//建立图g printf("***********************************\n"); printf("邻接矩阵为：\n"); for(i=0;i<g->n;i++){ for(j=0;j<g->n;j++) printf("%d ",g->edges[i][j]); printf("\n"); } printf("***********************************\n"); printf("深度优先序列是:");//对图g进行深度优先搜索 dfstraverse(g); printf("***********************************\n"); printf("广度优先序列是:");//对图g进行广度优先搜索 bfstraverse(g); printf("***********************************\n"); } void createmgraph(mgraph *g) {//建立图g的邻接矩阵表示 int i,j,k,w; int y=0; int flag; printf("请输入创建图的类型:\n"); printf("有向图--0\n"); printf("无向图--1\n"); printf("***********************************\n"); scanf("%d",&flag); printf("输入定点数和边数 n,e\n"); printf("n="); scanf("%d",&g->n); printf("e="); scanf("%d",&g->e);//输入图*g的顶点数和边数 printf("输入节点信息:\n"); for(i=0;i<g->n;i++){//输入n个顶点的信息 printf("v%d= ",y); y++; scanf("%d",&(g->vexs[i])); } for(i=0;i<g->n;i++)//将邻接矩阵数组初始化 for(j=0;j<g->n;j++) g->edges[i][j]=0; for(k=0;k<g->e;k++){//读入n有向边对应的三元组(i,j,w),若构造有向图, //i为有向边的弧尾,j是有向边的弧头, //w是有向边的权值(建立一般的有向图时,可输入1) printf("请输入 i,j,w:\n"); scanf("%d %d %d",&i,&j,&w); g->edges[i][j]=w; if (flag)//构造无向图 g->edges[j][i]=w; } } void dfsm(mgraph *g,int i) {//对以邻接矩阵表示的图,以序号为i的顶点为出发点进行深度优先搜索 int j; printf("%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 void 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 void 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("%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("%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 void 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