数据结构之图形结构（C++）
图的基本定义
*图（Graph）G有两个集合V和E组成，记为G=（V，E），其中V是顶点的有穷⾮空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。V(G)和E(G)通常分别表⽰图G的顶点集合和边集合，E(G)可以为空集。若E(G)为空，则图G只有顶点⽽没有边。 对于图G，若边集E(G)为有向边的集合，则称该图为有向图，反之，则称为⽆向图。*
图的基本术语
⼦图：*假设有两个图G=（V,E)和G‘=（V’,E’)，如果V’属于V且E’属于E，则称G"为G的⼦图。类似于数学中的集合。
⽆向完全图和有向完全图: 对于⽆向图，若具有n(n-1)/2条边，则称为⽆向完全图 。对于有向图，若具有n(n-1)条弧，则称**有向完全图
***。
稀疏图和稠密图：有很少条边或弧的图称为***稀疏图***，反之称为***稠密图***。
权和⽹：在实际应⽤中，每条边可以标上具有某种含义的数值，该数值称为该边上的权，这些权可以表⽰从⼀个顶点到另⼀个顶点的距离或耗费。这些带权的图通常称为⽹。
度：顶点的度指的是和其相关联的边的数⽬。
这些基本的东西简单理解就⾏。
最主要的就是如何构造图型结构。
以下是图的存储结构
1.【邻接矩阵表⽰法】
邻接矩阵：表⽰顶点之间相邻关系的矩阵。
其形式说明如下:
//-----------图的邻接矩阵存储表⽰----------
#define MaxInt 32767 //表⽰极⼤值
#define MVNum 100 //最⼤顶点数
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整形
typedef struct
{
VerTexType vexs[MVNum];//顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum,arcnum;//图的当前点数和边数
}AMGraph;
采⽤邻接矩阵表⽰法创建⽆向⽹
2.【算法步骤】
1）输⼊总顶点数和边数
3）初始化邻接矩阵，使每个权值初始化为极⼤值
4）构造邻接矩阵。依次输⼊每边依附的顶点和权值
算法描述
//⽆向图
void CreateUDN(AMGraph &G)
{
cout<<"输⼊总顶点数:";
cin>>G.vexnum;
cout<<"输⼊总边数:";
cin>>G.arcnum;
for(int i=0;i<G.vexnum;i++)
{
cout<<"第"<<i+1<<"顶点信息:";
cin>>G.vexs[i];
}
for(int i=0;i<G.arcnum;i++)
for(int j=0;j<G.arcnum;j++)
G.arcs[i][j]=MaxInt;//初始化邻接矩阵，边的权值均置为极⼤值
for(int k=0;k<G.arcnum;k++)
{
cout<<k+1<<"输⼊两边顶点及权值:"<<endl;
int v1,v2,w;
cin>>v1>>v2>>w;
G.arcs[v1][v2]=w;//边<v1，v2>的权值置为w
G.arcs[v2][v1]=G.arcs[v1][v2];//置<v1，v2>的对称边<v2，v1>的权值为w
}
}
【算法分析】
该算法的时间复杂度是O(n^2)。
若要建⽴有向图，只需对上述算法做⼀处⼩改动：删掉最后⼀个for循环的最后⼀步。
3.【邻接矩阵表⽰法的优缺点】
优点:
该边1）便于判断两个顶点是否有边，即根据A[i][j]=0/1来判断。
2）便于计算各个顶点的度。
缺点:
1）不便于增加和删除顶点
2）不便于统计边的数⽬
3）空间复杂度⾼
下⾯介绍的邻接表将将邻接矩阵的n⾏改成n个单链表，适合稀疏图
邻接表
1.【邻接表表⽰法】
邻接表：是图的⼀种链式存储结构，邻接表中每个单链表的第⼀个结点存放有关顶点的信息，把这⼀结点看成链表的表头，其余结点存放有关边的信息，这样邻接表便由两部分组成：表头结点表和边表 1）表头结点：由所有表头结点以顺序结构的形式存储，以便可以访问任⼀顶点的边链表。表头结点包括数据域和链域两部分，其中，数据域⽤于存储顶点的名称和其他有关信息；链域⽤于指向链表中的第⼀个结点（即与顶点邻接的第⼀个邻接点）。
2）边表：边链表中边结点包括邻接点域(adjvex)，数据域(info)，链域(nextarc)三部分，其中，邻接点域指⽰与顶点邻接的点在图中的位置；数据域存储边相关的信息，如权值等；链域指⽰与顶点邻接的下⼀条边的结点。
图的邻接表存储结构说明如下:
//-----------图的邻接表存储表⽰----------
#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 vertices;
int vexnum,arcnum;//图的当前顶点数和边数
}ALGraph;
2.采⽤邻接表表⽰法创建⽆向图
【算法步骤】
1）输⼊总顶点数和边数
2）依次输⼊点的信息存⼊顶点表中，使每个表头结点的指针域初始化为NULL
3）创建邻接表
【算法描述】
void CreateGraphAdjList(GraphAdjList &G)
{
ArcNode *e;
cin>>G.numvertex;//输⼊当前图的边数
cin>>G.numarc;//输⼊当前图的顶点数
for(int i=0;i<G.numvertex;i++)
{
cin>>G.adjlist[i].data;//输⼊顶点信息
G.adjlist[i].firstarc=NULL;//将表头置为空
}
for(int k=0;k<G.numarc;k++)
{
int i,j,w;
cin>>i>>j>>w;//输⼊两边的顶点和权值
e=new ArcNode;
e->adjvex=j;
e->weight=w;
e->next=G.adjlist[i].firstarc;
G.adjlist[i].firstarc=e;
//因为是⽆向图，彼此相对称
e=new ArcNode;
e->adjvex=i;
e->weight=w;
e->next=G.adjlist[j].firstarc;
G.adjlist[j].firstarc=e;
}
}
【算法分析】
该算法的时间复杂度是O(n+e)。
建⽴有向图的邻接表与此类似，只是更简单了，每读⼊⼀个顶点序号<i,j>，仅需⽣成⼀个邻接点序号为j的边表结点，并将其插⼊到Vi的边链表头部计科。
3.【邻接表表⽰法的优缺点】
优点：
1）便于增加和删除顶点
2）便于统计边的数⽬，按顶点表顺序扫描所有边表可得到边的数⽬，时间复杂度O(n+e)。3）空间效率⾼
缺点
1）不便于判断顶点之间是否有边
2）不便于计算有向图1各个顶点的度
希望这些内容对你们有所帮助。
下期介绍⼗字链表和邻接多重表
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议