用C语言实现有向图的邻接矩阵构建与遍历方法

  1 /*C语言建立有向图的邻接矩阵及其遍历操作*/
  2 #include"stdio.h"
  3 #include"stdlib.h"
  4 //图的邻接矩阵储存结构
  5 typedef char elemtype;
  6 #define maxsize 10
  7 #define queuesize 100  
  8 typedef struct{
  9     elemtype vex[maxsize];//顶点表
 10     int arc[maxsize][maxsize];//邻接矩阵
 11     int n,e;//边数，顶点数
 12 }graph;
 13 //在图中查找顶点v,存在返回其在顶点数组中的下标，不存在返回-1
 14 int locatevex(graph g,elemtype v)
 15 {
 16     int i;
 17     for(i=0;i<g.n;i++)if(g.vex[i]==v)return i;
 18     return -1;
 19 }
 20 //打印信息
 21 void print(graph g)
 22 {
 23     int i,j;
 24     printf("图的邻接矩阵表示：\n");
 25     for(i=0;i<g.n;i++){
 26         for(j=0;j<g.n;j++){
 27             printf("%3d",g.arc[i][j]);
 28         }
 29         printf("\n");
 30     }
 31 }
 32 //创建有向图的邻接矩阵
 33 void creategraph(graph *g){
 34     int i,j,k;
 35     elemtype v1,v2;
 36     printf("请输入顶点数和边数：\n");
 37     printf("顶点数n=");scanf("%d",&g->n);
 38     printf("边  数e=");scanf("%d",&g->e);
 39     printf("请输入图的顶点信息：\n");
 40     getchar();
 41     for(i=0;i<=g->n;i++)
 42     scanf("%c",&g->vex[i]);
 43     for(i=0;i<g->n;i++)
 44         for(j=0;j<g->n;j++)
 45             g->arc[i][j]=0;//初始化邻接矩阵
 46     printf("请输入图的边的信息：\n");
 47     for(k=0;k<g->e;k++)
 48     {
 49         printf("请输入第%d条边的两个端点：",k+1);
 50         scanf("%c%c",&v1,&v2);
 51         fflush(stdin);//清空输入缓冲区
 52         i=locatevex(*g,v1);j=locatevex(*g,v2);
 53         if(i>=0&&j>=0){
 54         g->arc[i][j]=1;
 55         g->arc[j][i]=1;//无向网矩阵对称
 56         }
 57     }
 58 }
 59 int DFSvisited[maxsize];/* 访问标志数组*/
 60  /*从第i个顶点出发递归地深度优先遍历图G*/
 61 void DFS(graph g,int i)
 62 {
 63     int j;
 64     printf("%3c",g.vex[i]); /*访问第i个项点*/
 65     DFSvisited[i]=1;
 66     for(j=0;j<g.n;j++)
 67     {
 68         if((g.arc[i][j]==1)&&(DFSvisited[j]==0))
 69             DFS(g,j);/* //对i的尚未访问的邻接顶点j递归调用DFS */
 70     }
 71 }
 72 //对图g进行深度优先遍历
 73 void DFStraverse(graph g) 
 74 {
 75     int v;
 76     for (v=0; v<g.n;v++)DFSvisited[v]=0; /*初始化标志数组*/
 77     for  (v=0; v<g.n;v++) /*保证非连通图的遍历,连通图只执行一次*/
 78 /*从第v个顶点出发递归地深度优先遍历图G*/
 79         if (!DFSvisited[v]) DFS(g,v);        
 80 }
 81 //循环队列存储结构定义
 82 typedef struct  cirqueue
 83 {
 84     elemtype  *data;      //队列存储空间的首地址
 85     int front;         //队头位置：指向当前队头元素
 86     int rear;    //队尾位置：指向当前队尾元素的下一位置
 87 }cirqueue;             // 循环队列
 88 //构造空队，如果成功，返回1，如果失败，返回0
 89 int initqueue(cirqueue *q)
 90 {
 91     q->data=(elemtype *)malloc(queuesize*sizeof(cirqueue));
 92     if (q->data==NULL)return 0; // 存储分配失败 
 93     q->front=q->rear=0;    
 94     return 1;
 95  }
 96 // 插入元素e为Q的新的队尾元素 ,如果成功，返回1，如果失败，返回0
 97 int enqueue (cirqueue *q,elemtype e)
 98 { 
 99     if ((q->rear+1) % queuesize == q->front) 
100         return 0; //队列满
101     q->data[q->rear] = e;
102     q->rear = (q->rear+1) % queuesize; //队尾后移一位
103     return 1;
104 }
105 //若队列不空，则删除Q的队头元素，用e返回其值,并返回1；否则返回0
106 int dequeue (cirqueue *q,int *e) 
107 {
108     if (q->front == q->rear)  return 0; //队列为空
109     *e = q->data[q->front];
110     q->front = (q->front+1) %queuesize; //队头后移一位
111     return 1;
112 }
113 //若栈不空，则用e返回队头元素,并返回1；否则返回0
114 int getfront(cirqueue q,elemtype *e)
115 {
116     if (q.front == q.rear)  return 0; //队列为空
117     *e=q.data[q.front];
118     return  1;
119  }
120 //若队列为空栈，则返回1，否则返回0 
121 int queueempty(cirqueue q)//栈非空
122 { 
123     if(q.front == q.rear)return 1; //队列为空
124     else return 0;
125 }
126 //返回队列的元素个数，即队列的长度
127 int queuelength(cirqueue q)
128 { 
129     return (q.rear-q.front+queuesize) % queuesize;
130 }
131 //【算法6-10：利用邻接矩阵实现连通图的广度优先搜索遍历】
132 int BFSvisited[maxsize];
133 cirqueue q;
134 /*从第k个顶点出发广度优先遍历图G,G以邻接矩阵表示。*/
135 void BFS(graph g,int i){
136     int j;    
137     initqueue(&q);/*初始化队列*/
138     printf("%3c",g.vex[i]);/*访问第k个顶点*/
139     BFSvisited[i]=1;
140     enqueue(&q,i);/*第k个顶点进队*/
141     while(queueempty(q)==0) {/*队列非空*/
142         dequeue(&q,&i);
143         for(j=0;j<g.n;j++){
144            if((g.arc[i][j]==1)&&(BFSvisited[j]==0)){
145 /*访问第i个顶点的末曾访问的顶点j*/
146                 printf("%3c",g.vex[j]);
147                 BFSvisited[j]=1;
148                 enqueue(&q,j);/*第k个顶点进队*/
149             }
150         }
151     }
152 }
153 //【算法6-11：对图G进行广度优先遍历】
154 void BFStraverse(graph  g) //对图G进行广度优先遍历
155 {
156     int v;
157     for (v=0; v<g.n;v++) //初始化标志数组
158         BFSvisited[v]=0; 
159     for  (v=0; v<g.n;v++) //保证非连通图的遍历
160         if (!BFSvisited[v])BFS(g,v); 
161        //从第v个顶点出发递归地广度优先遍历图G
162 }
163 int main()
164 {
165     graph g;
166     creategraph(&g);
167     print(g);
168     printf("\n");
169     printf("图的深度优先遍历序列：\n");
170     DFStraverse(g);
171     printf("\n");
172     printf("图的广度优先遍历序列：\n");
173     BFStraverse(g);
174     printf("\n");
175     return 0;
176 }