图处理算法-Kosaraju's-算法

1.写了算法课关于有向图的作业。

用c++开辟大数组容易出segment fault，后来改用堆开辟。图的邻接表用了链表表示。 

long int numVertexes = 875714; long int numEdges; VertexNode* adjList = new VertexNode[875714];

2.关于图的存储，用了邻接链表存储(用链表比vector数组存取速度快多了)。

2.1 边表

/********边表***********/ class EdgeNode { public: long int adjvex; //边表数据 EdgeNode *next; //边表指向的下一个节点 EdgeNode(long int adj, EdgeNode *n = NULL): adjvex(adj), next(n){} };

2.2 顶点表

/*********顶点表**********/ class VertexNode { public: long int data; //当前顶点数据 EdgeNode *firstEdge; //顶点第一条边 // VertexNode(long int d, EdgeNode *fir = NULL) : data(d), firstedge(fir) {} };

2.3 初始化图边时用了头插法

/*************头插法*************************/ void addEdge(long int a, long int b) { EdgeNode *enode = new EdgeNode(b,NULL); enode->next = (adjList+a)->firstEdge; (adjList+a)->firstEdge = enode; }

3.深度优先搜索

3.1 递归实现

伪代码如下： 

输入：有向图G和某个顶点i

1.将该顶点i标记为已访问。

2.对边(i,j)，即顶点i的邻接点j遍历：

3.if 存在某个顶点j未被访问，则对顶点j进行访问：

DFS(G,j)

c++代码如下:

/*---------------------第一次dfs-------------------*/ void DFS(Graph graph, long int i) { marked[i] = true; list<long int>::iterator iter; for(iter = graph._storage[i].begin(); iter != graph._storage[i].end(); iter++) { long int temp = *iter; if(!marked[temp]) { DFS(graph, temp); } } time++; ff[time-1] = i; } /*---------------第二次dfs---------------*/ void DFS2(Graph graph, long int i) { marked[i] = true; leader[i] = s; list<long int>::iterator iter; for(iter = graph._storage[i].begin(); iter != graph._storage[i].end(); iter++) { long int temp = *iter; if(!marked[temp]) { DFS2(graph, temp); } } }

 

3.2 非递归实现

伪代码如下： 

输入：有向图G，顶点i。

1.栈初始化，将顶点i入栈，将i标记为已访问。

2.while(栈非空)

x = 栈顶元素

3. 对边(x,j)进行遍历：

if：存在某个顶点j未被访问：

　　将j标记为已访问

　　将j入栈

　　break

else：

　　x出栈

c++代码：

/*================第一次dfs================*/ void dfsLoop1(Graph graph) { markedInit(); time = 0; for(long int i = length-1; i >= 0; i--) { if(!marked[i]) { DFS1(graph, i); } } } void DFS1(Graph graph, long int i) { stack< VertexNode* > stack; stack.push(graph.adjList+i); marked[i] = true; while(!stack.empty()) { VertexNode *temp = new VertexNode; temp = stack.top(); EdgeNode *p = new EdgeNode(0, NULL); p = temp->firstEdge; int flag = 0; while(p) { if(!marked[p->adjvex]) { marked[p->adjvex] = true; stack.push(graph.adjList + (p->adjvex)); flag = 1; break; } p = p->next; } if(!flag) { ff[time] = temp->data; time++; stack.pop(); } } } /*================第二次dfs================*/ void dfsLoop2(Graph graph) { markedInit(); time = 0; for(long int i = length-1; i >=0 ; i--) { if(!marked[ff[i]]) { s = ff[i]; DFS2(graph, ff[i]); } } } void DFS2(Graph graph, long int i) { stack < VertexNode* > stack; stack.push(graph.adjList+i); leader[i] = s; marked[i] = true; while(!stack.empty()) { VertexNode *temp = new VertexNode; temp = stack.top(); marked[temp->data] = true; EdgeNode *p = new EdgeNode(0,NULL); p = temp->firstEdge; int flag = 0; while(p) { if(!marked[p->adjvex]) { marked[p->adjvex] = true; stack.push(graph.adjList + p->adjvex); flag = 1; break; } p = p->next; } if(!flag) { leader[temp->data] = s; stack.pop(); } } }

完整代码： https://github.com/Shinered/Kosaraju/blob/master/dfs3.cpp

 

转载于:https://www.cnblogs.com/Shinered/p/8999688.html

相关资源：JAVA上百实例源码以及开源项目