图的存储结构主要分两种,一种是邻接矩阵,一种是邻接表。

基本概念

邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。
下图就是一个无向图的邻接矩阵

无向图的邻接矩阵
无向图的邻接矩阵

从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。
从这个矩阵中,很容易知道图中的信息。
(1)要判断任意两顶点是否有边无边就很容易了;
(2)要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;
(3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点;

下图是一个有向图的邻接矩阵

有向图的邻接矩阵
有向图的邻接矩阵

顶点数组为vertex[4]={v0,v1,v2,v3},弧数组arc[4][4]为上图的矩阵。
主对角线上数值依然为0.但因为是有向图,所以此矩阵并不对称,比如从v1到v0有弧,得到arc[1][0]=1,而v0到v1没有弧,因此arc[0][1]=0。有向图论入度和出度,顶点v1的入度为1,正好是第v1列上的数之和。顶点v1的出度为2,即第v1行的各数之和。与无向图同样的办法,判断顶点vi到vj是否存在弧,只需要查找矩阵中arc[i][j]是否为1即可。要想知道vi的所有邻接点就是将矩阵第i行元素扫描一遍,查找arc[i][j]为1的顶点。

邻接表

对于边数相对顶点较少的图,邻接矩阵对存储空间的极大浪费。
邻接表的处理方法是这样的:
(1)图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过,数组可以较容易的读取顶点的信息,更加方便。 另外,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息。
(2)图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表。

下图是一个无向图的邻接表结构

无向图邻接表
无向图邻接表

从图中我们知道,顶点表的各个结点由data和firstedge两个域表示,data是数据域,存储顶点的信息。firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个结点的指针,比如v1顶点与v0、v2互为邻接点,则在v1的边表中,adjvex分别为v0的0和v2的2.如果想知道某个顶点的度,就去查找这个顶点的边表中结点的各数。若要判断顶点vi和vj是否存在边,只需要测试顶点vi的边表adjvex中是否存在结点vj的下标就行了。若求顶点的所有邻接点,其实就是对此顶点的边表进行遍历,得到的adjvex域对应的顶点就是邻接点。

两种基本结构

邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MAXV 100 //最大顶点个数
#define INF 32767 //INF表示∞
//邻接矩阵
typedef struct {
int no;//顶点编号
int info;//顶点其他信息,可存放带权图的权值
}VertexType; //顶点类型

typedef struct {
int edges[MAXV][MAXV]; //邻接矩阵
int n, e;//顶点数,边数
VertexType vexs[MAXV];//顶点表
}MGraph;

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//边表结点
typedef struct EdgeNode {
int adjvex;//该弧的终点位置
struct EdgeNode *nextarc;//指向下一条弧的指针
int info;//该弧的相关信息,存放权值
}EdgeNode;
//顶点表节点
typedef int Vertex;
typedef struct VextexNode {
Vertex data;//顶点信息
int count; //顶点的入度
bool visited;//表示该节点是否被访问
EdgeNode *firstEdge;//指向第一条弧
}VextexNode,AdjList[MAXV];
//邻接表
typedef struct {
AdjList adjList;//邻接表
int n, e;//图中顶点数和边数
}ALGraph;

用普通数组构造图的邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
void arrayToMat(int *arr, int n, MGraph &g) {
int i, j, count = 0;//count用于统计边数,即矩阵中非0元素的个数
g.n = n;
for (i = 0; i < g.n; ++i) {
for (j = 0; j < g.n; ++j) {
g.edges[i][j] = arr[i*n + j];//将Arr看作n×n的二维数组,Arr[i*n+j]即是Arr[i][j],计算存储位置的功夫在此应用
if (g.edges[i][j] != 0 && g.edges[i][j] != INF) {
++count;
}
}
}
g.e = count;
}

用普通数组构造图的邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void arrayToList(int* arr, int n, ALGraph &g) {
int i, j, count = 0;
g.n = n;
EdgeNode *ep;
//输入顶点信息,将边表置为0
for (i = 0; i < g.n; ++i) {
g.adjList[i].data = i;
g.adjList[i].firstEdge = nullptr;
}
//建立边表
for (i = 0; i < n; ++i) {//检查邻接矩阵中每个元素
for (j = n - 1; j >= 0; --j) {
if (arr[i*n + j] != 0) { //存在一条边,将Arr看作n×n的二维数组,Arr[i*n+j]即是Arr[i][j]
ep = (EdgeNode*)malloc(sizeof(EdgeNode));//创建一个节点*ep
ep->adjvex = j;
ep->info = arr[i*n + j];
ep->nextarc = g.adjList[i].firstEdge;//采用头插法插入*ep
g.adjList[i].firstEdge = ep;
++count;
}
}
}
g.e = count;
}

邻接矩阵转邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void MatToList(MGraph g, ALGraph &G) {
int i, j;
EdgeNode* ep;
for (i = 0; i < g.n; ++i) {
G.adjList[i].firstEdge = nullptr;
}
for (i = 0; i < g.n; ++i) {
for (j = g.n - 1; j >= 0; --j) {
if (g.edges[i][j] != 0) {
ep = (EdgeNode*)malloc(sizeof(EdgeNode));
ep->adjvex = j;
ep->info = g.edges[i][j];
ep->nextarc = G.adjList[i].firstEdge;
G.adjList[i].firstEdge = ep;
}
}
}
G.n = g.n;
G.e = g.e;
}

邻接表转邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void ListToMat(ALGraph G, MGraph &g) {
int i, j;
EdgeNode *ep;
g.n = G.n;
g.e = G.e;
for (i = 0; i < G.n; ++i) {
for (j = 0; j < G.n; ++j) {
g.edges[i][j] = 0;
}
}
for (i = 0; i < G.n; ++i) {
ep = G.adjList[i].firstEdge;
while (ep) {
g.edges[i][ep->adjvex] = ep->info;
ep = ep->nextarc;
}
}
}

输出邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dispMat(MGraph g) {
int i, j;
for (i = 0; i < g.n; ++i) {
for (j = 0; j < g.n; ++j) {
if (g.edges[i][j] == INF) {
cout << "∞ ";
}
else {
cout << g.edges[i][j] << " ";
}
}
cout << endl;
}
}

输出邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
void dispAdj(ALGraph g) {
int i;
EdgeNode* ep;
for (i = 0; i < g.n; ++i) {
ep = g.adjList[i].firstEdge;
cout << i << ":";
while (ep) {
cout << "->" << ep->adjvex << "/" << ep->info;
ep = ep->nextarc;
}
cout << endl;
}
}

初始化邻接表节点的访问

初始化为0,表示还没有被访问过

1
2
3
4
5
void initVisted(ALGraph &G) {
for (int i = 0; i < G.n; ++i) {
G.adjList[i].visited = 0;
}
}

图的宽度搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void BFS(ALGraph G, int start, vector<int>& v) {
queue<int> q;
q.push(start);
G.adjList[start].visited = 1;

while (!q.empty()) {
int current = q.front();
q.pop();
v.push_back(current);
EdgeNode *ep;
ep = (EdgeNode*)malloc(sizeof(EdgeNode));
ep = G.adjList[current].firstEdge;//ep指向头结点,遍历边表
while (ep) {
if (!G.adjList[ep->adjvex].visited) {
q.push(ep->adjvex);
G.adjList[ep->adjvex].visited = 1;
}
ep = ep->nextarc;
}
}
}

图的深度搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void DFS(ALGraph G, int start, vector<int>& v) {
stack<int> s;
s.push(start);
G.adjList[start].visited = 1;
v.push_back(start);
while (!s.empty()) {
int current = s.top();
s.pop();
EdgeNode *ep;
ep = (EdgeNode*)malloc(sizeof(EdgeNode));
ep = G.adjList[current].firstEdge;
while (ep) {
if (!G.adjList[ep->adjvex].visited) {
s.push(current);
s.push(ep->adjvex);
G.adjList[ep->adjvex].visited = 1;
v.push_back(ep->adjvex);
break;
}
ep = ep->nextarc;
}
}
}