简单概念：对于图G(V,E)，通常有两种存储的数据结构，一。邻接表表示法存在很强的适应性，但是也有潜在的不足，，当要快速的确定图中边(u,v)是否存在，只能在顶点u的邻接表中搜索v，没有更快的方法，此时就可以使用邻接矩阵，但要以占用更多的存储空间作为代价；此外当图不是加权的，采用邻接矩阵存储还有一个优势：在存储邻接矩阵的每个元素时，可以只用一个二进位，而不必用一个字的空间。
图的搜索算法
搜索一个图示有序地沿着图的边访问所有的顶点，主要有两种搜索算法，广度优先遍历(bfs，也称为宽度遍历)和深度优先遍历(dfs)。
广度优先(bfs)
从源点s对图进行广度优先遍历，得到的路径为从源点s到其它各点的最短路径，也生成了一棵广度优先树。广度优先遍历需要一个队列，先进先出。
代码如下：
// 广度遍历图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)
深度优先搜素形成了一个由数棵深度优先树所组成的深度优先森林，每条边被称为树边。此外深度遍历对于每个节点会有个时间戳，用于标识该结点开始访问和结束访问的时间。一个重要的特性就是发现和完成时间具有括号结构。
代码如下：
// 深度优先遍历void Graph::dfs(int s){visited[s] = 1;time += 1;beginTime[s] = time;cout << s << "(" << beginTime[s] << " ";// shenGNode *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)一个有向图是无回路的，当且仅当对该图的深度优先搜索没有产生反向边
(2)对一个无向图G进行深度优先搜索的过程中，G的每一条边要么是树边，要么是反向边。
拓扑排序
有向无回路图(DAG,directed acyclic graph)的拓扑排序是深度优先搜索的一个应用。拓扑排序是对图G的所有顶点的一个线性序列，如果对于图G中的边(u,v)，则顶点u排在顶点v的前面。在很多应用中，有向无回路图用于说明事件发生的先后次序。
算法基本思想：通过对DAG图进行深度优先遍历以得到完成访问每个结点的时间，其逆序就是DAG图的拓扑排序。
代码如下：已经在深度遍历中体现。
时间复杂度为O(V+E)。
强连通分支
强连通分支为深度优先搜索的另一个经典应用。有向图G=(V,E)的一个强连通分支就是一个最大顶点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的转置// primint lowcost[maxSize];};#endif
graph.cpp
少一点预设的期待，那份对人的关怀会更自在
