图的基本操作

68 阅读 0 评论 45 点赞

我是靠谱客的博主忧心摩托，最近开发中收集的这篇文章主要介绍图的基本操作，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

实验目的
1．
掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。
2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。
实验内容
程序1
/* 定义邻接矩阵类型 */
typedef int
adjmatrix[n+1][n+1];
/* 建立图的邻接矩阵 */
void CreatMatrix(adjmatrix GA)
/* 从初始点v出发深度优先遍历邻接矩阵GA表示的图 */
void DfsMatrix(adjmatrix GA,int v)
/*从初始点v出发广度优先遍历邻接矩阵GA表示的图*/
void BfsMatrix(adjmatrix GA,int v)
程序2
/* 邻接表的结点类型 */
typedef struct arc
{int adjvex;
struct arc *next;}ArcNode;
typedef struct VexNode
{int vertex;
ArcNode *firstarc;
}VerNode;
typedef VerNode AdjList[MAXNODE];
/* 建立图的邻接表 */
void CreatAdjlist(AdjList GL)
/* 从初始点v出发深度优先遍历邻接表GL表示的图 */
void DfsAdjlist(AdjList GL,int v)
/*从初始点v出发广度优先遍历邻接表GL表示的图*/
void BfsAdjlist(AdjList GL,int v)

参考程序1：


1 /* 该程序仅适应于无权有向图 */

2 /* 一组测试数据：

3 5 3 1 2 2 4 1 3 */

4 #include <iostream>

5 #include <stdio.h>

6 #include <queue>

7 using namespace std;

8

9 /* 定义邻接矩阵类型 */
 10 #define MAXV 100
 11 typedef int
adjmatrix[MAXV+1][MAXV+1];
 12 int V,E;
//顶点数和边数
 13
 14 /* 建立图的邻接矩阵 */
 15 void CreatMatrix(adjmatrix &GA)
 16 {
 17
memset(GA,0,sizeof(GA));
 18
printf("请问你要输入的图有多少个顶点？n");
 19
scanf("%d",&V);
 20
printf("有多少条边？n");
 21
scanf("%d",&E);
 22
int i;
 23
for(i=1;i<=E;i++){
 24
int v1,v2;
 25
printf("请输入第%d条边的起点：n",i);
 26
scanf("%d",&v1);
 27
printf("请输入第%d条边的终点：n",i);
 28
scanf("%d",&v2);
 29
GA[v1][v2] = 1;
 30
//GA[v2][v1] = 1;
 31 
}
 32 }
 33
 34 void printGraph(adjmatrix GA) //输出邻接矩阵
 35 {
 36
int i,j;
 37
for(i=1;i<=V;i++){
//输出
 38
for(j=1;j<=V;j++)
 39
printf("%d ",GA[i][j]);
 40
printf("n");
 41 
}
 42 }
 43
 44
 45 /* 从初始点v出发深度优先遍历邻接矩阵GA表示的图 */
 46 void DfsMatrix(adjmatrix GA,int v)
 47 {
 48
int i;
 49
printf("->%d",v);
 50
for(i=1;i<=V;i++){
 51
if(v==i) continue;
 52
if(GA[v][i]==1)
 53 
DfsMatrix(GA,i);
 54 
}
 55 }
 56
 57 /*从初始点v出发广度优先遍历邻接矩阵GA表示的图*/
 58 void BfsMatrix(adjmatrix GA,int v)
 59 {
 60
queue <int> q;
 61
int cur,i;
 62 
q.push(v);
 63
while(!q.empty()){
 64
cur = q.front();
 65 
q.pop();
 66
if(cur==v)
 67
printf("%d",v);
 68
else
 69
printf("->%d",cur);
 70
for(i=1;i<=V;i++){
 71
if(GA[cur][i]==1)
 72 
q.push(i);
 73 
}
 74 
}
 75 }
 76
 77 void ShowDFS(adjmatrix GA)
//进行深度优先遍历
 78 {
 79
int n,i;
 80
printf("请输入开始遍历的点:");
 81
scanf("%d",&n);
 82
//输出dfs遍历顺序
 83
for(i=1;i<=V;i++)
 84
if(GA[n][i]==1)
 85
break;
 86
if(i>V){
 87
printf("%dn",n);
 88
return ;
 89 
}
 90
printf("%d",n);
 91
for(;i<=V;i++){
 92
if(i==n) continue;
 93
if(GA[n][i]==1)
 94 
DfsMatrix(GA,i);
 95 
}
 96
printf("n");
 97 }
 98 void ShowBFS(adjmatrix GA)
//进行广度优先遍历
 99 {
100
int n,i;
101
printf("请输入开始遍历的点:");
102
scanf("%d",&n);
103
//输出dfs遍历顺序
104
for(i=1;i<=V;i++)
105
if(GA[n][i]==1)
106
break;
107
if(i>V){
108
printf("%dn",n);
109
return ;
110 
}
111 
BfsMatrix(GA,n);
112
printf("n");
113 }
114
115 int main()
116 {
117 
adjmatrix g;
118
printf("【注：本程序适应于无权有向图】nn");
119
printf("[1] 创建图n");
120
CreatMatrix(g);
//创建
121
printf("n");
122
printf("创建成功nn");
123
system("pause");
124
system("cls");
125
126
printf("[2] 邻接矩阵为：n");
127
printGraph(g);
//输出邻接矩阵
128
printf("n");
129
system("pause");
130
system("cls");
131
132
printf("[3] DFS：n");
133
ShowDFS(g);
//dfs
134
printf("n");
135
system("pause");
136
system("cls");
137
138
printf("[4] BFS：n");
139 
ShowBFS(g);
140
printf("n");
141
system("pause");
142
system("cls");
143
144
return 0;
145 }

参考程序2：


1 /* 该程序适应于无权有向图 */

2 /* 一组测试数据：

3 5 3 1 2 2 4 1 3 */

4 #include <iostream>

5 #include <stdio.h>

6 #include <queue>

7 using namespace std;

8 #define MAXNODE 1000

9
 10 /* 邻接表的结点类型 */
 11 typedef struct arc{
 12
int adjvex;
 13
struct arc *next;
 14 }ArcNode;
 15 typedef struct VexNode{
 16
int vertex;
 17
ArcNode *firstarc;
 18 }VerNode;
 19 typedef VerNode AdjList[MAXNODE];
 20 int V,E;
//顶点数和边数
 21
 22 /* 建立图的邻接表 */
 23 void CreatAdjlist(AdjList &GL)
 24 {
 25
memset(GL,0,sizeof(GL));
 26
printf("请问你要输入的图有多少个顶点？n");
 27
scanf("%d",&V);
 28
printf("有多少条边？n");
 29
scanf("%d",&E);
 30
int i;
 31
for(i=1;i<=E;i++){
 32
int v1,v2;
 33
printf("请输入第%d条边的起点：n",i);
 34
scanf("%d",&v1);
 35
printf("请输入第%d条边的终点：n",i);
 36
scanf("%d",&v2);
 37
if(GL[v1].firstarc==NULL){
//如果该节点对应的表头结点的第一个边节点是空，说明这个节点还没有与它连接的节点
 38
GL[v1].firstarc = (ArcNode*)malloc(sizeof(ArcNode));
 39
GL[v1].firstarc->adjvex = v2;
 40
GL[v1].firstarc->next = NULL;
 41
continue;
 42 
}
 43
ArcNode *p = GL[v1].firstarc;
 44
while(p->next!=NULL)
//找到最后一个边节点
 45
p = p->next;
 46
p->next = (ArcNode*)malloc(sizeof(ArcNode));
 47
p->next->adjvex = v2;
 48
p->next->next = NULL;
 49 
}
 50 }
 51 void printGraph(AdjList GL)
 52 {
 53
int i;
 54
for(i=1;i<=V;i++){
//输出每一个顶点的下一个顶点
 55
ArcNode *p = GL[i].firstarc;
 56
if(p==NULL)
 57
printf("【顶点%d】没有下一个顶点。",i);
 58
else
 59
printf("【顶点%d】的下一个顶点是：",i);
 60
while(p){
 61
printf("【顶点%d】 ",p->adjvex);
 62
p = p->next;
 63 
}
 64
printf("n");
 65 
}
 66 }
 67
 68 /* 从初始点v出发深度优先遍历邻接表GL表示的图 */
 69 void DfsAdjlist(AdjList GL,int v)
 70 {
 71
printf("->%d",v);
 72
ArcNode *p = GL[v].firstarc;
 73
while(p){
 74
DfsAdjlist(GL,p->adjvex);
 75
p = p->next;
 76 
}
 77 }
 78
 79 /*从初始点v出发广度优先遍历邻接表GL表示的图*/
 80 void BfsAdjlist(AdjList GL,int v)
 81 {
 82
queue <int> q;
 83
int cur;
 84 
q.push(v);
 85
while(!q.empty()){
 86
cur = q.front();
 87 
q.pop();
 88
if(cur==v)
 89
printf("%d",v);
 90
else
 91
printf("->%d",cur);
 92
ArcNode *p = GL[cur].firstarc;
 93
while(p){
 94
q.push(p->adjvex);
 95
p = p->next;
 96 
}
 97 
}
 98 }
 99
100
101 void ShowDFS(AdjList GL)
//进行深度优先遍历
102 {
103
int n;
104
printf("请输入开始遍历的点:");
105
scanf("%d",&n);
106
//输出dfs遍历顺序
107
if(GL[n].firstarc==NULL){
108
printf("%dn",n);
109
return ;
110 
}
111
printf("%d",n);
112
ArcNode *p = GL[n].firstarc;
113
while(p){
114
DfsAdjlist(GL,p->adjvex);
115
p = p->next;
116 
}
117
printf("n");
118 }
119 void ShowBFS(AdjList GL)
//进行广度优先遍历
120 {
121
int n;
122
printf("请输入开始遍历的点:");
123
scanf("%d",&n);
124
//输出bfs遍历顺序
125
if(GL[n].firstarc==NULL){
126
printf("%dn",n);
127
return ;
128 
}
129 
BfsAdjlist(GL,n);
130
printf("n");
131 }
132
133 int main()
134 {
135 
AdjList GL;
136
//创建邻接表
137 
CreatAdjlist(GL);
138
printf("n创建成功!nn");
139
system("pause");
140
system("cls");
141
142
//输出邻接表
143
printf("邻接表内容：n");
144 
printGraph(GL);
145
printf("n");
146
system("pause");
147
system("cls");
148
149
//dfs
150
printf("DFS:n");
151 
ShowDFS(GL);
152
printf("n");
153
system("pause");
154
system("cls");
155
156
//bfs
157
printf("BFS:n");
158 
ShowBFS(GL);
159
printf("n");
160
system("pause");
161
system("cls");
162
163
return 0;
164 }