图的基本操作
- Adjacent(G, x, y) 判断图G是否存在边
- Neighbors(G, x) x的全部边
- InsertVertex(G, x) 在图G中插入顶点x
- DeleteVertex(G, x) 从图G中删除顶点x
- AddEdge(G, x, y) 若无向边(x, y)或有向边不存在，则向图G中添加该边。
- RemoveEdge(G, x, y) 若无向边(x, y)或有向边存在，则从图G中删除该边。
- FirstNeighbor(G, x) 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点 或图中不存在x，则返回-1。
- NextNeighbor(G, x, y) 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
- Get_edge_value(G, x, y) 获取图G中边(x, y)或对应的权值。以及Set_edge_value(G, x, y, v)
图的广度优先遍历BFS
利用队列和FirstNeighbor(G, x) NextNeighbor(G, x, y)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| void BFSTraverse(G)
{
for (int i = 0; i<G.vexnum; ++i)
{
G.visited[i] = false;
}
InitQueue(Q);
for (int i = 0; i<G.vexnum; ++i)
{
if (!G.visited[i])
{
BSF(G, i);
}
}
}
void BSF(G, x)
{
visit(G, x);
G.visited[x] = true;
Enqueue(Q, x);
while (!isEmpty(Q))
{
DeQueue(Q,v);
for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
{
if (G.visited[w])
{
continue;
}
visit(w);
G.visit[w] = true;
EnQueue(Q, w)
}
}
}
|
图的深度优先遍历DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| void DFSTraverse(G)
{
for (int i = 0; i<G.vexnum; ++i)
{
G.visited[i] = false;
}
for (int i = 0; i<G.vexnum; ++i)
{
if (!G.visited[i])
{
DSF(G, i);
}
}
}
void DFS(G,x)
{
visit(x);
G.visited[x] = true;
for (w = FirstNeighbor(G, x); w >= 0; w = NextNeighbor(G, v, w))
{
if (G.visited[w])
{
continue;
}
DFS(G,w);
}
}
|