存档：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #define maxv 10 4 #define max 10 5 typedef char elem; 6 typedef int elemtype; 7 #include "queue.h" 8 #include "mgraph.h" 9 void main() 10 { 11 mgraph g; 12 printf("1.初始化函数测试:\n"); 13 initial(g); 14 printf("2.创建函数测试:\n"); 15 create(g); 16 printf("3.输出函数测试:\n"); 17 printg(g); 18 printf("4.输出顶点度函数测试:\n"); 19 degree(g); 20 printf("5.深度优先遍历函数测试:\n"); 21 dfstraverse(g); 22 printf("6.广度优先遍历函数测试:\n"); 23 bfs(g); 24 }
1 //有向图的邻接矩阵,顶点数据为字符型 2 typedef struct MGraph 3 { 4 elem vexes[maxv];//顶点表 5 int edges[maxv][maxv];//邻接矩阵 6 int n,e;//顶点数n和边数e 7 }mgraph; 8 bool visited[maxv];//访问标志数组 9 void initial(mgraph &g)//初始化函数 10 { 11 int i,j; 12 g.e=0; 13 g.n=0; 14 for(j=0;j<maxv;j++) 15 g.vexes[j]=0;//建立顶点表 16 for(i=0;i<maxv;i++) 17 { 18 for(j=0;j<maxv;j++) 19 { 20 g.edges[i][j]=0;//初始化邻接矩阵 21 } 22 } 23 } 24 int locate(mgraph g,elem u)//查找顶点对应的数组下标值 25 { 26 for(int i=0;i<g.n;i++) 27 { 28 if(g.vexes[i]==u) 29 return i; 30 } 31 return -1; 32 } 33 void create(mgraph &g)//创建图的邻接矩阵存储 34 { 35 int i,j,k; 36 elem u,v; 37 printf("请输入有向图的顶点数:"); 38 scanf("%d",&g.n); 39 printf("请输入有向图的弧数:"); 40 scanf("%d",&g.e); 41 fflush(stdin);//清空缓存中的数据 42 printf("请输入字符型顶点数据,如ABCD:"); 43 for(j=0;j<g.n;j++) 44 scanf("%c",&g.vexes[j]);//建立顶点表 45 fflush(stdin); 46 printf("请输入弧的信息,格式:弧尾,弧头\n"); 47 for(k=0;k<g.e;k++) 48 { 49 scanf("%c,%c",&u,&v); 50 i=locate(g,u); 51 j=locate(g,v); 52 g.edges[i][j]=1; 53 fflush(stdin); 54 } 55 } 56 void printg(mgraph g)//输出有向图的邻接矩阵 57 { 58 int i,j; 59 printf("输入图的邻接矩阵存储信息:\n"); 60 printf("顶点数据:\n"); 61 for(i=0;i<g.n;i++) 62 printf("%d:%c\n",i,g.vexes[i]); 63 printf("邻接矩阵数据:\n"); 64 for(i=0;i<g.n;i++) 65 { 66 for(j=0;j<g.n;j++) 67 { 68 printf("%3d",g.edges[i][j]); 69 } 70 printf("\n"); 71 } 72 } 73 void degree(mgraph g)//输出顶点的度 74 { 75 int i,j,in,out; 76 for(i=0;i<g.n;i++) 77 { 78 in=0; 79 out=0; 80 for(j=0;j<g.n;j++) 81 { 82 if(g.edges[i][j]!=0) 83 out++; 84 if(g.edges[j][i]!=0) 85 in++; 86 } 87 printf("顶点%c的出度为%d---入度为%d---度为%d\n",g.vexes[i],out,in,in+out); 88 } 89 } 90 int firstadjvex(mgraph g,int v)//顶点v的第一个邻接顶点 91 { 92 for(int i=0;i<g.n;i++) 93 { 94 if(g.edges[v][i]==1) 95 return i; 96 } 97 return -1; 98 } 99 int nextadjvex(mgraph g,int v,int w)//顶点v的相对于w的下一个邻接顶点 100 { 101 for(int i=w+1;i<g.n;i++) 102 { 103 if(g.edges[v][i]==1) 104 return i; 105 } 106 return -1; 107 } 108 void dfs(mgraph g,int v)//遍历一个连通分量 109 { 110 int w; 111 visited[v]=true; 112 printf("%c ",g.vexes[v]); 113 for(w=firstadjvex(g,v);w>=0;w=nextadjvex(g,v,w)) 114 { 115 if(!visited[w]) 116 dfs(g,w); 117 } 118 } 119 void dfstraverse(mgraph g)//深度优先遍历 120 { 121 int v; 122 for(v=0;v<g.n;v++) 123 visited[v]=false;//标志访问数组初始化 124 for(v=0;v<g.n;v++) 125 { 126 if(!visited[v]) 127 dfs(g,v); 128 } 129 } 130 void bfs(mgraph g)//广度优先遍历 131 { 132 int u=0,v=0,w=0; 133 queue q; 134 for(v=0;v<g.n;v++) 135 visited[v]=false; 136 initqueue(q); 137 for(v=0;v<g.n;v++) 138 { 139 if(!visited[v]) 140 { 141 visited[v]=true; 142 printf("%c ",g.vexes[v]); 143 enqueue(q,v); 144 while(!queueempty(q)) 145 { 146 dequeue(q,u); 147 for(w=firstadjvex(g,u);w>=0;w=nextadjvex(g,u,w)) 148 { 149 if(!visited[w]) 150 { 151 visited[w]=true; 152 printf("%c ",g.vexes[w]); 153 enqueue(q,w); 154 } 155 } 156 } 157 } 158 } 159 destroyqueue(q); 160 }
1 typedef struct 2 { 3 elemtype *base;//动态分配存储空间 4 int front;//头指针,若队列不空指向队列头元素 5 int rear;//尾指针,若队列不空指向队列尾元素的下一个位置 6 }queue; 7 void initqueue(queue &q)//初始化队列 8 { 9 q.base=new elemtype[max];//分配存储空间 10 if(!q.base) 11 { 12 printf("队列分配失败\n"); 13 exit(-2); 14 } 15 else 16 q.front=q.rear=0; 17 } 18 int queueempty(queue q)//判断队列是否为空 19 { 20 if(q.front==q.rear) 21 return 1; 22 else 23 return 0; 24 } 25 void enqueue(queue &q,elemtype e)//入队列操作 26 { 27 if((q.rear+1)%max==q.front) 28 { 29 printf("队满,无法插入新元素!\n"); 30 exit(-2); 31 } 32 else 33 { 34 q.base[q.rear]=e; 35 q.rear=(q.rear+1)%max; 36 } 37 } 38 void dequeue(queue &q,elemtype e)//出队列操作 39 { 40 if(q.front==q.rear)//判断队列是否为空 41 { 42 printf("空队列,无法删除头元素!\n"); 43 exit(-2); 44 } 45 else 46 { 47 e=q.base[q.front]; 48 q.front=(q.front+1)%max; 49 } 50 } 51 void destroyqueue(queue &q)//销毁队列 52 { 53 free(q.base); 54 q.base=NULL; 55 q.front=0; 56 q.rear=0; 57 printf("\n"); 58 }
运行结果如下：
