数据结构学习小记3（图2之图的存储结构）
由于图的结构比较复杂，任意两个顶点都可能存在联系，因此图没有顺序存储结构，但可以借助二维数组即邻接矩阵表示法来表示元素之间的关系，自然也有用链式存储表示图，图的链式存储有多种，有邻接表，十字链表和邻接多重表，应根据实际需要的不同选择不同的存储结构。
邻接矩阵
//图的邻接矩阵存储表示
#define MaxInt 32767 //表示极大值，即∞ （基本整型变量数据范围是-32768～32767）
#define MVNum 100 //最大顶点数
typedef char VerTexType; //假设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型
typedef struct
{
VetTexType vexs[MvNum];//顶点表
ArcType arcs[MvNum][MvNum];//邻接矩阵
int vexnum,arcnum; //图的当前点数和边数
}AMGraph;
采用邻接矩阵表示法创建无向网（带权的图）
Status CreateUDN(AMGraph &G)
{
cin>>G.vexnum>>G.arcnum;//输入总顶点数和总边数
for(i=0;i<G.vexnum;++i)
cin>>G.vexs[i];
for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j)
G.arcs[i][j]=MaxInt;//给每一条边赋予最大权值，若要建立无向图，则将权值均初始化为0
for(k=0;k<G.arcnum;++k)//构造邻接矩阵
{
cin>>v1>>v2>>w;//输入一条边依附的顶点以及权值
i=LocateVex(G,v1);j=LocateVex(G,v2);//LocateVex函数为获取v1,v2顶点数组下标的函数
G.arcs[i][j]=w;//边<v1,v2>的权值置为w，若要建立无向图，将权值改为常量1即可
G.arcs[j][i]=G.arcs[i][j];//将边<v1,v2>的对称边的权值置为w
}
return OK;
}
【算法分析】
（1）时间复杂度：O(n的平方）
（2）空间复杂度高。如果是有向图，n个顶点需要n平方个单元存储边，如果是无向图，因其邻接矩阵是对称的，所以对规模较大的邻接矩阵可以采用仅存储下三角或上三角的元素，需要n(n-1)/2个单元即可。无论以那种方式，这种表示法的空间复杂度都为O(n的平方），这对于稀疏图而言浪费空间。
//图的邻接表表示
#define MVNum 100 //最大顶点数
typedef struct ArcNode //边结点
{
int adjvex;//该边所指向的顶点的位置
struct ArcNode *nextarc;//指向下一条边的指针
OtherInfo info;//和边相关的其他信息,将边的权值存储在其中，即可创建网
}ArcNode;
typedef struct VNode //顶点信息
{
VerTexType data;
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型
typedef struct
{
AdjList vertice;
int vexnum,arcnum; //图的当前顶点数和边数
}ALGraph;
采用邻接表表示法创建无向图
Status CreateUDG(ALGraph &G)
{
cin>>G.vexnum>>G.arcnum;
for(i=0;i<G.vexnum;++i)
{
cin>>G.vertices[i].data; //输入顶点值
G.vertices[i].firstarc=NULL;//初始化表头结点的指针域为NULL
}
for(k=0;k<G.arcnum;++k)//输入各边建立邻接表
{
cin>>v1>>v2;
i=LocateVex(G,v1);j=LocateVex(G,v2);
p1=new ArcNode;//生成一个新的边结点*p1
p1->adjvex=j;//邻接点序号为j
p1->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p1;
//将新结点插入顶点vi的边表头部（类似于链表的插入，先连后继再连前驱）
p2=new ArcNode;
p2->adjvex=i;
//邻接点序号为i，若是建立有向图则只需要建立前面一个序号为j的表结点即可，后面不用建立序号为i的边表结点
p2->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p2;
}
return OK;
}
【算法分析】
算法的时间复杂度为：O(n+e)
空间复杂度：O(n+e),适合稀疏图
对于无向图，其邻接表表示有n个顶点表结点，2e个边表结点；对于有向图，则它的邻接表与逆邻接表表示有n个顶点表结点，e个边表结点。
优缺点对比：
邻接矩阵表示的优点：
（1）便于判断两个顶点是否有边
（2）便于计算各个顶点的度
缺点：
（1）不利于增删结点
（2）不便于统计边的数目
邻接表表示的缺点：
（1）不便于判断两个顶点是否有边
（2）不便于计算各个顶点的度
优点：
（1）利于增删结点
（2）便于统计边的数目
