数据结构-图

线性结构 1:1,树形结构 1:N,图形结构 N:N

图定义

图存储

邻接矩阵

邻接矩阵,益存储稠密图。但是现实总稀疏图较多,用邻接矩阵存储浪费空间

邻接表


邻接表存储,不会浪费空间。计算入度简单,但是计算出度复杂
通常计算顶点出度时,通常会用逆邻接表

有向图十字链表


无向图多重邻接表

图遍历

深度优先算法

遍历原则:从图中某一指定顶点v出发,先访问v,然后从该顶点的未被访问过的邻接顶点w出发,进行深度优先搜索。直到图中与v相通的所有顶点都被访问。若图中还存在未被访问过的顶点,则以这个未被访问的顶点重复上述过程。
白话:找一个顶点,遍历其邻接顶点,在遍历邻接顶点的邻接节点。


1
2
3
4
5
6
7
8
9
10
11
12
13
void DFS(VLink G[], int v) {
int w;
VISIT(v); //访问顶点v
visited[v] = 1; // 将顶点v对应的访问标记为1
w = FIRSTADJ(G, v); // 求v的第一个邻接点,若无邻接点,则返回-1

while (w != -1) {
if (visited[i] == 0) {
DFS(G, w); // 递归遍历
}
w = NEXTADJ(G, w); // 求v的下一个邻接点,若无邻接点,则返回-1
}
}

广度优先算法

遍历原则:从图中指定顶点v触发,访问v以后再依次访问v的各个未被访问的邻接点。然后从这些邻接点出发,按照同样原则依次访问它们的未被访问过的邻接点…。若此时图中还存在未被访问的顶点,则从另一个未被访问的顶点出发,继续上述过程。
白话:先访问指定出发点,然后依次访问该顶点的所有未被访问过的邻接点,再接下来访问邻接点的未被访问过的邻接点。(需要队列实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void BFS(VLink G[], int v) {
int w;
VISIT(v); // 访问顶点v
visited[v] = 1; // 将顶点v对应的访问标位1
ADDQ(Q, v); // 将v添加到队列中
while (!EMPTY(Q)) {
v = DEL(Q); // 退出队头元素v
w = FIRSTADJ(G, v); // 求v的第1个邻接点,无邻接点返回-1
while (w != -1) {
if (visited[w]) {
continue;
}
VISIT(w); //访问顶点w
ADDQ(Q, w); // 当前被访问过的顶点w入队
visited[w] = 1; // 顶点w对应的访问标记为1
w = NEXTADJ(G, v); //求v的下一个邻接点,无邻接点,返回-1
}
}
}

xpisme wechat
微信号