邻接表：使用数组来存储顶点的集合，使用链表来存储顶点之间边的关系。
例：
从图中可以看出邻接表更节省空间，如果我们要求图中有多少条边的话，则用邻接表是非常快的。用邻接表存储边的话有多少条边就有多少个结点，所以它真正存储的就是边。 图的遍历：图的遍历有两种方式，深度优先遍历(DFS)和广度(BFS)优先遍历。深度优先遍历就是沿着一条路径一直走到底，直到走不下去的时候再返回上一个路口寻找一条没走过的路径再走。广度优先遍历是一种层层递进的思想，以起点为中心，一层一层的访问。不过对于图来说，不管是哪种遍历，我们都可能再次遇到已经访问过的结点，所以在对图遍历的时候我们还需要用一个辅助数组来标记哪些结点已经访问过了，哪些结点还没有访问过。我在这里实现的是邻接表方式存储的图的两种遍历方式。 广度优先遍历： void BFS(V src)//广度优先搜索 { vector<bool> visited(_vertex.size(),false); _BFS(GetIndex(src),visited); for(int i = 0; i<_vertex.size(); ++i) { if(visited[i] == false) _BFS(GetIndex(_vertex[i]),visited); } cout<<"NULL"<<endl; } void _BFS(size_t index,vector<bool>& visited) { queue<size_t> q; q.push(index); while(!q.empty()) { int front = q.front(); q.pop(); if(visited[front] == false) { cout<<_vertex[front]<<":"<<front<<"->"; visited[front] = true; } Node* cur = _tables[front]; while(cur) { if(visited[GetIndex(cur->_dst)] == false) q.push(GetIndex(cur->_dst)); cur = cur->_next; } } } 深度优先遍历： void DFS(V src)//深度优先搜索 { vector<bool> visited(_vertex.size(),false); _DFS(GetIndex(src),visited); for(int i = 0; i<_vertex.size(); ++i) { if(visited[i] == false) _DFS(GetIndex(_vertex[i]),visited); } cout<<"NULL"<<endl; } void _DFS(size_t src,vector<bool>& visited) { cout<<_vertex[src]<<":"<<src<<"->"; visited[src] = true; Node* cur = _tables[src]; while(cur) { int index = GetIndex(cur->_dst); if(visited[index] == false) { _DFS(index,visited); } cur = cur->_next; } } 最小生成树： 首先要明白最小生成树的概念是针对于无向图而言的。对于一个连通图，图中有N个顶点。如果我们能在连通图中选取N-1条边将图的所有顶点连在一起且不构成回路，则这N-1条边就构成了一个生成树。如果这N-1条边的权值和最小，则就构成了最小生成树。 构造最小生成树时有两个算法，分别是Kruskal算法和Prim算法，这两个算法都使用了贪心法求解。但是要注意：使用贪心算法在求解最小生成树的时候总是得到了局部最优解，但是整体结果不一定最优解。Kurscal算法和Prim算法 Kruskal算法： Kruskal算法是一种找边的思想。假设初始时有两个存放边的集合为E1和E2，E1里面存放了连通图的所有边，E2是空集合。 1、在E1里面找一条权值最小的边edge,并将edge从E1里面删除 2、判断edge是否与E2里面的边能形成回路。 3、如果构成回路则就丢弃这条边，从步骤1重新开始。 4、如果不构成回路，则就将edge加入到E2中。 5、如果E2中有N-1条边的话，则就停止，这时候最小生成树就已经找出来了。否则就重复上述步骤。 找边的时候可以借助堆，建一个小堆，每次拿到堆顶值，就找到了最小边, 判断回路：可以用一个并查集ufs,将连通图的 所有顶点都加入到并查集里面，将E2里面的所有边的顶点都并入一个集合，这样的话如果edge的两个顶点是在一个集合中，则它就会构成回路，否则不会构成回路。 Kruskal: bool Kruskal(GraphLink<V,W>& graph) { if(_isDirection) return false; graph._vertex = _vertex; graph._isDirection = _isDirection; size_t size = _tables.size(); graph._tables.resize(size); UnionSet us(size); struct Compare { bool operator()(Node* l,Node* r) { return l->_w < r->_w; } }; //建一个小堆 Heap<Node*,Compare> minHeap; for(size_t i = 0; i<size; ++i) { Node* cur = _tables[i]; while(cur) { minHeap.Push(cur); cur = cur->_next; } } int n = 0; while(n<size-1) { if(minHeap.Empty()) return false; Node* top = minHeap.Top(); minHeap.Pop(); size_t root1 = us.GetRoot(top->_src); size_t root2 = us.GetRoot(top->_dst); if(root1 != root2) { graph.AddEdg(top->_src,top->_dst,top->_w); us.Union(top->_src,top->_dst); n++; } } return true; } Prim算法：Prim算法是一种找点的思想。初始时有两个存放点的集合V1和V2，V1里面存放了连通图里面任意的N-1个顶点，V2是里面存放了1个顶点。 1、在V1和V2里面各选一个点，将他们组成的边的所有情况存放在集合E里面。 2、假设v1和v2是分别从V1和V2里面选择出来的点，并且v1和v2构成的边是E里面最小的。 3、将v1加入到V2里面，并将v1从V1里面删除。 4、如果V1不为空，则重复上述步骤。 Prim: bool Prim(GraphLink<V,W>& graph) { if(_isDirection) return false; graph._vertex = _vertex; graph._isDirection = _isDirection; size_t size = _vertex.size(); graph._tables.resize(size); struct Compear { bool operator()(Node* l,Node* r) { return l->_w < r->_w; } }; Heap<Node*,Compear> minHeap; //建一个并查集 UnionSet us(size); Node* cur = _tables[0]; size_t n = 0; while(n<size-1) { while(cur)//将这个点的所有边都放入小堆 { minHeap.Push(cur); cur = cur->_next; } if(minHeap.Empty()) return false; Node* top = minHeap.Top(); minHeap.Pop(); int root1 = us.GetRoot(top->_src); int root2 = us.GetRoot(top->_dst); if(root1 != root2) { //修改并查集 us.Union(top->_src,top->_dst); graph.AddEdg(top->_src,top->_dst,top->_w); //把边加入到Graph中 cur = _tables[top->_dst]; //以目标为起点， ++n; } } return true; } 全部代码： 邻接矩阵(简易版) template<class V,class W> class GraphMatrix { public: GraphMatrix(V* vertex,int size,bool isDriection = false,const W& invalid = W()) :_vertex(new V[size]) ,_size(size) ,_isDriection(isDriection) { _matrix = new W*[size]; for(int i = 0; i<size; ++i) { _vertex[i] = vertex[i]; _matrix[i] = new W[size]; } for(int i = 0;i<_size;++i) { for(int j = 0; j<_size; ++j) { _matrix[i][j] = W(); } } } int GetIndex(V src) { for(int i = 0; i<_size; ++i) { if(src == _vertex[i]) { return i; } } //assert(false); //invalid_argument---参数异常 } void AddEdg(V src,V dst,const W& w) { int index1 = GetIndex(src); int index2 = GetIndex(dst); _matrix[index1][index2] = w; if(_isDriection == false) _matrix[index2][index1] = w; } ~GraphMatrix() { delete[] _vertex; for(int i = 0; i<_size; ++i) { delete[] _matrix[i]; } delete[] _matrix; } void Print() { for(int i = 0; i<_size; ++i) { cout<<_vertex[i]<<"->"; for(int j = 0;j<_size; ++j) { if(_matrix[i][j] != W()) { cout<<_matrix[i][j]; cout<<_vertex[j]<<"->"; } } cout<<"NULL"<<endl; } cout<<endl; } protected: V* _vertex; //顶点 W** _matrix; //边 int _size; //顶点个数 bool _isDriection; //是有向图还是无向图 }; void TestGraphMatrix() { //string vertex[] = {"西安","咸阳","宝鸡","渭南","延安"}; //GraphMatrix<string,int> gm(vertex,5); //gm.AddEdg("西安","宝鸡",300); //gm.AddEdg("西安","咸阳",100); //gm.AddEdg("西安","渭南",200); //gm.AddEdg("宝鸡","延安",300); //gm.AddEdg("渭南","宝鸡",200); int vertex[] = {0,1,2,3,4}; GraphMatrix<int,int> gl(vertex,5); gl.AddEdg(0,3,10); gl.AddEdg(0,4,20); gl.AddEdg(1,2,10); gl.AddEdg(1,3,20); gl.AddEdg(1,4,30); gl.AddEdg(2,4,40); gl.Print(); } 邻接表 #include <vector> #include <queue> template<class V,class W> class GraphLink { struct Node { V _src; V _dst; W _w; Node* _next; Node(V src,V dst,const W& w) :_src(src) ,_dst(dst) ,_w(w) ,_next(NULL) {} }; public: GraphLink(V* vertex,int size,bool isDirection = false) :_isDirection(isDirection) { _vertex.resize(size); _tables.resize(size); for(int i = 0; i<size; ++i) { _vertex[i] = vertex[i]; } } int GetIndex(V src) { for(int i = 0; i<_vertex.size(); ++i) { if(src == _vertex[i]) { return i; } } //assert(false); //invalid_argument---参数异常 } void AddEdg(V src,V dst,const W& w) { int index1 = GetIndex(src); Node* tmp = new Node(src,dst,w); tmp->_next = _tables[index1]; _tables[index1] = tmp; if(_isDirection == false) { int index2 = GetIndex(dst); Node* tmp = new Node(dst,src,w); tmp->_next = _tables[index2]; _tables[index2] = tmp; } } void BFS(V src)//广度优先搜索 { vector<bool> visited(_vertex.size(),false); _BFS(GetIndex(src),visited); for(int i = 0; i<_vertex.size(); ++i) { if(visited[i] == false) _BFS(GetIndex(_vertex[i]),visited); } cout<<"NULL"<<endl; } void _BFS(size_t index,vector<bool>& visited) { queue<size_t> q; q.push(index); while(!q.empty()) { int front = q.front(); q.pop(); if(visited[front] == false) { cout<<_vertex[front]<<":"<<front<<"->"; visited[front] = true; } Node* cur = _tables[front]; while(cur) { if(visited[GetIndex(cur->_dst)] == false) q.push(GetIndex(cur->_dst)); cur = cur->_next; } } } void DFS(V src)//深度优先搜索 { vector<bool> visited(_vertex.size(),false); _DFS(GetIndex(src),visited); for(int i = 0; i<_vertex.size(); ++i) { if(visited[i] == false) _DFS(GetIndex(_vertex[i]),visited); } cout<<"NULL"<<endl; } void _DFS(size_t src,vector<bool>& visited) { cout<<_vertex[src]<<":"<<src<<"->"; visited[src] = true; Node* cur = _tables[src]; while(cur) { int index = GetIndex(cur->_dst); if(visited[index] == false) { _DFS(index,visited); } cur = cur->_next; } } void Print() { for(int i = 0; i<_tables.size(); ++i) { Node* cur = _tables[i]; cout<<_vertex[i]; while(cur) { cout<<"->"<<cur->_w<<" "<<cur->_dst; cur = cur->_next; } cout<<"->NULL"<<endl; } } //最小生成树---Kruskal算法 bool Kruskal(GraphLink<V,W>& graph) { if(_isDirection) return false; graph._vertex = _vertex; graph._isDirection = _isDirection; size_t size = _tables.size(); graph._tables.resize(size); UnionSet us(size); struct Compare { bool operator()(Node* l,Node* r) { return l->_w < r->_w; } }; //建一个小堆 Heap<Node*,Compare> minHeap; for(size_t i = 0; i<size; ++i) { Node* cur = _tables[i]; while(cur) { minHeap.Push(cur); cur = cur->_next; } } int n = 0; while(n<size-1) { if(minHeap.Empty()) return false; Node* top = minHeap.Top(); minHeap.Pop(); size_t root1 = us.GetRoot(top->_src); size_t root2 = us.GetRoot(top->_dst); if(root1 != root2) { graph.AddEdg(top->_src,top->_dst,top->_w); us.Union(top->_src,top->_dst); n++; } } return true; } //最小生成树---Prim算法 bool Prim(GraphLink<V,W>& graph) { if(_isDirection) return false; graph._vertex = _vertex; graph._isDirection = _isDirection; size_t size = _vertex.size(); graph._tables.resize(size); struct Compear { bool operator()(Node* l,Node* r) { return l->_w < r->_w; } }; Heap<Node*,Compear> minHeap; //建一个并查集 UnionSet us(size); Node* cur = _tables[0]; size_t n = 0; while(n<size-1) { while(cur)//将这个点的所有边都放入小堆 { minHeap.Push(cur); cur = cur->_next; } if(minHeap.Empty()) return false; Node* top = minHeap.Top(); minHeap.Pop(); int root1 = us.GetRoot(top->_src); int root2 = us.GetRoot(top->_dst); if(root1 != root2) { //修改并查集 us.Union(top->_src,top->_dst); graph.AddEdg(top->_src,top->_dst,top->_w); //把边加入到Graph中 cur = _tables[top->_dst]; //以目标为起点， ++n; } } return true; } protected: vector<V> _vertex; //顶点数组 bool _isDirection; vector<Node*> _tables; //邻接表 }; //void TestGraphLink() //{ // string vertex[6] = {"西安","咸阳","宝鸡","渭南","延安","汉中"}; // // GraphLink<string,int> gl(vertex,6); // // gl.AddEdg("西安","宝鸡",300); // gl.AddEdg("西安","咸阳",100); // gl.AddEdg("西安","渭南",200); // gl.AddEdg("宝鸡","延安",300); // gl.AddEdg("渭南","宝鸡",200); // // gl.Print(); // // gl.DFS("西安"); // gl.BFS("西安"); //} void TestKruskal() { int vertex[] = {0,1,2,3,4}; GraphLink<int,int> gl(vertex,5); gl.AddEdg(0,3,10); gl.AddEdg(0,4,20); gl.AddEdg(1,2,10); gl.AddEdg(1,3,20); gl.AddEdg(1,4,30); gl.AddEdg(2,4,40); gl.Print(); cout<<gl.Kruskal(gl)<<endl; GraphLink<int,int> g2(vertex,5); cout<<gl.Kruskal(g2)<<endl; g2.Print(); } void TestPrim() { int vertex[] = {0,1,2,3,4}; GraphLink<int,int> gl(vertex,5); gl.AddEdg(0,3,10); gl.AddEdg(0,4,20); gl.AddEdg(1,2,10); gl.AddEdg(1,3,20); gl.AddEdg(1,4,30); gl.AddEdg(2,4,40); gl.Print(); cout<<gl.Prim(gl)<<endl; GraphLink<int,int> g2(vertex,5); cout<<gl.Prim(g2)<<endl; g2.Print(); }
