图的遍历

实验5 图的遍历问题

邻接表实现

  1 #include <stdio.h>
  2 #define MaxVertexNum 100
  3 #define QueueSize 30
  4 #include<iostream>
  5 using namespace std;
  6 typedef enum{ FALSE, TRUE }Boolean;
  7 Boolean visited[MaxVertexNum];
  8 typedef char VertexType;
  9 typedef int EdgeType;
 10 typedef struct node     //边表结点
 11 {
 12     int adjvex;         //邻接点域
 13     struct node *next;  //域链
 14     //若是要表示边上的权,则应增加一个数据域
 15 }EdgeNode;
 16 typedef struct vnode    //顶点边结点
 17 {
 18     VertexType vertex;  //顶点域
 19     EdgeNode *firstedge;//边表头指针
 20 }VertexNode;
 21 typedef VertexNode AdjList[MaxVertexNum];   //AdjList是邻接表类型
 22 typedef struct
 23 {
 24     AdjList adjlist;    //邻接表
 25     int n, e;           //图中当前顶点数和边数
 26 }ALGraph;               //对于简单的应用，无须定义此类型，可直接使用AdjList类型
 27 
 28 void CreateGraphAL(ALGraph *G)
 29 {
 30     int i, j, k,c;
 31     char a,b,first;
 32     EdgeNode * s;
 33     cout<<"请输入顶点数和边数(输入格式为:顶点数,边数)：
";
 34     cin>>(G->n)>>(G->e);       // 读入顶点数和边数
 35     cout<<"输入"<<G->n<<"个顶点"<<endl;
 36     for (i = 0; i < G->n; i++)              // 立有n个顶点的顶点表
 37     {
 38         cout<<"输入顶点"<<i<<":";
 39         cin>>a;
 40         G->adjlist[i].vertex=a; // 读入顶点信息
 41         G->adjlist[i].firstedge = NULL;            // 点的边表头指针设为空
 42     }
 43     first=G->adjlist[0].vertex;
 44     cout<<"first"<<first<<endl;
 45 
 46     for (k = 0; k < G->e; k++)      // 建立边表
 47     {
 48         // 读入边<Vi,Vj>的顶点对应序号
 49         cout<<"输入弧"<<k<<":";
 50         cin>>a>>b>>c;
 51         s = new EdgeNode;         // 生成新边表结点s
 52         i=a-first;
 53         j=b-first;
 54       //  printf("%d  %d  
",i,j);
 55         s->adjvex = j;         // 邻接点序号为j
 56         s->next = G->adjlist[i].firstedge; // 将新边表结点s插入到顶点Vi的边表头部
 57         G->adjlist[i].firstedge = s;
 58 
 59     }
 60 
 61 }
 62 
 63 void DFS(ALGraph *G, int i)
 64 {
 65     //以vi为出发点对邻接表表示的图G进行深度优先搜索
 66     EdgeNode *p;
 67     cout<<G->adjlist[i].vertex;
 68     visited[i] = TRUE;              //标记vi已访问
 69     p = G->adjlist[i].firstedge;        //取vi边表的头指针
 70     while (p)
 71     {                               //依次搜索vi的邻接点vj，这里j=p->adjvex
 72         if (!visited[p->adjvex])    //若vi尚未被访问
 73             DFS(G, p->adjvex);      //则以Vj为出发点向纵深搜索
 74         p = p->next;                     //找vi的下一邻接点
 75     }
 76 }
 77 void DFSTraverseM(ALGraph *G)
 78 {
 79     int i;
 80     for (i = 0; i < G->n; i++)
 81         visited[i] = FALSE;
 82     for (i = 0; i < G->n; i++)
 83         if (!visited[i])
 84             DFS(G, i);
 85 }
 86 typedef struct
 87 {
 88     int front;
 89     int rear;
 90     int count;
 91     int data[QueueSize];
 92 }CirQueue;
 93 void InitQueue(CirQueue *Q)
 94 {
 95     Q->front = Q->rear = 0;
 96     Q->count = 0;
 97 }
 98 int QueueEmpty(CirQueue *Q)
 99 {
100     return Q->count == 0;
101 }
102 int QueueFull(CirQueue *Q)
103 {
104     return Q->count == QueueSize;
105 }
106 void EnQueue(CirQueue *Q, int x)
107 {
108     if (QueueFull(Q))
109         cout<<"Queue overflow"<<endl;
110     else
111     {
112         Q->count++;
113         Q->data[Q->rear] = x;
114         Q->rear = (Q->rear + 1) % QueueSize;
115     }
116 }
117 int DeQueue(CirQueue *Q)
118 {
119     int temp;
120     if (QueueEmpty(Q))
121     {
122         cout<<"Queue underflow"<<endl;
123         return NULL;
124     }
125     else
126     {
127         temp = Q->data[Q->front];
128         Q->count--;
129         Q->front = (Q->front + 1) % QueueSize;
130         return temp;
131     }
132 }
133 void BFS(ALGraph*G, int k)
134 {   // 以vk为源点对用邻接表表示的图G进行广度优先搜索
135     int i;
136     CirQueue Q;             //须将队列定义中DataType改为int
137     EdgeNode *p;
138     InitQueue(&Q);          //队列初始化
139     cout<<G->adjlist[k].vertex;      //访问源点vk
140     visited[k] = TRUE;
141     EnQueue(&Q, k);         //vk已访问，将其人队。（实际上是将其序号人队）
142     while (!QueueEmpty(&Q))
143     {                                   //队非空则执行
144         i = DeQueue(&Q);                    //相当于vi出队
145         p = G->adjlist[i].firstedge;        //取vi的边表头指针
146         while (p)
147         {                               //依次搜索vi的邻接点vj(令p->adjvex=j)
148             if (!visited[p->adjvex])
149             {                           //若vj未访问过
150               //  printf("visit vertex:%c
", G->adjlist[p->adjvex].vertex);      //访问vj
151                 cout<<G->adjlist[p->adjvex].vertex;
152                 visited[p->adjvex] = TRUE;
153                 EnQueue(&Q, p->adjvex); //访问过的vj人队
154             }
155             p = p->next;                    //找vi的下一邻接点
156         }
157     }
158 }
159 void BFSTraverseM(ALGraph *G)
160 {
161     int i;
162     for (i = 0; i < G->n; i++)
163         visited[i] = FALSE;
164     for (i = 0; i < G->n; i++)
165         if (!visited[i])
166             BFS(G, i);
167 }
168 
169 void PrintfGraphAL(ALGraph *G)
170 {
171     for (int i = 0; i < G->n; i++)
172     {
173         cout<<"vertex"<<G->adjlist[i].vertex;
174         EdgeNode *p = G->adjlist[i].firstedge;
175         while (p)
176         {
177             cout<<"→"<<p->adjvex;
178             p = p->next;
179         }
180         cout<<endl;
181     }
182 }
183 
184 void DeleteGraphAL(ALGraph *G)
185 {
186     for (int i = 0; i < G->n; i++)
187     {
188         EdgeNode *q;
189         EdgeNode *p = G->adjlist[i].firstedge;
190         while (p)
191         {
192             q = p;
193             p = p->next;
194             delete q;
195         }
196         G->adjlist[i].firstedge = NULL;
197     }
198 }
199 int main()
200 {
201 
202     ALGraph G;
203     CreateGraphAL(&G);
204     cout<<"深度优先遍历：
";
205     DFSTraverseM(&G);
206     cout<<endl;
207     cout<<"广度优先遍历：
";
208     BFSTraverseM(&G);
209  //   PrintfGraphAL(&G);
210     DeleteGraphAL(&G);
211 
212     return 0;
213 }

View Code

邻接矩阵实现

  1 #include <stdio.h>
  2 #include<iostream>
  3 
  4 typedef enum{ FALSE, TRUE }Boolean;
  5 #define maxSize 20
  6 Boolean visited[maxSize];
  7 using namespace std;
  8 struct g
  9 {
 10     int w[maxSize][maxSize];
 11     int n,e;
 12     char first;
 13     char vertex[maxSize];
 14 };
 15 g graph;
 16 void creatgraph()
 17 {
 18 
 19     int i,j,w;
 20     char a,b;
 21 
 22     cout<<"输入顶点数和弧数："<<endl;
 23     cin>>graph.n>>graph.e;
 24     for(i=0;i<graph.n;i++)
 25     {
 26         cout<<"输入顶点"<<i<<":";
 27         cin>>a;
 28         graph.vertex[i]=a;
 29     }
 30    graph.first=graph.vertex[0];
 31     cout<<"输入"<<graph.e<<"条弧"<<endl;
 32     for(i=0;i<graph.e;i++)
 33     {
 34         cout<<"输入弧"<<i<<":";
 35         cin>>a>>b>>w;
 36         graph.w[a-graph.first][b-graph.first]=w;
 37     }
 38     cout<<"----图----"<<endl;
 39     for(i=0;i<graph.n;i++)
 40     {
 41         for(j=0;j<graph.n;j++)
 42         cout<<graph.w[i][j];
 43         cout<<endl;
 44     }
 45 
 46 
 47 }
 48 void DFS(g graph,int i)
 49 {
 50     int j;
 51     cout<<graph.vertex[i];
 52     visited[i]=TRUE;
 53     for(j=0;j<graph.n;j++)
 54         if(graph.w[i][j]==1 && visited[j]!=1)
 55             DFS(graph,j);
 56 }
 57 void DFST()
 58 {
 59     int i;
 60     for(i=0;i<graph.n;i++)
 61         visited[i]=FALSE;
 62     for(i=0;i<graph.n;i++)
 63         if(!visited[i])
 64             DFS(graph,i);
 65 }
 66 void clearg(int j)
 67 {
 68     for(int i=0;i<graph.n;i++)
 69         graph.w[i][j]=0;
 70 }
 71 char change(int x)
 72 {
 73     for(char c='a';c<='z';c++)
 74     {
 75         if(c-x==0)
 76             return c;
 77     }
 78 }
 79 
 80 void BFST()
 81 {
 82     int i,j;bool flag=0;
 83     for (i = 0; i < graph.n; i++)
 84     {
 85 
 86 
 87         for(int j=0;j<graph.n;j++)
 88         if(graph.w[i][j])
 89         {cout<<change(i+graph.first);flag=1;break;}
 90         if(flag)
 91         break;
 92     }
 93     for(i=0;i<graph.n;i++)
 94             for(int j=0;j<graph.n;j++)
 95                 if(graph.w[i][j])
 96     {cout<<change(j+graph.first);clearg(j);}
 97 }
 98 int main()
 99 {
100     creatgraph();
101     cout<<"深度优先："<<endl;
102     DFST();
103     cout<<endl;
104     cout<<"广度优先："<<endl;
105     BFST();
106     cout<<endl;
107     return 0;
108 }

View Code

矩阵实现的BFS部分我偷懒了，我为了应付实验验收，没有用队列，而且搜索之后数组全被我清零。这样是有bug的。建议用visited数组来标记是否被访问。