图的分类
有/无向图
如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。
下面介绍图的两种存储结构
1、邻接矩阵
用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵
邻接矩阵的思想图
代码实现
int GetIndex(const V& v)//获取顶点
{
for (size_t i=0;i<_size;i++)
{
if(_vertex[i]==v)
return i;
}
throw std::invalid_argument("顶点赋值错误");
}
void AddEdge(const V& src,const V& dst,const W& w)//增加矩阵中的点
{
size_t srcIndex=GetIndex(src);
size_t dstIndex=GetIndex(dst);
_matrix[srcIndex][dstIndex]=w;
if(_isDirection==false)
_matrix[dstIndex][srcIndex]=w;
}
2、邻接表
图的邻接矩阵存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
邻接表的思想图
邻接表的代码实现
int GetIndex(const V& v)
{
for (int i=0;i<_vertex.size();i++)
{
if(_vertex[i]==v)
return i;
}
throw std::invalid_argument("顶点赋值错误");
}
void _AddEdge(size_t src,size_t dst,const W& w)
{
// _table[src][dst]._w=w;
Node* cur=new Node(src,dst,w);
cur->Next=_table[src];
_table[src]=cur;
}
void AddEdge(const V& src,const W& w)
{
int srcIndex=GetIndex(src);
int dstIndex=GetIndex(dst);
if (_isDirection)
{
_AddEdge(srcIndex,dstIndex,w);
}
else
{
_AddEdge(srcIndex,w);
_AddEdge(dstIndex,srcIndex,w);
}
}
邻接表的深度优先遍历，类似于二叉树的前序遍历
一个节点知道遍历到无路可走才遍历旁边的节点
代码实现，这里用vector实现
void DFS(const V& v)
{
vector<bool> visted(_vertex.size(),false);
cout<<v;
_DFS(GetIndex(v),visted);
for(size_t i=0;i<_vertex.size();i++)
{
if(visted[i]==false)
{
cout<<_vertex[i];
visted[i]=true;
_DFS(i,visted);
}
}
cout<<"NULL"<<endl;
}
void _DFS(size_t src,vector<bool>& visted)
{
visted[src]=true;
Node* cur=_table[src];
cout<<"["<<src<<"]->";
while (cur)
{
if(visted[cur->_dst]==false)
{
cout<<_vertex[cur->_dst];
visted[cur->_dst]=true;
_DFS(cur->_dst,visted);
}
cur=cur->Next;
}
}
邻接表的广度优先遍历
一个节点把它周围的节点全部都遍历完，才会进行前进遍历
代码实现，这里用队列实现，队列有先进先出的特点，符合此算法
void _BFS(size_t src,vector<bool>& visted)
{
visted[src]=true;
cout<<"["<<src<<"]->";
queue<size_t> q;
q.push(src);
while (!q.empty())
{
src=q.front();
q.pop();
Node* cur=_table[src];
while (cur)
{
if(visted[cur->_dst]==false)
{
cout<<_vertex[cur->_dst]<<"["<<cur->_dst<<"]"<<"-> ";
visted[cur->_dst]=true;
q.push(cur->_dst);
}
cur=cur->Next;
}
}
cout<<endl;
}
void BFS(const V& v)
{
vector<bool> visted(_vertex.size(),false);
cout<<v;
_BFS(GetIndex(v),visted);
}
附全部代码及其测试
临街矩阵
#include <iostream>
#include <string>
#include <vector>
using namespace std;
template<class V,class W>
class GraphMatrix
{
public:
GraphMatrix(V* vertex,size_t size,bool isDirection=false,const int invalid=0 )
:_vertex(new V[size]),_size(size),_isDirection(isDirection)
{
_matrix=new W*[size];
for(size_t i=0;i<size;i++)
{
_vertex[i]=vertex[i];
_matrix[i]=new W[size];
for (size_t j=0;j<size;j++)
{
_matrix[i][j]=invalid;
}
}
}
~GraphMatrix()
{
delete[] _vertex;
delete[] _matrix;
_size=0;
}
int GetIndex(const V& v)//获取顶点
{
for (size_t i=0;i<_size;i++)
{
if(_vertex[i]==v)
return i;
}
throw std::invalid_argument("顶点赋值错误");
}
void AddEdge(const V& src,const W& w)//增加矩阵中的点
{
size_t srcIndex=GetIndex(src);
size_t dstIndex=GetIndex(dst);
_matrix[srcIndex][dstIndex]=w;
if(_isDirection==false)
_matrix[dstIndex][srcIndex]=w;
}
void PrintMaxtix()
{
for(size_t i=0;i<_size;i++)
{
for(size_t j=0;j<_size;j++)
{
cout<<_matrix[i][j]<<" ";
}
cout<<endl;
}
}
protected:
V* _vertex;
W** _matrix;
size_t _size;
bool _isDirection;
};
void TestGraphMatrix()
{
string v[4]={"西安","宝鸡","咸阳","延安"};
GraphMatrix<string,size_t> gm(v,4);//无向图
cout<<"无向图邻接矩阵："<<endl;
gm.AddEdge("西安",7);
gm.AddEdge("西安",200);
gm.AddEdge("西安","延安",500);
gm.AddEdge("宝鸡",100);
gm.AddEdge("宝鸡",200);
gm.AddEdge("咸阳",100);
gm.PrintMaxtix();
GraphMatrix<string,size_t> gm1(v,4,true);//有向图
cout<<"有向图邻接矩阵："<<endl;
gm1.AddEdge("西安",7);
gm1.AddEdge("西安",200);
gm1.AddEdge("西安",500);
gm1.AddEdge("宝鸡",100);
gm1.AddEdge("宝鸡",200);
gm1.AddEdge("咸阳",100);
gm1.PrintMaxtix();
}
邻接表及其遍历
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
template<class V,class W>
class GraphLink
{
struct Node
{
W _w;
size_t _src;
size_t _dst;
Node* Next;
Node(int src=0,int dst=0,const W& w=W())
:_src(src),_dst(dst),_w(w),Next(NULL)
{}
};
public:
GraphLink(const V* vertex,int size,bool isDirection=false)
:_isDirection(isDirection)
{
_vertex.resize(size);
_table.resize(size);
for(size_t i=0;i<size;i++)
{
_vertex[i]=vertex[i];
}
}
int GetIndex(const V& v)
{
for (int i=0;i<_vertex.size();i++)
{
if(_vertex[i]==v)
return i;
}
throw std::invalid_argument("顶点赋值错误");
}
void _AddEdge(size_t src,w);
}
}
void DFS(const V& v)
{
vector<bool> visted(_vertex.size(),visted);
}
cur=cur->Next;
}
}
void _BFS(size_t src,visted);
}
void PrintLink()
{
for (size_t i=0;i<_vertex.size();++i)
{
cout<<_vertex[i]<<"["<<i<<"]->";
Node* cur=_table[i];
while (cur)
{
cout<<_vertex[cur->_dst]<<" ["<<cur->_dst<<"]"<<cur->_w<<"->";
cur=cur->Next;
}
cout<<"NULL"<<endl;
}
}
protected:
vector<V> _vertex;
vector<Node*> _table;
bool _isDirection;
};
void TestGraphLink()
{
string v[4]={"西安","延安"};
GraphLink<string,4);//无向图邻接表
cout<<"无向图邻接表："<<endl;
gm.AddEdge("西安",100);
gm.PrintLink();
cout<<"无向图DFS遍历："<<endl;//深度优先遍历
gm.DFS("西安");
gm.DFS("宝鸡");
gm.DFS("咸阳");
gm.DFS("延安");
cout<<"无向图BFS遍历："<<endl;//广度优先遍历
gm.BFS("西安");
gm.BFS("宝鸡");
gm.BFS("咸阳");
gm.BFS("延安");
GraphLink<string,true);//有向图邻接表
cout<<"有向图邻接表："<<endl;
gm1.AddEdge("西安",100);
gm1.PrintLink();
cout<<"有向图DFS遍历："<<endl;//深度优先遍历
gm1.DFS("西安");
gm1.DFS("宝鸡");
gm1.DFS("咸阳");
gm1.DFS("延安");
cout<<"有向图BFS遍历："<<endl;//广度优先遍历
gm1.BFS("西安");
gm1.BFS("宝鸡");
gm1.BFS("咸阳");
gm1.BFS("延安");
}
测试代码
#include "Graph.h"
#include "GraphLink.h"
#include<stdlib.h>
int main()
{
TestGraphMatrix();
TestGraphLink();
system("pause");
return 0;
}
测试结果
