范某帅的博客
0%

数据结构-第六章-图

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 13k 阅读时长 ≈ 11 分钟

图的存储

邻接矩阵法

1
2
3
4
5
6
7
8
#include<stdio.h>
#define MaxVertexNum 100//顶点数目的最大值

typedef struct {
	char Vex[MaxVertexNum];//顶点表
	int Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
	int vexnum, arcnum;//图的当前定点数和边数/弧数
}MGraph;

邻接矩阵存储带权图（网）

邻接表法（顺序+链式存储）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#define MaxVertexNum 100//顶点数目的最大值

//边/弧
typedef struct ArcNode {
	int adjvex;//边/弧指向哪个结点
	struct ArcNode* next;//指向下一条狐的指针
}ArcNode;

//顶点
typedef struct VNode {
	char data;//顶点信息
	ArcNode* first;//第一条边/弧
}VNode, AdjList[MaxVertexNum];

//用邻接表存储的图
typedef struct {
	AdjList vertices;
	int vexnum, arcnum;//图的当前定点数和边数/弧数
}ALGraph;

十字链表存储有向图

邻接多重表存储无向图

图的基本操作

图的广度优先遍历

注：代码有问题 暂未解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include<stdio.h>
#include <malloc.h>
#define Max 10

//邻接表结构
typedef int VertexType;//顶点类型
typedef int EdgeType;//权值类型

//边/弧
typedef struct EdgeNode {
	int adjvex;//邻接点域，保存邻接点下标
	EdgeType weight;//存储权值
	struct EdgeNode* next;//链域，指向下一个邻接点
}EdgeNode;

//顶点
typedef struct VertexNode {
	VertexType data;
	EdgeNode* first_edge;
}VertexNode, AdjList[Max];

//用邻接表存储的图
typedef struct {
	AdjList adjList;
	int numVertexes, numEdges;//顶点数量和边数量
}GraphAdjList, * GraphAdj;


//链式队列结点
typedef struct LinkNode {
	VertexNode data;
	struct LinkNode* next;
}LinkNode;

//队头队尾
typedef struct {
	LinkNode* front, * rear;
}LinkQueue;

//创建邻接表
void InitGraph(GraphAdj& G) {
	int m, n;
	EdgeNode* e = NULL;
	G->numVertexes = 8;
	G->numEdges = 10;
	for (int i = 0; i < G->numVertexes; i++)
	{
		G->adjList[i].data = i + 1;
		G->adjList[i].first_edge = NULL;
	}
	for (int k = 0; k < G->numEdges; k++)
	{
		printf("输入边(Vi,Vj)上的顶点序号：");
		scanf_s("%d%d", &m, &n);

		e = (EdgeNode*)malloc(sizeof(EdgeNode));
		e->adjvex = n;
		e->next = G->adjList[m].first_edge;
		G->adjList[m].first_edge = e;

		e = (EdgeNode*)malloc(sizeof(EdgeNode));
		e->adjvex = m;
		e->next = G->adjList[n].first_edge;
		G->adjList[n].first_edge = e;
	}
}

int FirstNeighbor(GraphAdj G, int x)
{
	if (x >= Max)
	{
		return -1;
	}
	if (G->adjList[x].first_edge != NULL)
		return G->adjList[x].first_edge->adjvex;
	else
		return -1;
}

int NextNeighbor(GraphAdj G, int x, int y) {
	EdgeNode* temp = G->adjList[x].first_edge;
	while (temp != NULL)
	{
		if (temp->adjvex == y)
		{
			return -1;
		}
		else
		{
			temp = temp->next;
			if (temp != NULL)
			{
				return temp->adjvex;
			}
			else
			{
				return -1;
			}
		}
	}
}

//初始化队列 带头结点
void InitQueue(LinkQueue& Q) {
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next = NULL;
}

//是否为空
bool isEmpty(LinkQueue Q) {
	return Q.front == Q.rear;
}

//新元素入队
void EnQueue(LinkQueue& Q, GraphAdj G, int v) {
	LinkNode* new_point = (LinkNode*)malloc(sizeof(LinkNode));
	new_point->data = G->adjList[v];
	new_point->next = NULL;
	Q.rear->next = new_point;
	Q.rear = new_point;
}

void DeQueue(LinkQueue& Q, int& v) {
	if (Q.front == Q.rear)
	{
		printf("队列为空");
	}
	else
	{
		LinkNode* new_point = Q.front->next;
		v = new_point->data.data;
		Q.front->next = new_point->next;
		if (Q.rear == new_point)
		{
			Q.rear = Q.front;
		}
		free(new_point);
	}
}

bool visited[Max];

void visit(GraphAdj G, int num) {
	printf("访问到的数据为：%d\n", G->adjList[num].data);
	visited[num] = true;
}

void BFS(GraphAdj G, int v) {//从顶点出发，广度优先遍历图
	LinkQueue Q;
	InitQueue(Q);
	visit(G, v);
	EnQueue(Q, G, v);
	while (!isEmpty(Q))
	{
		DeQueue(Q, v);
		for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
		{
			if (!visited[w])
			{
				visit(G, w);
				EnQueue(Q, G, w);
			}
		}
	}
}

void BFS_Traverse(GraphAdj G) {
	for (int i = 0; i < Max; i++)
	{
		visited[i] = false;
	}
	for (int i = 0; i < G->numVertexes; i++)
	{
		if (!visited[i])
		{
			BFS(G, i);
		}
	}
}

int main() {
	GraphAdj G = (GraphAdj)malloc(sizeof(GraphAdj));
	InitGraph(G);
	BFS_Traverse(G);
	return 0;
}

可供参考的代码：

  1. 邻接表
  2. 邻接矩阵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
#include <stdio.h>
#include <stdlib.h>
#define VertexMax 20 //最大顶点个数 
#define Maxsize 100 //队列最大元素个数100 

typedef char VertexType;//顶点的数据类型（char）
typedef int dataType; //队列元素类型 

/*邻接表结构体*/
typedef struct ArcNode//边表 
{
	int adjvex;//存储的是该顶点在顶点数组即AdjList[]中的位置 
	struct ArcNode *next;
}ArcNode;

typedef struct VNode //顶单个点 
{
	VertexType vertex;
	struct ArcNode *firstarc;
}VNode;

typedef struct //顶点表 
{
	VNode AdjList[VertexMax];//由顶点构成的结构体数组 
	int vexnum,arcnum; //顶点数和边数 
}ALGraph;

/*循环队列结构体*/
typedef struct
{
	dataType *base;
	int front;
	int rear;
}CyQueue;

/*无向图UDG基本操作*/
int LocateVex(ALGraph *G,VertexType v)
{    
    int i;
	for(i=0;i<G->vexnum;i++)
	{
		if(v==G->AdjList[i].vertex)
		{
			return i;
		}
	}
	
	printf("No Such Vertex!\n");
	return -1;
}

//2.无向图 
void CreateUDG(ALGraph *G)
{
	int i,j;
	//1.输入顶点数和边数
	printf("输入顶点个数和边数：\n");
	printf("顶点数 n="); 
	scanf("%d",&G->vexnum);
	printf("边  数 e="); 
	scanf("%d",&G->arcnum);
	printf("\n"); 
	
	printf("\n");
	//2.顶点表数据域填值初始化顶点表指针域
	printf("输入顶点元素(无需空格隔开)：");
	for(i=0;i<G->vexnum;i++)
	{
		scanf(" %c",&G->AdjList[i].vertex);
		G->AdjList[i].firstarc=NULL;
	} 
	printf("\n");
	
	//3.输入边信息构造邻接表
	int n,m;
	VertexType v1,v2;
	ArcNode *p1,*p2; 
	
	printf("请输入边的信息：\n\n"); 
	for(i=0;i<G->arcnum;i++)
	{   //输入边信息，并确定v1和v2在G中的位置，即顶点在AdjList[]数组中的位置（下标） 
		printf("输入第%d条边信息：",i+1); 
		scanf(" %c%c",&v1,&v2);
		n=LocateVex(G,v1);
		m=LocateVex(G,v2);
		
		if(n==-1||m==-1)
		 {
		 	printf("NO This Vertex!\n");
		 	return;
		  } 
		
		p1=(ArcNode *)malloc(sizeof(ArcNode));
		p1->adjvex=m;//填上坐标 
		p1->next=G->AdjList[n].firstarc;//改链（头插法） 
		G->AdjList[n].firstarc=p1;
		
		p2=(ArcNode *)malloc(sizeof(ArcNode));//无向图的对称 
		p2->adjvex=n;
		p2->next=G->AdjList[m].firstarc;
		G->AdjList[m].firstarc=p2;
		
	}//for 

} 

void print(ALGraph G)
{
	int i;
	ArcNode *p;
	printf("\n-------------------------------");
	printf("\n图的邻接表表示：\n");
	
	for(i=0;i<G.vexnum;i++)
	{
		printf("\n   AdjList[%d]%4c",i,G.AdjList[i].vertex);
		p=G.AdjList[i].firstarc;
		
		while(p!=NULL)
		{
			printf("-->%d",p->adjvex);
			p=p->next;
		}
	 } 
	 printf("\n");
} 

/*循环队列基本操作*/
void create(CyQueue *q)
{
	q->base=(dataType *)malloc(Maxsize*sizeof(dataType));
	if(!q->base)
	{
		printf("Space allocation failed!\n");
		return;
	}
	q->front=q->rear=0;
	return;
}

void EnQueue(CyQueue *q,dataType value)
{
	if((q->rear+1)%Maxsize==q->front)
	{
		printf("Cyclic Queue is Full!\n");
		return;
	}
	q->base[q->rear]=value;
	q->rear=(q->rear+1)%Maxsize;
	return;
}

void DeQueue(CyQueue *q,dataType *value)
{
	if(q->front==q->rear)
	{
		printf("Cyclic Queue is Empty!\n");
		return;
	}
	*value=q->base[q->front];
	q->front=(q->front+1)%Maxsize;
	return;
} 

int QueueEmpty(CyQueue *q)
{
    if (q->front==q->rear)//队列为空返回1，不为空返回0 
	{
        return 1;
    }
    return 0;
}


/*广度优先遍历*/
int visited[VertexMax]; //定义数组为全局变量 

void BFS(ALGraph *G,int i)
{
	int j;
	struct ArcNode *p;
	CyQueue q;
	create(&q);
	
    //1.设置起始点
	printf("%c",G->AdjList[i].vertex);//1.输出起始结点
	visited[i]=1;//2.将已访问的结点标志成1
	EnQueue(&q,i);//3.将第一个结点入队 

    //2.由起始点开始，对后续结点进行操作
	while(!QueueEmpty(&q))
	{
		p=G->AdjList[i].firstarc;
		
		DeQueue(&q,&i);
		while(p!=NULL)
		{
			
			if(visited[p->adjvex]==0)
			{
				printf("%c",G->AdjList[p->adjvex].vertex);
	            visited[p->adjvex]=1;
	            EnQueue(&q,p->adjvex);
			}
			p=p->next;//查找完之后，将p向后推一位 
		}
	} 	
} 

void BFSTraverse(ALGraph *G)
{
	int i;
	
	//数组初始化为全0 
	for(i=0;i<G->vexnum;i++)
	{
		visited[i]=0;
	} 
	
	for(i=0;i<G->vexnum;i++)
	{
		if(visited[i]==0)
		{
			BFS(G,i);
		}
	}
} 

int main() 
{
	ALGraph G; 
	CreateUDG(&G);
	print(G); 
	
	printf("\n\n广度优先遍历："); 
	BFSTraverse(&G); 
	 
	return 0;
}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include <stdio.h>
#include <stdlib.h>
#define VertexMax 100 //最大顶点数为100
#define Maxsize 100 //队列最大元素个数100 

typedef char VertexType; //每个顶点数据类型为字符型 
typedef int dataType; //队列元素类型 

/*图结构体*/
typedef struct
{
	VertexType Vertex[VertexMax];//存放顶点元素的一维数组 
	int AdjMatrix[VertexMax][VertexMax];//邻接矩阵二维数组 
	int vexnum,arcnum;//图的顶点数和边数  
}MGraph;

/*队列结构体*/
typedef struct
{
	dataType *base;
	int front;
	int rear;
}CyQueue;
 
/*无向图UDG的基本操作*/
int LocateVex(MGraph *G,VertexType v)//查找元素v在一维数组 Vertex[] 中的下标，并返回下标 
{
	int i;
	
	for(i=0;i<G->vexnum;i++)
	{
		if(v==G->Vertex[i])
		{
			return i; 
		} 
	 } 
	 
	 printf("No Such Vertex!\n");
	 return -1;
}

void CreateUDG(MGraph *G) 
{
	int i,j;

	printf("输入顶点个数和边数：\n");
	printf("顶点数 n="); 
	scanf("%d",&G->vexnum);
	printf("边  数 e="); 
	scanf("%d",&G->arcnum);
	printf("\n"); 
	
	printf("\n");
	

	printf("输入顶点元素(无需空格隔开)：");
	scanf("%s",G->Vertex);
	printf("\n");

	for(i=0;i<G->vexnum;i++) 
	 for(j=0;j<G->vexnum;j++)
	    {
	    	G->AdjMatrix[i][j]=0;
		}
	

	 int n,m;
	 VertexType v1,v2;
	 
	 printf("请输入边的信息：\n");
	 for(i=0;i<G->arcnum;i++)
	 {
	 	printf("输入第%d条边信息：",i+1);
	 	scanf(" %c%c",&v1,&v2);
	 	n=LocateVex(G,v1); 
	 	m=LocateVex(G,v2); 
	 	
	 	if(n==-1||m==-1)
		 {
		 	printf("NO This Vertex!\n");
		 	return;
		  } 
	
	   G->AdjMatrix[n][m]=1;
	   G->AdjMatrix[m][n]=1;
	 } 
	 
}

void print(MGraph G)
{
	int i,j;
	printf("\n-------------------------------");
	printf("\n 邻接矩阵：\n\n"); 	

		printf("\t ");
	    for(i=0;i<G.vexnum;i++)
		printf("  %c",G.Vertex[i]);
		printf("\n");
		 
		for(i=0;i<G.vexnum;i++)
	   {
	   	  printf("\t%c",G.Vertex[i]);
	   	
		  for(j=0;j<G.vexnum;j++)
	    {
	 	    printf("  %d",G.AdjMatrix[i][j]);
	    }
	        printf("\n");
	   }
}

/*循环队列基本操作*/
void create(CyQueue *q)
{
	q->base=(dataType *)malloc(Maxsize*sizeof(dataType));
	if(!q->base)
	{
		printf("Space allocation failed!\n");
		return;
	}
	q->front=q->rear=0;
	return;
}

void EnQueue(CyQueue *q,dataType value)
{
	if((q->rear+1)%Maxsize==q->front)
	{
		printf("Cyclic Queue is Full!\n");
		return;
	}
	q->base[q->rear]=value;
	q->rear=(q->rear+1)%Maxsize;
	return;
}

void DeQueue(CyQueue *q,dataType *value)
{
	if(q->front==q->rear)
	{
		printf("Cyclic Queue is Empty!\n");
		return;
	}
	*value=q->base[q->front];
	q->front=(q->front+1)%Maxsize;
	return;
} 

int QueueEmpty(CyQueue *q)
{
    if (q->front==q->rear)//队列为空返回1，不为空返回0 
	{
        return 1;
    }
    return 0;
}

/*广度优先遍历BFS*/ 
int visited[VertexMax];//定义"标志"数组为全局变量 

void BFS(MGraph *G,int i)
{
	int j;
	CyQueue q;
	create(&q);
   //1.设置起始点 
	printf("%c",G->Vertex[i]);//1.输出当前结点 
	visited[i]=1;//2.将已访问的结点标志成1
	EnQueue(&q,i);//3.将第一个结点入队 
    
    //2.由起始点开始，对后续结点进行操作
	while(!QueueEmpty(&q))
	{
		
		DeQueue(&q,&i);
		
		for(j=0;j<G->vexnum;j++)
		{
			if(G->AdjMatrix[i][j]==1&&visited[j]==0)
			{
				printf("%c",G->Vertex[j]);//输出符合条件的顶点 
	            visited[j]=1;//设置成已访问状态1 
	            EnQueue(&q,j);//入队 
			}
		}
	} 	
} 

void BFSTraverse(MGraph *G)
{
	int i;
	
	//数组初始化为全0 
	for(i=0;i<G->vexnum;i++)
	{
		visited[i]=0;
	} 
	
	for(i=0;i<G->vexnum;i++)
	{
		if(visited[i]==0)
		{
			BFS(G,i);
		}
	}
} 

int main() 
{
	MGraph G; 
	CreateUDG(&G);
	print(G); 
	
	printf("\n\n广度优先遍历："); 
	BFSTraverse(&G); 
	 
	return 0;
}

参考运行结果：

图的深度优先遍历

最小生成树

Prim算法（普里姆）

Kruskal算法（克鲁斯卡尔）

Prim算法和Kruskal比较

最短路径问题

BFS算法

Dijkstra算法

Floyd算法

有向无环图(描述表达式)

本文标题:数据结构-第六章-图

文章作者:fanchen

发布时间:2021年06月06日 - 18:07:08

最后更新:2021年06月29日 - 12:14:47

原始链接:http://88fanchen.github.io/posts/5b7c4e95/

许可协议:署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。