实验目的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 /* 该程序仅适应于无权有向图 */  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 }

  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 }