图的存储结构分析

实验6.1实现图的存储和遍历一，实验目的掌握图的邻接矩阵和邻接表存储以及图的邻接矩阵存储的递归遍历。

二，实验内容6.1实现图的邻接矩阵和邻接表存储编写一个程序，实现图的相关运算，并在此基础上设计一个主程序，完成如下功能：（1）建立如教材图7.9所示的有向图G的邻接矩阵，并输出。

（2）由有向图G的邻接矩阵产生邻接表，并输出。

（3）再由（2）的邻接表产生对应的邻接矩阵，并输出。

6.2 实现图的遍历算法（4）在图G的邻接矩阵存储表示基础上，输出从顶点V1开始的深度优先遍历序列（递归算法）。

（5）利用非递归算法重解任务（4）。

（6）在图G的邻接表存储表示基础上，输出从顶点V1开始的广度优先遍历序列。

三，源代码及结果截图#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<malloc.h>#define MAX_VERTEX_NUM 20typedef char VRType;typedef int InfoType; // 存放网的权值typedef char VertexType; // 字符串类型typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网}/*建立有向图的邻接矩阵*/typedef struct ArcCell{VRType adj;//VRType是顶点关系类型，对无权图用1或0表示是否相邻;对带权图则为权值类型InfoType *info; //该弧相关信息的指针(可无)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM];//顶点向量AdjMatrix arcs;//邻接矩阵int vexnum,arcnum;;//图的当前顶点数和弧数GraphKind kind;//图的种类标志}MGraph;/* 顶点在顶点向量中的定位*/int LocateVex(MGraph &M,VRType v1){int i;for(i=0;i<M.vexnum;i++)if(v1==M.vexs[i])return i;return -1;}void CreateGraph(MGraph &M)//建立有向图的邻接矩阵{int i,j,k,w;VRType v1,v2;M.kind=DN;printf("构造有向网:\n");printf("\n输入图的顶点数和边数(以空格作为间隔):");scanf("%d%d",&M.vexnum,&M.arcnum);printf("输入%d个顶点的值(字符):",M.vexnum);getchar();for(i=0;i<M.vexnum;i++) //输入顶点向量{scanf("%c",&M.vexs[i]);}printf("建立邻接矩阵:\n");for(i=0;i<M.vexnum;i++)for(j=0;j<M.vexnum;j++){M.arcs[i][j].adj=0;M.arcs[i][j].info=NULL;}printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");for(k=0;k<M.arcnum;++k)// 构造表结点链表{cin>>w>>v1>>v2;i=LocateVex(M,v1);j=LocateVex(M,v2);M.arcs[i][j].adj=w;}}//按邻接矩阵方式输出有向图void PrintGraph(MGraph M){int i,j;printf("\n输出邻接矩阵:\n");for(i=0; i<M.vexnum; i++){printf("%10c",M.vexs[i]);for(j=0; j<M.vexnum; j++)printf("%2d",M.arcs[i][j].adj);printf("\n");}}// 图的邻接表存储表示typedef struct ArcNode{int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc; // 指向下一条弧的指针InfoType *info; // 网的权值指针）}ArcNode; // 表结点typedef struct VNode{VertexType data; // 顶点信息ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];// 头结点typedef struct{AdjList vertices;int vexnum,arcnum; // 图的当前顶点数和弧数int kind; // 图的种类标志}ALGraph;void CreateMGtoDN(ALGraph &G,MGraph &M){//由有向图M的邻接矩阵产生邻接表int i,j;ArcNode *p;G.kind=M.kind;G.vexnum=M.vexnum;G.arcnum=M.arcnum;for(i=0;i<G.vexnum;++i){//构造表头向量G.vertices[i].data=M.vexs[i];G.vertices[i].firstarc=NULL;//初始化指针}for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)if(M.arcs[i][j].adj){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.vertices[i].firstarc;p->info=M.arcs[i][j].info;G.vertices[i].firstarc=p;}}void CreateDNtoMG(MGraph &M,ALGraph &G){ //由邻接表产生对应的邻接矩阵int i,j;ArcNode *p;M.kind=GraphKind(G.kind);M.vexnum=G.vexnum;M.arcnum=G.arcnum;for(i=0;i<M.vexnum;++i)M.vexs[i]=G.vertices[i].data;for(i=0;i<M.vexnum;++i){p=G.vertices[i].firstarc;while(p){M.arcs[i][p->adjvex].adj=1;p=p->nextarc;}//whilefor(j=0;j<M.vexnum;++j)if(M.arcs[i][j].adj!=1)M.arcs[i][j].adj=0;}//for}//输出邻接表void PrintDN(ALGraph G){int i;ArcNode *p;printf("\n输出邻接表：\n");printf("顶点:\n");for(i=0;i<G.vexnum;++i)printf("%2c",G.vertices[i].data);printf("\n弧:\n");for(i=0;i<G.vexnum;++i){p=G.vertices[i].firstarc;while(p){printf("%c→%c(%d)\t",G.vertices[i].data,G.vertices[p->adjvex].data,p->info);p=p->nextarc;}printf("\n");}//for}int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)void(*VisitFunc)(char* v); // 函数变量(全局量)// 从第v个顶点出发递归地深度优先遍历图G。

图的常⽤存储结构⼀、邻接矩阵 邻接矩阵是简单的也是⽐较常⽤的⼀种表⽰图的数据结构，对于⼀个有N个点的图，需要⼀个N*N的矩阵，这个矩阵的i⾏第j列的数值表⽰点vi到点vj的距离。

邻接矩阵需要初始化，map[i][i] = 0;map[i][j] = INF(i != j)，对于每组读⼊的数据vi,vj,w(vi为边的起点,vj为边的终点,w为边的权值),赋值map[vi][vj] = w，另外邻接矩阵的值和边的输⼊顺序⽆关。

对于邻接矩阵来说，初始化需要O(n^2)的时间，建图需要O(m),所以总时间复杂度是O(n^2)，空间上，邻接矩阵的开销也是O(n^2)，和点的个数有关。

⼆、前向星 前向星是⼀种通过存储边的⽅式来存储图的数据结构。

构造的时候，只需要读⼊每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序，前向星就构造完毕，为了查询⽅便，经常会有⼀个数组存储起点为vi的第⼀条边的位置. 由于涉及排序，前向星的构造时间复杂度与排序算法有关，⼀般情况下时间复杂度为O(mlogN)，空间上需要两个数组，所以空间复杂度为O(m + n),有点在于可以应对点⾮常多的情况，可以存储重边，但是不能直接判断任意两个顶点之间是否有边.1 #include <iostream>2 #include <cmath>3 #include <cstdio>4 #include <cstring>5 #include <cstdlib>6 #include <algorithm>7using namespace std;8 typedef long long LL;910const int MAXN = 1000 + 3;11int head[MAXN]; //存储起点为Vi的边第⼀次出现的位置1213struct NODE14 {15int from;16int to;17int w;18 };19 NODE edge[MAXN];2021bool cmp(NODE a, NODE b)22 {23if(a.from == b.from && a.to == b.to) return a.w < b.w;24if(a.from == b.from) return a.to < b.to;25return a.from < b.from;26 }2728int main()29 {30 freopen("input.txt", "r", stdin);31int n,m;32 cin >> n >> m;33for(int i = 0; i < m; i++)34 {35 cin >> edge[i].from >> edge[i].to >> edge[i].w;36 }37 sort(edge, edge + m, cmp);38 memset(head, -1, sizeof(head));39 head[edge[0].from] = 0;40for(int i = 1; i < m; i++)41 {42if(edge[i].from != edge[i - 1].from)43 {44 head[edge[i].from] = i;45 }46 }47for(int i = 1; i <= n; i++)48 {49for(int k = head[i]; edge[k].from == i && k < m; k++)50 {51 cout << edge[k].from << '' << edge[k].to << '' << edge[k].w <<endl;52 }53 }54for(int i = 0; i <= n; i++)55 {56 cout << head[i] << "";57 }58 cout << endl;59return0;60 }三、链式前向星 链式前向星采⽤数组模拟链表的⽅式实现邻接表的功能，并且使⽤很少的额外空间，是当前建图和遍历效率最⾼的存储⽅式.数组模拟链表的主要⽅式是记录下⼀个节点的数组的在哪⼀个位置。