算法系列筆記6(有關圖的算法一―搜索，拓撲排序和強連通分支)
來源：程序員人生 發布時間：2015-03-13 07:56:54 閱讀次數：3875次
簡單概念：對圖G(V,E)，通常有兩種存儲的數據結構，1種是鄰接矩陣，此時所需要的存儲空間為O(V^2)；第2種是鄰接表，所需要的存儲空間為O(V+E)。鄰接表表示法存在很強的適應性，但是也有潛伏的不足，當要快速的肯定圖中邊(u,v)是不是存在，只能在頂點u的鄰接表中搜索v，沒有更快的方法，此時就能夠使用鄰接矩陣，但要以占用更多的存儲空間作為代價；另外當圖不是加權的，采取鄰接矩陣存儲還有1個優勢：在存儲鄰接矩陣的每一個元素時，可以只用1個2進位，而沒必要用1個字的空間。
圖的搜索算法
搜索1個圖示有序地沿著圖的邊訪問所有的頂點，主要有兩種搜索算法，廣度優先遍歷(bfs，也稱為寬度遍歷)和深度優先遍歷(dfs)。
廣度優先(bfs)
從源點s對圖進行廣度優先遍歷，得到的路徑為從源點s到其它各點的最短路徑，也生成了1棵廣度優先樹。廣度優先遍歷需要1個隊列，先進先出。
代碼以下：
// 廣度遍歷圖
void Graph::bfs(int s){
queue<int> q;
q.push(s);
visited[s] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
cout << u <<" ";
GNode *p = edges[u].next;
while(p != NULL){
if(!visited[p->val]){ // 未被訪問，則將其加入隊列中并標志為訪問過
q.push(p->val);
visited[p->val] = 1;
}
p = p->next;
}
}
}
void Graph::bfsTravel(){
memset(visited, 0, sizeof(int)*vertexNum);
for(int i = 0; i < vertexNum; i++){
if(!visited[i]){
bfs(i);
cout << endl;
}
}
}
時間復雜度為O(V+E)
深度優先(dfs)
深度優先搜素構成了1個由數棵深度優先樹所組成的深度優先森林，每條邊被稱為樹邊。另外深度遍歷對每一個節點會有個時間戳，用于標識該結點開始訪問和結束訪問的時間。1個重要的特性就是發現和完成時間具有括號結構。
代碼以下：
// 深度優先遍歷
void Graph::dfs(int s){
visited[s] = 1;
time += 1;
beginTime[s] = time;
cout << s << "(" << beginTime[s] << " "; // shen
GNode *p = edges[s].next;
while(p != NULL){
if(!visited[p->val])
dfs(p->val);
p = p->next;
}
time += 1;
endTime[s] = time;
topSort.push_back(s);
cout << endTime[s] << ")" <<" ";
}
void Graph::dfsTravel(){
memset(visited, 0, sizeof(int)*vertexNum);
memset(beginTime, 0, sizeof(int)*vertexNum); // 結點開始訪問的時間
memset(endTime, 0, sizeof(int)*vertexNum); // 結點結束訪問的時間
for(int i = 0; i < vertexNum; i++){
if(!visited[i]){
dfs(i);
cout << endl;
}
}
}
時間復雜度O(V+E)
注意：
對深度優先遍歷，其邊還可以劃分為4類。
(1)樹邊，深度遍歷森林中的每條邊就是樹邊。
(2)前向邊，u到其后裔的非樹邊(u,v)。
(3)反向邊，u到其先人的邊(u,v)。
(4)橫向邊，1個頂點就不是另外1個頂點的先人或后裔。
性質：(1)1個有向圖是無回路的，當且僅當對該圖的深度優先搜索沒有產生反向邊
(2)對1個無向圖G進行深度優先搜索的進程中，G的每條邊要末是樹邊，要末是反向邊。
拓撲排序
有向無回路圖(DAG,directed acyclic graph)的拓撲排序是深度優先搜索的1個利用。拓撲排序是對圖G的所有頂點的1個線性序列，如果對圖G中的邊(u,v)，則頂點u排在頂點v的前面。在很多利用中，有向無回路圖用于說明事件產生的前后次序。
算法基本思想：通過對DAG圖進行深度優先遍歷以得到完成訪問每一個結點的時間，其逆序就是DAG圖的拓撲排序。
代碼以下：已在深度遍歷中體現。
時間復雜度為O(V+E)。
強連通分支
強連通分支為深度優先搜索的另外一個經典利用。有向圖G=(V,E)的1個強連通分支就是1個最大頂點C是V的子集，使得C中任意兩個頂點可以相互到達
圖G的轉置：GT=(V,ET),ET={(u,v):(u,v) ∈E}.由ET是由G的邊改變方向后所組成的。建立GT所需要的時間復雜度也為O（V+E）
算法的基本思想：首先對圖G進行深度優先搜索，據此得到圖G的拓撲排序序列，然后將圖GT依照此序列進行深度遍歷，得到的括號結構便是所有的強連通分支。時間復雜度依然為O(V+E)
代碼以下：
// 創建圖g的轉置
void Graph::buildTransGraph(Graph &g){
this->vertexNum = g.vertexNum;
this->edgesNum = g.edgesNum;
for(int i = 0; i < vertexNum; i++){
this->vertex[i] = g.vertex[i];
this->edges[i].val = g.edges[i].val;
this->edges[i].weight = g.edges[i].weight;
this->edges[i].next = NULL;
}
for(int i = 0; i < vertexNum; i++){
GNode *p = g.edges[i].next;
while(p != NULL){
GNode *newNode = new GNode();
newNode->val = i;
newNode->next = NULL;
newNode->weight = p->weight;
GNode *q = &edges[p->val];
while(q->next != NULL) q = q->next;
q->next = newNode;
p = p->next;
}
}
}
//強連通份量
void Graph::componentSC(){
//time = 0;
//dfsTravel(); // 對圖g進行深度搜索得到完成x訪問所需要的時間 并由此得到其拓撲排序
Graph g2;
g2.buildTransGraph(*this); // 得到圖G的轉置
time = 0;
memset(g2.visited, 0, sizeof(int)*vertexNum);
cout << "強連通份量: " << endl;
for(vector<int>::reverse_iterator iter = topSort.rbegin(); iter != topSort.rend(); iter++){ // 對轉置圖g2進行深度搜索得到強連通份量
if(!g2.visited[*iter])
g2.dfs(*iter);
}
cout << endl;
}
完全代碼：
graph.h
#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <vector>
using namespace std;
#define maxSize 10
#define maxInt 0x80000000 // 將此值設為權值的最大值
struct GNode{
int val;
int weight;
GNode *next;
};
class Graph{
public:
void createGraph(int n, int e);
void destroyGraph(GNode *p);
~Graph(){
for(int i = 0; i < vertexNum; i++){
destroyGraph(edges[i].next);
//cout << "析構:" << i << endl;
}
}
void showGraph();
void bfsTravel(); // 廣度遍歷
void dfsTravel(); // 深度遍歷
void showTopSort(); // 輸出拓撲序列
void componentSC(); // 建立圖g的強連通份量
void prim();
private:
int vertex[maxSize]; // 寄存頂點
GNode edges[maxSize]; // 寄存鄰接表
int vertexNum; //頂點個數
int edgesNum; //邊條數
//bfs and dfs 遍歷
int visited[maxSize];
void bfs(int s);
void dfs(int s);
int beginTime[maxSize]; // 深度開始訪問x的時間
int endTime[maxSize]; // 結束訪問x的時間
static int time;
vector<int> topSort; // topSort的逆序為有向無回路的拓撲排序
void buildTransGraph(Graph &g); // 建立圖g的轉置
// prim
int lowcost[maxSize];
};
#endif
graph.cpp
#include <iostream>
#include "graph.h"
#include <queue>
using namespace std;
int Graph::time = 0;
void Graph::createGraph(int n, int e){
vertexNum = n;
edgesNum = e;
for(int i = 0; i < n; i++){
vertex[i] = i;
edges[i].val = i;
edges[i].weight = 0;
edges[i].next = NULL;
}
for(int i = 0; i < e; i++){
int source, dest, wei;
cin >> source >> dest >> wei;
GNode *newNode = new GNode();
newNode->val = dest;
newNode->weight = wei;
newNode ->next = NULL;
GNode *p = &edges[source];
while(p->next != NULL) p = p->next;
p->next = newNode;
// 無向圖 有向圖就將這段刪除掉
/*GNode *newNode2 = new GNode();
newNode2->val = source;
newNode2->weight = wei;
newNode2 ->next = NULL;
GNode *p2 = &edges[dest];
while(p2->next != NULL) p2 = p2->next;
p2->next = newNode2;*/
}
}
void Graph::destroyGraph(GNode *p){
if(p == NULL) return;
else{
destroyGraph(p->next);
delete p;
}
}
void Graph::showGraph(){
for(int i = 0; i < vertexNum; i++){
int j = i;
cout << i << "->";
GNode *p = edges[j].next;
while( p != NULL) {
cout << "(" << p->val <<"," << p->weight << ")" ;
p = p->next;
}
cout << endl;
}
}
// 廣度遍歷圖
void Graph::bfs(int s){
queue<int> q;
q.push(s);
visited[s] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
cout << u <<" ";
GNode *p = edges[u].next;
while(p != NULL){
if(!visited[p->val]){ // 未被訪問，則將其加入隊列中并標志為訪問過
q.push(p->val);
visited[p->val] = 1;
}
p = p->next;
}
}
}
void Graph::bfsTravel(){
memset(visited, 0, sizeof(int)*vertexNum);
for(int i = 0; i < vertexNum; i++){
if(!visited[i]){
bfs(i);
cout << endl;
}
}
}
// 深度優先遍歷
void Graph::dfs(int s){
visited[s] = 1;
time += 1;
beginTime[s] = time;
cout << s << "(" << beginTime[s] << " "; // shen
GNode *p = edges[s].next;
while(p != NULL){
if(!visited[p->val])
dfs(p->val);
p = p->next;
}
time += 1;
endTime[s] = time;
topSort.push_back(s);
cout << endTime[s] << ")" <<" ";
}
void Graph::dfsTravel(){
memset(visited, 0, sizeof(int)*vertexNum);
memset(beginTime, 0, sizeof(int)*vertexNum); // 結點開始訪問的時間
memset(endTime, 0, sizeof(int)*vertexNum); // 結點結束訪問的時間
for(int i = 0; i < vertexNum; i++){
if(!visited[i]){
dfs(i);
cout << endl;
}
}
}
// 輸出拓撲排序
void Graph::showTopSort(){
for(vector<int>::reverse_iterator iter = topSort.rbegin(); iter != topSort.rend(); iter ++)
cout << *iter << " ";
cout << endl;
}
// 創建圖g的轉置
void Graph::buildTransGraph(Graph &g){
this->vertexNum = g.vertexNum;
this->edgesNum = g.edgesNum;
for(int i = 0; i < vertexNum; i++){
this->vertex[i] = g.vertex[i];
this->edges[i].val = g.edges[i].val;
this->edges[i].weight = g.edges[i].weight;
this->edges[i].next = NULL;
}
for(int i = 0; i < vertexNum; i++){
GNode *p = g.edges[i].next;
while(p != NULL){
GNode *newNode = new GNode();
newNode->val = i;
newNode->next = NULL;
newNode->weight = p->weight;
GNode *q = &edges[p->val];
while(q->next != NULL) q = q->next;
q->next = newNode;
p = p->next;
}
}
}
//強連通份量
void Graph::componentSC(){
//time = 0;
//dfsTravel(); // 對圖g進行深度搜索得到完成x訪問所需要的時間 并由此得到其拓撲排序
Graph g2;
g2.buildTransGraph(*this); // 得到圖G的轉置
time = 0;
memset(g2.visited, 0, sizeof(int)*vertexNum);
cout << "強連通份量: " << endl;
for(vector<int>::reverse_iterator iter = topSort.rbegin(); iter != topSort.rend(); iter++){ // 對轉置圖g2進行深度搜索得到強連通份量
if(!g2.visited[*iter])
g2.dfs(*iter);
}
cout << endl;
}
main.cpp
#include <iostream>
#include "graph.h"
using namespace std;
int main(){
Graph g;
g.createGraph(8, 13);
cout << "鄰接表: " << endl;
g.showGraph();
cout << "廣度遍歷的結果: " << endl;
g.bfsTravel();
cout << "深度遍歷的結果: " << endl; // 具有括號結果 其中x(a b) x代表結點 a代表開始訪問x的時間 b代表完成訪問x的時間
g.dfsTravel(); // 深度遍歷完成訪問x的時間的逆序就是有向無回路的拓撲排序
cout << "拓撲排序: " << endl;
g.showTopSort();
g.componentSC();
return 0;
}
圖例:
待傳...
輸入:
0 1 1
1 2 1
2 0 1
1 3 1
3 4 1
4 3 1
2 5 1
5 6 1
6 5 1
3 6 1
6 7 1
7 7 1
4 7 1
輸出:
其中0(1 2(2 3) 4)表示在深度遍歷中第0個結點開始訪問結點的時間為1，結束訪問結點的時間為4；2結點開始訪問的時間為2，結束訪問的時間為3.
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
