1. 图的存储结构——所存储的信息有哪些
一、邻接矩阵存储方法
邻接矩阵是表示顶点之间相邻关系的矩阵。
设G=(V，E)是具有n（n＞0）个顶点的图，顶点的顺序依次为0～n-1，则G的邻接矩阵A是n阶方阵，其定义如下：
（1）如果G是无向图，则：
A[i][j]=1：若(i,j)∈E(G) 0:其他
（2）如果G是有向图，则：
A[i][j]=1：若<i,j>∈E(G) 0:其他
（3）如果G是带权无向图，则：
A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他
（4）如果G是带权有向图，则：
A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j∞：其他
注意：带权图和不带权图表示的元素类型不同。
带权图（不论有向还是无向图）A[i][j]用double表示，不带权图（不论有向还是无向图）A[i][j]用int表示。
用一维数组G[ ]存储有4个顶点的无向图如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
则顶点2和顶点0之间是有边的。
如：
邻接矩阵的特点如下：
（1）图的邻接矩阵表示是唯一的。
（2）无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上（或下）三角形阵的元素即可。
（3）不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵。因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。
（4）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。
（5）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。
（6）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。
邻接矩阵的数据类型定义如下：
#define MAXV <最大顶点个数>
typedef struct
{ int no; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct //图的定义
{ int edges[MAXV][MAXV]; //邻接矩阵
int n，e; //顶点数，弧数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵表示类型
二、 邻接表存储方法
图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。
在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。
其中，表节点由三个域组成，adjvex指示与顶点i邻接的点在图中的位置，nextarc指示下一条边或弧的节点，info存储与边或弧相关的信息，如权值等。
表头节点由两个域组成，data存储顶点i的名称或其他信息，firstarc指向链表中第一个节点。
typedef struct ANode
{ int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
InfoType info; //该边的相关信息
} ArcNode; //边表节点类型
typedef struct Vnode
{ Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
} VNode; //邻接表头节点类型
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct
{ AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} ALGraph; //完整的图邻接表类型
邻接表的特点如下：
（1）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。
（2）对于有n个顶点和e条边的无向图，其邻接表有n个顶点节点和2e个边节点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。
（3）对于无向图，邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。
（4）对于有向图，邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。
例， 给定一个具有n个节点的无向图的邻接矩阵和邻接表。
（1）设计一个将邻接矩阵转换为邻接表的算法；
（2）设计一个将邻接表转换为邻接矩阵的算法；
（3）分析上述两个算法的时间复杂度。
解：
（1）在邻接矩阵上查找值不为0的元素，找到这样的元素后创建一个表节点并在邻接表对应的单链表中采用前插法插入该节点。
void MatToList(MGraph g，ALGraph *&G)
//将邻接矩阵g转换成邻接表G
{ int i，j，n=g.n; ArcNode *p; //n为顶点数
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<n;i++) //给所有头节点的指针域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++) //检查邻接矩阵中每个元素
for (j=n-1;j>=0;j--)
if (g.edges[i][j]!=0)
{ p=(ArcNode *)malloc(sizeof(ArcNode));
//创建节点*p
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;
//将*p链到链表头
G->adjlist[i].firstarc=p;
}
G->n=n;G->e=g.e;
}
（2）在邻接表上查找相邻节点，找到后修改相应邻接矩阵元素的值。
void ListToMat(ALGraph *G，MGraph &g)
{ int i，j，n=G->n;ArcNode *p;
for (i=0;i<n;i++)
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ g.edges[i][p->adjvex]=1;
p=p->nextarc;
}
}
g.n=n;g.e=G->e;
}
（3）算法1的时间复杂度均为O(n2)。算法2的时间复杂度为O(n+e)，其中e为图的边数。
2. 有向图的邻接表存储如图所示，请画出其邻接矩阵存储结构
有向图的邻接表存储如图所示，其邻接矩阵存储如图：
3. 怎样用邻接矩阵为存储结构创建一个无向图
int CreateUDG(AdjMatrix *G){
int i,j,k,weight;
VertexData v1,v2;
printf("输入图的弧数和顶点数\n");
fflush(stdin);
scanf("%d,%d",&G->arcnum,&G->vexnum); /*输入图的顶点数和弧数*/
for(i=0;i<G->vexnum;i++) /*初始化邻接矩阵*/
for(j=0;j<G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
for(i=0;i<G->vexnum;i++)
{
printf("输入图的顶点\n");
fflush(stdin);
scanf("%c",&G->vexs[i]); /* 输入图的顶点*/
}
for(k=0;k<G->arcnum;k++)
{
printf("输入一条弧的两个顶点及权值\n");
fflush(stdin);
scanf("%c,%c,%d",&v1,&v2,&weight);/*输入一条弧的两个顶点及权值*/
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
G->arcs[i][j].adj=weight; /*建立弧*/
}
return(Ok);
}
void main()
{
AdjMatrix G;
CreateDN(&G);
}
4. 图的基本概念，图的存储--邻接矩阵、邻接表、十字链表、邻接多重表
一个图(G)定义为一个偶对(V,E)，记为G=(V,E)。
V是顶点(Vertex)的非空有限集合，记为V(G)。
E是无序集V&V的一个子集，记为E(G)，其元素是图的弧(Arc)。
将顶点集合为空的图称为空图。
弧：表示两个顶点v和w之间存在一个关系，用顶点偶对<v,w>表示。
(1)无向图:
在一个图中，如果任意两个顶点构成的偶对(v,w)∈E 是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。
(2)有向图:
在一个图中，如果任意两个顶点构成的偶对(v,w)∈E 是有序的，即顶点之间的连线是有方向的，则称该图为有向图。一般记作<v,w>
(3)完全无向图:
在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为完全无向图。在一个含有 n 个顶点的完全无向图中，有n(n-1)/2条边。
(4)完全有向图:
在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为完全有向图。在一个含有 n 个顶点的完全有向图中，有n(n-1)条边。
(5)稠密图、稀疏图:
若一个图接近完全图，称为稠密图;称边数很少( )的图为稀疏图。
(6)顶点的度、入度、出度:
顶点的度(degree)是指依附于某顶点 的边数，通常记为TD( )。
在无向图中，所有顶点度的和是图中边的2倍。
在有向图中，要区别顶点的入度(Indegree)与出度(Outdegree)的概念。
顶点 的入度是指以顶点为终点的弧的数目，记为ID ( );
顶点 出度是指以顶点 为始点的弧的数目，记为 OD( )。
顶点 的出度与入度之和称为 的度，记为TD( )。即TD( )=OD( )+ID ( )。
(7)边的权、网图:
与边有关的数据信息称为权(weight)。在实际应用中，权值可以有某种含义。
边上带权的图称为网图或网络(network)。如果边是有方向的带权图，则就是一个有向网图。
(8)路径、路径长度:
对无向图，若从顶点 经过若干条边能到达 ，则称顶点 和 是连通的，又称顶点 到 有路径。
对有向图，从顶点 到 有有向路径，指的是从顶点 经过若干条有向边能到达 。
路径上边或有向边(弧)的数目称为路径长度。
(9)简单路径、回路、简单回路:
在一条路径中，若没有重复相同的顶点，该路径称为简单路径。
第一个顶点和最后一个顶点相同的路径称为回路(环)。
除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。
(10)子图和生成子图:
对于图 G=(V，E)，G’=(V’，E’)，若存在 V’是 V 的子集 ，E’是 E的子集，则称图 G’是 G 的一个子图；
若V’=V且E’是E的子集，则称图G’是G的一个生成子图。
(11)连通图、连通分量:
对无向图G=(V,E)，若任意 都是连通的，则称该图是连通图，否则称为非连通图。
若G是非连通图，则极大连通子图称为连通分量。
极大的含义：指的是对子图再增加图G中的其它顶点，子图就不再连通。
任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。
(12)强连通图、强连通分量:
对于有向图来说，若图中任意一对顶点 均有从一个顶点 到另一个顶点 有路径，也有从 到 的路径，则称该有向图是强连通图。
有向图的极大强连通子图称为强连通分量。
强连通图只有一个强连通分量，即本身。非强连通图有多个强连通分量。
(13)生成树:
一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树。
(14)生成森林:
有向树是只有一个顶点的入度为0，其余顶点的入度均为1的有向图。
有向图的生成森林是这样一个子图，由若干棵有向树组成，含有图中全部顶点。
(1)邻接矩阵法(Adjacency Matrix)
基本思想：对于有n个顶点的图，用一维数组vexs[n]存储顶点信息，用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。
在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。
1)无向图的数组表示
①无向无权图的邻接矩阵
无向无权图其邻接矩阵是n阶对称方阵。
若两条边相连,A[i][j]=1; 若不相连A[i][j]=0。
②无向带权图的邻接矩阵
若两条边相连， ，W为权值。
若两条边不相连，A[i][j]=
③无向图邻接矩阵的特性
无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放 上(或下)三角矩阵的元素即可。
对于顶点 ，其度数是第i行的非0元素(或非 元素)的个数。
无向图的边数是上（或下）三角形矩阵的非0元素(或非 元素)的个数。
2)有向图的数组表示
①有向无权图的邻接矩阵
若有向无权图G=(V,E)有n个顶点，则其邻接矩阵是n阶方阵：
若从 到 有弧，A[i][j]=1；
若从 到 没有弧，A[i][j]=0；
②有向带权图的邻接矩阵
③有向图邻接矩阵的特性
对于顶点 ，第i行的非0元素(或非 元素)的个数是其出度OD( )；
第i列的非0元素(或非 元素)的个数是其入度ID( );
邻接矩阵中非0元素(或非 元素)的个数就是图的弧的个数。
对于n个顶点e条边的无向图，邻接矩阵表示时有n n个元素，2 e个非0元素。
对于n个顶点e条边的有向图，邻接矩阵表示时有n n个元素，e个非0元素。
3)图的邻接矩阵的操作
定义两个数组分别存储顶点信息(数据元素)和边或弧的信息(数据元素之间的关系) 。
图的各种操作。
①图的创建
②图的顶点定位
实际上是确定一个顶点在 vexs 数组中的位置(下标) ，其过程完全等同于在顺序存储的线性表中查找一个数据元素。
③向图中增加顶点
向图中增加一个顶点的操作，类似在顺序存储的线性表的末尾增加一个数据元素。
④向图中增加一条弧
根据给定的弧或边所依附的顶点，修改邻接矩阵中所对应的数组元素。
(2)邻接链表法
1)基本思想：类似于树的孩子链表法，就是对于图 G 中的每个顶点 ，将所有邻接于 的顶点 链成一个单链表，这个单链表就称为顶点 的邻接链表，再将所有点的邻接表表头放到数组中，就构成了图的邻接链表。
对无向图，其邻接链表是唯一(按顺序链接)的；对有向图，其邻接链表有两种形式。
2)从图的邻接表存储方法容易看出，这种表示具有以下特点:
①表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目。
②在边稀疏的情况下，用邻接表表示图比邻接矩阵节省存储空间。
③在无向图的邻接表中，顶点 的度恰为第 i 个链表中的结点数。
④有向图可以建立一个正邻接表和逆邻接表，便于统计每个结点的出度和入度。
⑤在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点( 和 )之间是否有边或弧相连，则需搜索第 i 个或第 j 个链表，因此，不及邻接矩阵方便。
对于n个顶点e条边的无向图，邻接表表示时有n个表头结点，2 e个表结点。
对于n个顶点e条边的有向图，邻接表表示时有n个表头结点，表结点数不确定，但正邻接表加上逆邻接表表结点数为e。
3)表结点及其类型定义
图的各种操作
①图的创建
②顶点定位
图的顶点定位实际上是确定一个顶点在 AdjList 数组中的某个元素的 data 域内容。
③向图中增加顶点
向图中增加一个顶点的操作，在 AdjList 数组的末尾增加一个数据元素。
④向图中增加一条弧
根据给定弧或边所依附的顶点，修改单链表，无向图修改两个单链表;有向图修改一个单链表。
(3) 十字链表法
十字链表(Orthogonal List)是有向图的另一种链式存储结构，是将有向图的正邻接表和逆邻接表结合起来得到的一种链表。
在这种结构中，每条弧的弧头结点和弧尾结点都存放在链表中，并将弧结点分别组织到以弧尾结点为头(顶点)结点和以弧头结点为头(顶点)结点的链表中。这种结构的结点逻辑结构如图所示。
data 域:存储和顶点相关的信息;
指针域 firstin:指向以该顶点为弧头的第一条弧所对应的弧结点，即逆邻接链表;
指针域 firstout:指向以该顶点为弧尾的第一条弧所对应的弧结点，即正邻接链表;
尾域 tailvex:指示弧尾顶点在图中的位置;
头域 headvex:指示弧头顶点在图中的位置;
指针域 hlink:指向弧头相同的下一条弧;
指针域 tlink:指向弧尾相同的下一条弧;
Info 域:指向该弧的相关信息，比如权值;
结点类型定义：
下图所示是一个有向图及其十字链表(略去了表结点的 info 域)。实质就是先把图的正邻接链表(出度)画出来，然后再把firstin,firstout,hlink,tlink连起来。
(4)邻接多重表法
邻接多重表(Adjacency Multilist)是无向图的另一种链式存储结构。
邻接多重表的结构和十字链表类似，每条边用一个结点表示。
邻接多重表中的顶点结点结构与邻接表中的完全相同，而表结点包括六个域。
data 域:存储和顶点相关的信息;
指针域 firstedge:指向依附于该顶点的第一条边所对应的表结点;
标志域 mark:用以标识该条边是否被访问过;
ivex 和 jvex 域:分别保存该边所依附的两个顶点在图中的位置;
info 域:保存该边的相关信息;
指针域 ilink:指向下一条依附于顶点 ivex 的边;
指针域 jlink:指向下一条依附于顶点 jvex 的边;
结点类型定义:
邻接多重表与邻接表的区别:后者的同一条边用两个表结点表示，而前者只用一个表结点表示;除标志域外，邻接多重表与邻接表表达的信息是相同的，因此，操作的实现也基本相似。
5. 存储结构为邻接矩阵，怎么编写无向图添加、删除一个顶点，添加、删除一条边的算法
邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。
/* MGraph.cc: 图的邻接矩阵存储表示和实现 */
/* 包含图类型Graph定义；创建图；深度优先遍历；广度优先遍历 */
/* 用到引用型参数，在TC下无法通过编译，VC等C++编译器可通过 */
#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX
#define VType char //顶点值类型
#define EType int //边权值类型
#define MAXVNUM 50 //最大顶点个数
#define DIGRAPH 0 //有向图(网)
#define UNDIGRAPH 1 //无向图(网)
#define INVALID INT_MAX //无效权值(最大整数表示无穷大)
#define EMPTY -1 //"空"顶点序号
6. 试以邻接矩阵为存储结构，写出连通图的深度优先搜索算法。
/* MGraph.cc: 图的邻接矩阵存储表示和实现 */
/* 包含图类型Graph定义；创建图；深度优先遍历；广度优先遍历 */
/* 用到引用型参数，在TC下无法通过编译，VC等C++编译器可通过 */
#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX
#define VType char //顶点值类型
#define EType int //边权值类型
#define MAXVNUM 50 //最大顶点个数
#define DIGRAPH 0 //有向图(网)
#define UNDIGRAPH 1 //无向图(网)
#define INVALID INT_MAX //无效权值(最大整数表示无穷大)
#define EMPTY -1 //"空"顶点序号
//定义邻接矩阵表示的图类型Graph:
typedef struct
{
VType v[MAXVNUM]; //顶点序列(顶点编号从0开始)
EType w[MAXVNUM][MAXVNUM]; //邻接矩阵
int vn, en; //顶点数,边数
int kind; //图的种类：=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)
}Graph;
int visited[MAXVNUM]; //访问标志数组(=1已访问，=0未访问)。遍历时用到的全局量。
/* 创建图G
参数Vex是存放顶点序列的数组
参数VVW是整数数组，以{Vi,Vj,Wij,...,-1}的形式依次存放各边的起止点序号(Vi,Vj)和权(Wij)，-1是数据结束标志
参数kind=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)
*/
void CreateGraph(Graph &G, VType *Vex, int VVW[], int kind)
{
int i, j, p, n, w;
n = strlen(Vex);
G.vn = n; //顶点数
G.kind = kind; //图的种类
//置顶点序列:
for (i = 0; i < n; i++)
G.v[i] = Vex[i];
//初始化邻接矩阵:
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
G.w[i][j] = INVALID;
//构造邻接矩阵:
p = 0; //VVW数组元素“指针”
n = 0; //边计数器
while (VVW[p] != -1)
{//只要p未到结束位置便继续:
i = VVW[p]; //边的起点序号
j = VVW[p + 1]; //边的终点序号
w = VVW[p + 2]; //边的权
G.w[i][j] = w; //置邻接矩阵的(i,j)位置元素
if (G.kind == UNDIGRAPH) //若是无向图(网),
G.w[j][i] = G.w[i][j]; //则置(i,j)的对称位置(j,i)
n++; //边计数器加1
p += 3; //p指向下一组(Vi,Vj,Wij)
}//end while
G.en = n; //边数
}//CreateGraph
/* 返回G中顶点i的一个未曾访问过的邻接点(序号) */
int NextAdjVex(Graph &G, int i)
{
int j, a;
a = EMPTY; //邻接点序号初始为"空"
//在邻接矩阵的第v行找有效元素：
for (j = 0; j < G.vn; j++)
{
if (G.w[i][j] == INVALID) //若当前元素是无效元素,
continue; //则继续找。
if (!visited[j])
{//若当前有效元素未曾访问过,则作为邻接点a:
a = j;
break;
}//end if
}//end for
return a;
}//NextAdjVex
/* 访问顶点i */
void visit(Graph &G, int i)
{
printf("%c", G.v[i]);
}//visit
/* 从第i个顶点出发深度优先遍历连通图G */
/* 调用DFS前可能需初始化数组visited[] */
void DFS(Graph &G, int i)
{int a;
visit(G, i); //访问i顶点
visited[i] = 1; //标注i顶点已访问
a = NextAdjVex(G, i); //找出一个i的邻接点a
while (a != EMPTY)
{//只要a存在便继续:
if (visited[a] == 0) //若a未曾访问,
DFS(G, a); //则从a出发继续进行深度优先遍历。
a = NextAdjVex(G, i); //找出i的下一个邻接点a
}//end while
}//DFS
/* 从第i个顶点出发深度优先遍历图G */
void DFSTrav(Graph &G, int i)
{int k;
//初始化各顶点的访问标志为0(未曾访问):
for (k = 0; k < G.vn; k++)
visited[k] = 0;
DFS(G, i); //从i出发遍历
//若G非连通图，执行一次DFS无法遍历所有顶点，还需用如下for对尚未访问的顶点DFS。
//若G是连通图，执行一次DFS就已遍历所有顶点，此时如下for什么也不做，因所有visited=1。
for (k = 0; k < G.vn; k++)
if (!visited[k]) DFS(G, k); //对尚未访问的顶点DFS
}//DFSTrav
//显示图的邻接矩阵
void ShowM(Graph &G)
{
int row, col, n;
n = G.vn; //顶点数
//以表格形式输出数组：
//输出表头：
printf(" ");
for(col = 0; col < n; col++)
printf("%3d",col);
printf("\n");
printf("---+");
for(col = 0; col < n; col++)
printf("---");
printf("\n");
//输出表体(矩阵元素)：
for(row = 0; row < n; row++)
{
printf("%3d|", row);
for(col = 0; col < n; col++)
{
if (G.w[row][col] == INVALID)
printf("%3c", '*');
else
printf("%3d", G.w[row][col]);
}//end for col
printf("\n");
}//end for row
printf("\n");
}//ShowM