C语言实现邻接表的完全无向图生成，图的深度优先搜索和广度优先搜索

ALGraph* InitGraph(ALGraph* g, int number)创建了完全无向图

ALGraph* CreatTestGraph(ALGraph *g)创建了测试用有向图

ALGraph* InitGraph(ALGraph* g, int number) 实现了完全无向图的生成

BFS(ALGraph *g)与DFS(ALGraph *g)实现了图的广度与深度优先搜索

g是生产的完全无向图

g2是测试用的有向图,如下所示：

邻接表中： 1 ->2 ->4           2->3             3->6        4->3->5          5->7->8

6->NULL            7->6->9            8->NULL      9->NULL

可知：

BFS:        1 2 4 3 5 6 7 8 9
DFS:        1 2 3 6 4 5 7 9 8

1.  
   #include <stdio.h>
2.  
   #include <stdlib.h>
3.  
   #include <string.h>
4.  
   #define MAXSIZE 30
5.  
   typedef struct ArcNode //边表
6.  
   {
7.  
   int adjvex;
8.  
   struct ArcNode* next;
9.  
   }ArcNode;
10.  
     
11.  
     
12.  
    typedef struct VNode{ //点表
13.  
    int data;
14.  
    ArcNode * first;
15.  
    }VNode;
16.  
     
17.  
    typedef struct ALGraph //邻接表
18.  
    {
19.  
    VNode* vertcies[MAXSIZE];
20.  
    int vexnum,arcnum;
21.  
    }ALGraph;
22.  
     
23.  
    typedef struct Queue //队列及相关操作
24.  
    {
25.  
    VNode *data[MAXSIZE];
26.  
    int rear,front;
27.  
    }Queue;
28.  
     
29.  
    Queue* initQueue(){
30.  
    Queue* p = (Queue *)malloc(sizeof(Queue));
31.  
    p->rear=p->front=0;
32.  
    return p;
33.  
    }
34.  
     
35.  
    int isQueueEmpty(Queue *p){
36.  
    if(p->rear==p->front){
37.  
    return 1;
38.  
    }
39.  
    return -1;
40.  
    }
41.  
     
42.  
    int enQueue(Queue *p,VNode *node){
43.  
    if((p->rear 1)%MAXSIZE==p->front){
44.  
    printf("full error,please enlarge Maxsize\n");
45.  
    return -1;
46.  
    }
47.  
    p->data[p->rear]=node;
48.  
    p->rear=(p->rear 1)%MAXSIZE;
49.  
    return 1;
50.  
    }
51.  
     
52.  
    VNode* deQueue(Queue *p){
53.  
    if(p->rear==p->front){
54.  
    printf("empty error\n");
55.  
    return NULL;
56.  
    }
57.  
    VNode *temp =p->data[p->front];
58.  
    p->front = (p->front 1)%MAXSIZE;
59.  
    return temp;
60.  
     
61.  
    }
62.  
     
63.  
     
64.  
    ALGraph* InitGraph(ALGraph* g, int number){ //生成有number个节点的完全无向图
65.  
    g = (ALGraph*)malloc(sizeof(ALGraph));
66.  
    VNode *tempV;
67.  
    g->vexnum=number,g->arcnum=number*(number-1)/2; //统计结点数和边数
68.  
    for(int i=0;i<number;i ){ //节点初始化
69.  
    tempV = (VNode *)malloc(sizeof(VNode));
70.  
    tempV->data=i 1;
71.  
    g->vertcies[i]=tempV;
72.  
    }
73.  
    int k; //k统计连接的次数，总共连接number-1条边
74.  
    for(int i=0;i<number;i ){
75.  
    k=1;
76.  
    int now = (i k)%(number);
77.  
    ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));
78.  
    p->adjvex =now,p->next=NULL;
79.  
    g->vertcies[i]->first=p; //first初始化
80.  
    k ;
81.  
    while(k<number){
82.  
    ArcNode* tempA;
83.  
    tempA =(ArcNode*)malloc(sizeof(ArcNode));
84.  
    now = (i k)%(number);
85.  
    tempA->adjvex=now;
86.  
    tempA->next=NULL;
87.  
    p->next = tempA; //边表连接
88.  
    p=tempA;
89.  
    k ;
90.  
    }
91.  
    }
92.  
    return g;
93.  
    }
94.  
     
95.  
    void VisitingBFS(ALGraph* g,int *visit,int begin,Queue *p){ //BFS队列实现
96.  
    int num = g->vexnum;
97.  
    printf("%d ",g->vertcies[begin]->data);
98.  
    visit[begin]=1;
99.  
    enQueue(p,g->vertcies[begin]);
100.  
     VNode * tempV;
101.  
     ArcNode * tempA;
102.  
     while (isQueueEmpty(p)!=1)
103.  
     {
104.  
     tempV =deQueue(p);
105.  
     for(tempA=tempV->first;tempA!=NULL;tempA=tempA->next){
106.  
     if(visit[tempA->adjvex]==0){
107.  
     tempV = g->vertcies[tempA->adjvex];
108.  
     printf("%d ",tempV->data);
109.  
     visit[tempA->adjvex]=1;
110.  
     enQueue(p,tempV);
111.  
     }
112.  
     }
113.  
     }
114.  
      
115.  
     }
116.  
      
117.  
     void BFS(ALGraph *g){ //BFS
118.  
     printf("BFS:\n");
119.  
     int num = g->vexnum;
120.  
     int visit[num];
121.  
     memset(visit,0,sizeof(visit)); //全赋值0
122.  
     Queue *p= initQueue();
123.  
     for(int i=0;i<num;i ){
124.  
     if(visit[i]==0){
125.  
     VisitingBFS(g,visit,i,p);
126.  
     }
127.  
     }
128.  
     printf("\n");
129.  
     }
130.  
      
131.  
     void VisitingDFS(ALGraph* g,int *visit,int begin){ //DFS递归实现
132.  
     VNode * tempV = g->vertcies[begin];
133.  
     ArcNode * tempA;
134.  
     visit[begin]=1;
135.  
     printf("%d ",tempV->data);
136.  
     if(tempV->first!=NULL){
137.  
     for(tempA=tempV->first;tempA!=NULL;tempA=tempA->next){
138.  
     if(visit[tempA->adjvex]==0){
139.  
     VisitingDFS(g,visit,tempA->adjvex);
140.  
     }
141.  
     }
142.  
     }
143.  
      
144.  
     }
145.  
      
146.  
      
147.  
      
148.  
     void DFS(ALGraph *g){ //DFS，为求简便此处采取递归实现
149.  
     printf("DFS:\n");
150.  
     int num = g->vexnum;
151.  
     int visit[num];
152.  
     memset(visit,0,sizeof(visit));
153.  
     for(int i=0;i<num;i ){
154.  
     if(visit[i]==0){
155.  
     VisitingDFS(g,visit,i);
156.  
     }
157.  
     }
158.  
     printf("\n");
159.  
     }
160.  
      
161.  
      
162.  
      
163.  
      
164.  
      
165.  
     void printALGRaph(ALGraph* g){ //输出图的基本信息
166.  
     printf("num of vexnum is %d, num of arcnum is %d\n",g->vexnum,g->arcnum);
167.  
     int i=0;
168.  
     ArcNode *tempA;
169.  
     VNode * tempV;
170.  
      
171.  
     while (i<g->vexnum)
172.  
     {
173.  
     tempV = g->vertcies[i];
174.  
     printf("data is: %d \n",tempV->data);
175.  
     tempA =tempV->first;
176.  
     if (tempA!=NULL)
177.  
     {
178.  
     printf("%d -> %d ",i 1,tempA->adjvex 1);
179.  
     while(tempA->next!=NULL){
180.  
     printf("-> ");
181.  
     tempA=tempA->next;
182.  
     printf("%d ",tempA->adjvex 1);
183.  
     }
184.  
     printf("\n");
185.  
     }
186.  
     i ;
187.  
      
188.  
      
189.  
     }
190.  
      
191.  
     }
192.  
      
193.  
      
194.  
     ALGraph* CreatTestGraph(ALGraph *g){ //创建测试用有向图
195.  
     g = (ALGraph*)malloc(sizeof(ALGraph));
196.  
     g->vexnum=9,g->arcnum=10;
197.  
     VNode *tempV;
198.  
     ArcNode *tempA;
199.  
     for(int i=0;i<9;i ){ //节点初始化
200.  
     tempV = (VNode *)malloc(sizeof(VNode));
201.  
     tempV->data=i 1;
202.  
     tempV->first=NULL;
203.  
     g->vertcies[i]=tempV;
204.  
     }
205.  
     tempA = (ArcNode *)malloc(sizeof(ArcNode)),tempA->next=NULL;
206.  
     tempA->adjvex=1,g->vertcies[0]->first=tempA;
207.  
     tempA = (ArcNode *)malloc(sizeof(ArcNode)),tempA->next=NULL;
208.  
     tempA->adjvex=3,g->vertcies[0]->first->next=tempA;
209.  
     tempA = (ArcNode *)malloc(sizeof(ArcNode)),tempA->next=NULL;
210.  
     tempA->adjvex=2,g->vertcies[1]->first=tempA;
211.  
     tempA = (ArcNode *)malloc(sizeof(ArcNode)),tempA->next=NULL;
212.  
     tempA->adjvex=5,g->vertcies[2]->first=tempA;
213.  
     tempA = (ArcNode *)malloc(sizeof(ArcNode)),tempA->next=NULL;
214.  
     tempA->adjvex=2,g->vertcies[3]->first=tempA;
215.  
     tempA = (ArcNode *)malloc(sizeof(ArcNode)),tempA->next=NULL;
216.  
     tempA->adjvex=4,g->vertcies[3]->first->next=tempA;
217.  
     tempA = (ArcNode *)malloc(sizeof(ArcNode)),tempA->next=NULL;
218.  
     tempA->adjvex=6,g->vertcies[4]->first=tempA;
219.  
     tempA = (ArcNode *)malloc(sizeof(ArcNode)),tempA->next=NULL;
220.  
     tempA->adjvex=7,g->vertcies[4]->first->next=tempA;
221.  
     tempA = (ArcNode *)malloc(sizeof(ArcNode)),tempA->next=NULL;
222.  
     tempA->adjvex=5,g->vertcies[6]->first=tempA;
223.  
     tempA = (ArcNode *)malloc(sizeof(ArcNode)),tempA->next=NULL;
224.  
     tempA->adjvex=8,g->vertcies[6]->first->next=tempA;
225.  
     return g;
226.  
     }
227.  
      
228.  
     int main(){
229.  
     ALGraph *g,*g1;
230.  
     g=InitGraph(g,5);
231.  
     printf("g:\n");
232.  
     printALGRaph(g);
233.  
     BFS(g);
234.  
     DFS(g);
235.  
     printf("\ng1:\n");
236.  
     g1 =CreatTestGraph(g1);
237.  
     printALGRaph(g1);
238.  
     BFS(g1);
239.  
     DFS(g1);
240.  
     }

这篇好文章是转载于：学新通技术网