首页 > 代码库 > 数据结构 【实验9 图的基本操作】
数据结构 【实验9 图的基本操作】
实验9 图的基本操作
实验目的
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("%d\n",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("%d\n",n);109 return ;110 }111 BfsMatrix(GA,n);112 printf("\n");113 }114 115 int main()116 {117 adjmatrix g;118 printf("【注:本程序适应于无权有向图】\n\n");119 printf("[1] 创建图\n");120 CreatMatrix(g); //创建121 printf("\n");122 printf("创建成功\n\n");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); //dfs134 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("%d\n",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("%d\n",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创建成功!\n\n");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 //dfs150 printf("DFS:\n");151 ShowDFS(GL);152 printf("\n");153 system("pause");154 system("cls");155 156 //bfs157 printf("BFS:\n");158 ShowBFS(GL);159 printf("\n");160 system("pause");161 system("cls");162 163 return 0;164 }
Freecode : www.cnblogs.com/yym2013