各种基本算法实现小结（四）—

各种基本算法实现小结（四）—— 图及其遍历

 　　
  1 // graph.cpp : 定义控制台应用程序的入口点。
  2 //邻接矩阵表示
  3 #include "stdafx.h"
  4 #include <malloc.h>
  5 #define INFINITY 32767
  6 #define MAX_VEX 20
  7 #define QUEUE_SIZE 20
  8 bool *visited;                                                 //用来判断是否遍历过,为true则遍历过,为false,则未遍历过
  9 
 10 typedef struct{        
 11     char* vexs;                                                //顶点向量(包含的顶点a,b,c,d ...)
 12     int arcs[MAX_VEX][MAX_VEX];                                //邻接矩阵
 13     int vexnum,arcnum;                                         //图的顶点数和弧数
 14 }Graph;
 15 
 16 class Queue{
 17 public:
 18     Queue(){};
 19     virtual ~Queue(){
 20         delete this->base;
 21     }
 22     int* base;
 23     int front;
 24     int rear;
 25 
 26 public:
 27     void InitQueue(){
 28         base=(int *)malloc(QUEUE_SIZE*sizeof(int));
 29         front=rear=0;
 30     }
 31     void EnQueue(int e){
 32         base[rear]=e;
 33         rear=((rear+1) % QUEUE_SIZE);
 34     }
 35     void DeQueue(int &e){
 36         e=base[front];
 37         front=(front+1)%QUEUE_SIZE;
 38     }
 39 };
 40 
 41 
 42 int Locate(Graph G,char c){
 43     for(int i=0;i<G.vexnum;i++)
 44         if(G.vexs[i] == c)
 45             return i;
 46     return -1;
 47 }
 48 
 49 void CreateUDN(Graph &G){
 50     int i,j,w,s1,s2;
 51     char a,b,temp;
 52     printf("输入顶点数和弧数:");
 53     scanf_s("%d%d",&G.vexnum,&G.arcnum);
 54     temp=getchar();                                            //接收回车
 55     G.vexs=(char*)malloc(G.vexnum*sizeof(char));
 56     printf("输入%d个顶点.
",G.vexnum);
 57     for(i=0;i<G.vexnum;i++){
 58         printf("输入顶点%d:",i);
 59         scanf_s("%c",&G.vexs[i]);
 60         temp=getchar();
 61     }
 62     for(i=0;i<G.vexnum;i++)                                    //初始化邻接矩阵
 63         for(j=0;j<G.vexnum;j++)
 64             G.arcs[i][j]=INFINITY;
 65 
 66     printf("输入%d条弧.
",G.arcnum);
 67     
 68     for(i=0;i<G.arcnum;i++){
 69         printf("输入弧%d:",i);
 70         scanf_s("%c %c %d",&a,1,&b,1,&w);
 71         temp=getchar();
 72         s1=Locate(G,a);
 73         s2=Locate(G,b);
 74         G.arcs[s1][s2]=G.arcs[s2][s1]=w;
 75     }
 76 }
 77 
 78 //获取图G中顶点K的第一个邻接顶点
 79 int FirstVex(Graph G,int k){
 80     if(k>=0 && k<G.vexnum)            //k合理
 81         for(int i=0;i<G.vexnum;i++)
 82             if(G.arcs[k][i]!=INFINITY)
 83                 return i;
 84     return -1;
 85 }
 86 
 87 //获取图G中以i为顶点的第j个邻接顶点的下一个邻接顶点
 88 int NextVex(Graph G,int i,int j){
 89     if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum)
 90         for(int k=j+1;k<G.vexnum;k++)
 91             if(G.arcs[i][k]!=INFINITY)
 92                 return k;
 93     return -1;                                                //如果遍历完还没有返回k的就返回-1;
 94 }
 95 
 96 void DFS(Graph G,int k){
 97     int i;
 98     if(k == -1){                                            //第一次执行DFS时,k为-1
 99         for(i=0;i<G.vexnum;i++)
100             if(!visited[i])
101                 DFS(G,i);                                    //对尚未访问的顶点调用DFS
102     }
103     else{
104         visited[k] = true;
105         printf("%c ",G.vexs[k]);                            //访问第k个顶点
106         for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))            
107             if(!visited[i])                                    //对k的尚未访问的邻接顶点i递归调用DFS
108                 DFS(G,i);        
109     }
110 }
111 
112 void BFS(Graph G){
113     int k,w;
114     Queue Q;                                                //辅助队列Q
115     Q.InitQueue();
116     for(int i=0;i<G.vexnum;i++)
117         if(!visited[i]){
118             visited[i]=true;
119             printf("%c ",G.vexs[i]);
120             Q.EnQueue(i);
121             while(Q.front!=Q.rear){
122                 Q.DeQueue(k);
123                 for(w=FirstVex(G,k);w>=0;w=NextVex(G,k,w)){
124                     if(!visited[w]){
125                         visited[w]=true;
126                         printf("%c ",G.vexs[w]);
127                         Q.EnQueue(w);
128                     }
129                 }
130             }
131         }
132 }
133 
134 int _tmain(int argc, _TCHAR* argv[])
135 {
136     int i;
137     Graph G;
138     CreateUDN(G);
139     visited=(bool*)malloc(G.vexnum*sizeof(bool));
140     
141     printf("
深度优先遍历:");
142     for(i=0;i<G.vexnum;i++)
143         visited[i]=false;
144     DFS(G,-1);
145     
146     printf("
广度优先遍历
");
147     for(i=0;i<G.vexnum;i++)
148         visited[i]=false;
149     
150     BFS(G);
151     free(G.vexs);
152     printf("
程序结束
");
153     return 0;
154 }
测试环境： VS 2010
运行结果：
本文参考自：~~~