图的存储结构的实现(C/C++实现)详解编程语言

 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 }