C语言建立有向图的邻接表及其遍历操作
生活随笔
收集整理的這篇文章主要介紹了
C语言建立有向图的邻接表及其遍历操作
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
1 /*C語言建立有向圖的鄰接表及其遍歷操作*/
2 #include"stdio.h"
3 #include"stdlib.h"
4 //圖的鄰接矩陣儲(chǔ)存結(jié)構(gòu)
5 typedef char elemtype;
6 #define maxsize 10
7 #define queuesize 100
8 //邊結(jié)點(diǎn)的類型定義
9 typedef struct edgenode
10 {
11 int adjvex;//存放鄰接的點(diǎn)在頂點(diǎn)表的下標(biāo)，鄰接點(diǎn)
12 struct edgenode *next;//指向Vi下一個(gè)鄰接點(diǎn)的邊結(jié)點(diǎn)
13 int weight;/*權(quán)值*/
14 }edgenode;
15 //頂點(diǎn)結(jié)點(diǎn)類型定義
16 typedef struct vexnode
17 {
18 elemtype data; //存儲(chǔ)頂點(diǎn)的名稱或其相關(guān)信息
19 edgenode *firstedge;//邊表頭指針
20 }vexnode;
21 //圖的鄰接表數(shù)據(jù)類型
22 typedef struct{
23 vexnode vexlist[maxsize];//頂點(diǎn)表
24 int n,e;
25 }graph;
26 //在圖g中查找頂點(diǎn)v,存在頂點(diǎn)數(shù)組中的下標(biāo)，不存在返回-1
27 int locatevex(graph g,elemtype v)
28 {
29 int i;
30 for(i=0;i<g.n;i++)
31 if(g.vexlist[i].data==v)return i;
32 return -1;
33 }
34 //打印圖信息
35 void print(graph g)
36 {
37 int i;
38 edgenode *p;
39 printf("圖的鄰接表表示：");
40 for(i=0;i<g.n;i++){
41 printf("\n%4c",g.vexlist[i].data);
42 p=g.vexlist[i].firstedge;
43 while(p!=NULL){
44 printf("-->%d",p->adjvex);p=p->next;
45 }
46 }
47 printf("\n");
48 }
49 void creategraph(graph *g){
50 int i,j,k;
51 elemtype v1,v2;
52 edgenode *s;
53 printf("請(qǐng)輸入圖的頂點(diǎn)數(shù)及邊數(shù)\n");
54 printf("頂點(diǎn)數(shù) n=");scanf("%d",&g->n);
55 printf("邊 數(shù) e=");scanf("%d",&g->e);
56 printf("請(qǐng)輸入圖的頂點(diǎn)信息：\n");getchar();
57 for(i=0;i<=g->n;i++){
58 scanf("%c",&g->vexlist[i].data); //構(gòu)造頂點(diǎn)信息
59 g->vexlist[i].firstedge=NULL;
60 }
61 printf("請(qǐng)輸入圖的邊的信息：\n");
62 for(k=0;k<g->e;k++)
63 {
64 printf("請(qǐng)輸入第%d條邊的兩個(gè)端點(diǎn)下標(biāo)：",k+1);
65 scanf("%c%c",&v1,&v2);getchar();//輸入一條邊的兩個(gè)頂點(diǎn)
66 i=locatevex(*g,v1);
67 j=locatevex(*g,v2);
68 if(i>=0&&j>=0){
69 //建立無向圖的鄰接表
70 /*s=(edgenode *)malloc(sizeof(edgenode));
71 s->adjvex=j;
72 s->next=g->vexlist[i].firstedge;
73 g->vexlist[i].firstedge=s;
74
75 s=(edgenode *)malloc(sizeof(edgenode));
76 s->adjvex=i;
77 s->next=g->vexlist[j].firstedge;
78 g->vexlist[j].firstedge=s;*/
79 //建立有向圖的鄰接表
80 s=(edgenode *)malloc(sizeof(edgenode));
81 s->adjvex=j;
82 s->next=g->vexlist[i].firstedge;
83 g->vexlist[i].firstedge=s;
84 }
85 }
86 }
87 int visited[maxsize];/* 訪問標(biāo)志數(shù)組*/
88 /*從第i個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G*/
89 void DFS(graph g,int i)
90 {
91 edgenode *p;
92 printf("%3c",g.vexlist[i].data);/*訪問第i個(gè)項(xiàng)點(diǎn)*/
93 visited[i]=1;
94 p=g.vexlist[i].firstedge;
95 while(p!=NULL) {
96 if(visited[p->adjvex]==0)
97 DFS(g,p->adjvex);/*對(duì)i的尚未訪問的鄰接頂點(diǎn)j遞歸調(diào)用DFS*/
98 p=p->next;
99 }
100 }
101 void DFStraverse(graph g) /*對(duì)圖G進(jìn)行深度優(yōu)先遍歷*/
102 {
103 int v;
104 for (v=0; v<g.n;v++)visited[v]=0; /*初始化標(biāo)志數(shù)組*/
105 for (v=0; v<g.n;v++) /*保證非連通圖的遍歷*/
106 /*從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G*/
107 if (!visited[v])DFS(g,v);
108 }
109 //循環(huán)隊(duì)列存儲(chǔ)結(jié)構(gòu)定義
110 typedef struct cirqueue
111 {
112 elemtype *data; //隊(duì)列存儲(chǔ)空間的首地址
113 int front; //隊(duì)頭位置：指向當(dāng)前隊(duì)頭元素
114 int rear; //隊(duì)尾位置：指向當(dāng)前隊(duì)尾元素的下一位置
115 }cirqueue; // 循環(huán)隊(duì)列
116 //構(gòu)造空隊(duì)，如果成功，返回1，如果失敗，返回0
117 int initqueue(cirqueue *q)
118 {
119 q->data=(elemtype *)malloc(queuesize*sizeof(cirqueue));
120 if (q->data==NULL)return 0; // 存儲(chǔ)分配失敗
121 q->front=q->rear=0;
122 return 1;
123 }
124 // 插入元素e為Q的新的隊(duì)尾元素 ,如果成功，返回1，如果失敗，返回0
125 int enqueue (cirqueue *q,elemtype e)
126 {
127 if ((q->rear+1) % queuesize == q->front)
128 return 0; //隊(duì)列滿
129 q->data[q->rear] = e;
130 q->rear = (q->rear+1) % queuesize; //隊(duì)尾后移一位
131 return 1;
132 }
133 //若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值,并返回1；否則返回0
134 int dequeue (cirqueue *q,int *e)
135 {
136 if (q->front == q->rear) return 0; //隊(duì)列為空
137 *e = q->data[q->front];
138 q->front = (q->front+1) %queuesize; //隊(duì)頭后移一位
139 return 1;
140 }
141 //若棧不空，則用e返回隊(duì)頭元素,并返回1；否則返回0
142 int getfront(cirqueue q,elemtype *e)
143 {
144 if (q.front == q.rear) return 0; //隊(duì)列為空
145 *e=q.data[q.front];
146 return 1;
147 }
148 //若隊(duì)列為空棧，則返回1，否則返回0
149 int queueempty(cirqueue q)//棧非空
150 {
151 if(q.front == q.rear)return 1; //隊(duì)列為空
152 else return 0;
153 }
154 //返回隊(duì)列的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度
155 int queuelength(cirqueue q)
156 {
157 return (q.rear-q.front+queuesize) % queuesize;
158 }
159 //【算法6-10：利用鄰接矩陣實(shí)現(xiàn)連通圖的廣度優(yōu)先搜索遍歷】
160 int BFSvisited[maxsize];
161 cirqueue q;
162 /*從第k個(gè)頂點(diǎn)出發(fā)廣度優(yōu)先遍歷圖G,G以鄰接矩陣表示。*/
163 void BFS(graph g,int k){
164 int i;
165 edgenode *p;
166 initqueue(&q);/*初始化隊(duì)列*/
167 printf("%3c",g.vexlist[k].data);/*訪問第k個(gè)項(xiàng)點(diǎn)*/
168 visited[k]=1;
169 enqueue(&q,k);/*第k個(gè)頂點(diǎn)進(jìn)隊(duì)*/
170 while(queueempty(q)==0) {/*隊(duì)列非空*/
171 dequeue(&q,&i);
172 p=g.vexlist[i].firstedge;/*獲取第1個(gè)鄰接點(diǎn)*/
173 while(p!=NULL){
174 if(visited[p->adjvex]==0){
175 /*訪問第i個(gè)頂點(diǎn)的末曾訪問的頂點(diǎn)*/
176 printf("%3c",g.vexlist[p->adjvex].data);
177 visited[p->adjvex]=1;
178 enqueue(&q,p->adjvex);/*第k個(gè)頂點(diǎn)進(jìn)隊(duì)*/
179 }
180 p=p->next;
181 }
182 }
183 }
184 void BFStraverse(graph g) //對(duì)圖G進(jìn)行廣度優(yōu)先遍歷
185 {
186 int v;
187 for (v=0; v<g.n;v++) //初始化標(biāo)志數(shù)組
188 visited[v]=0;
189 for (v=0; v<g.n;v++) //保證非連通圖的遍歷
190 if (!visited[v])BFS(g,v);
191 //從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G
192 }
193 int main()
194 {
195 graph g;
196 creategraph(&g);
197 print(g);
198 printf("\n");
199 printf("圖的深度優(yōu)先遍歷序列：\n");
200 DFStraverse(g);
201 printf("\n");
202 printf("圖的廣度優(yōu)先遍歷序列：\n");
203 BFStraverse(g);
204 printf("\n");
205 return 0;
206 }
轉(zhuǎn)載于:https://www.cnblogs.com/1772642558sgzj/p/9354882.html
總結(jié)
以上是生活随笔為你收集整理的C语言建立有向图的邻接表及其遍历操作的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 勾股数性质
- 下一篇： Android.mk文件编写