1.图的表示
a.邻接矩阵:适合稠密图(|E|接近|V|2)
//用二维数组表示邻接矩阵 int G[|V|][|V|]; //初始化 for(int i=0;i<|V|;i++){ for(int j=0;j<|V|;j++){ if( (i,j) in E){ G[i][j] = 1;//or G[i][j] = weight[i][j]; } else if(i==j){ G[i][j] = 0; } else{ G[i][j] = MAX; } } }
b.邻接表:适合稀疏图(|E|远小于|V|2)
//邻接表的表示 class Node{ public: int index;//顶点索引 Node* next=nullptr;//下一顶点 Node(int i):index(i){} }; class VNode{ public: char vertex;//顶点 int index;//顶点索引 int dist;//BFS:表示顶点到源点的距离,DFS:表示顶点第一次被发现的时间 int finish;//BFS:无意义,DFS:表示顶点的邻接表扫描完成时的时间 Color color;//顶点颜色 int prev;//顶点的前驱 Node* firstNode=nullptr;//第一条边的尾节点 VNode(char c,int i):vertex(c),index(i){} }; class Graph{ vector<VNode> Adj;//所有顶点 }; //初始化 void AddEdge(Graph &G,int i,int j,int weight,int w[][|V|]){ Node* p = new Node(j); p->next = G.Adj[i].firstNode; G.Adj[i].firstNode = p; w[i][j]=weight; //有向图只需上面部分代码即可 Node* p2 = new Node(i); p2->next = G.Adj[j].firstNode; G.Adj[j].firstNode = p2; w[j][i] = weight; } //初始化顶点 for(int i=0;i<|V|;i++){ G.Adj.push_back(VNode(V[i], i)); } //初始化边、权重 int w[6][6]; for (int i = 0; i < 6; ++i){ for (int j = 0; j < 6; ++j){ if(i == j){ w[i][j] = 0; } else{ w[i][j] = MAX; } } } for (i,j) in E: AddEdge(G,i,j,weight[i][j],w);
2.广度优先搜索BFS
思路:从某个源点开始遍历图,先将源点颜色置为灰色,然后将其加入队列Q,对Q中的元素进行如下循环操作:
1.从队列Q中弹出一个元素u 2.访问与u相邻的每个顶点v,若v的颜色为白色(未被发现) 则将v的颜色置为灰色 v与源点的距离更新为u到源点距离加1 v的前驱更新为u 将v压入队列Q 3.u的邻接表扫描完成,将u的颜色置为黑色
直至Q为空.
伪代码:
BFS(G,s) for each vertex u in G.V u.color = white u.d = MAX u.p = NIL s.color = gray s.d = 0 s.p = NIL Q = ∅ ENQUEUE(Q,s) while Q ≠ ∅ u = DEQUEUE(Q) for each v in G.Adj[u] if v.color == white v.color = gray v.d = u.d+1 v.p = u ENQUEUE(Q,v) u.color = black
时间复杂度:O(V+E)
打印源节点s到结点v的一条路径上的所有节点
PrintPath(G,s,v) if v==s print s else if v.p == NIL print "No such path" else PrintPath(G,s,v.p) print v
对于每个从源结点s可以到达的结点v,广度优先搜索里从结点s到结点v的简单路径就是图G中从结点s到结点v的"最短路径",即包含最少边数的路径.
3.深有优先搜索DFS
思路:对每一个顶点u,若u的颜色为白色,则对u进行深度优先访问(DFS-VISIT)
1.全局时间戳time加1,u被发现的时间更新为time,u的颜色更新为灰色 2.访问与u相邻的每个顶点v,若v的颜色为白色(未被发现) v的前驱更新为u 对v进行深度优先访问 3.u的邻接表扫描完成,u的颜色置位黑色,time加1,u的邻接表扫描完成时间更新为time
一次深度优先访问可能无法访问到所有顶点,这正是要对每个顶点进行深度优先访问的原因.
伪代码:
DFS(G) for each vertex u in G.V u.color = white u.p = NIL time = 0 for each vertex u in G.V if u.color == white DFS-VISIT(G,u) DFS-VISIT(G,u) time = time +1//u has just been discovered u.d = time u.color = gray for each v in G.Adj[u]//explore edge(u,v) if v.color == white v.p = u DFS-VISIT(G,v) u.color = black//blacken u,it is finished time = time +1 u.f = time
时间复杂度:O(V+E)
BFS和DFS的区别:
BFS的前驱子图是一棵树,DFS的前驱子图是有多颗树组成的深林.
结点颜色的含义:
初始时未被发现是白色,被发现后为灰色,其邻接表被扫描完成后为黑色.
遍历路径:
若要得到图的遍历顺序,可在结点被访问后保存到一个向量.