建站
咨询
售后
建站咨询
一 图的定义与操作
A 定义
图是有顶点集合(Vertex)及顶点间的关系集合(Edge)组成的一种数据结构
Graph=(V,E)
无向边
1.顶点x和y之间的边没有方向,则称该边为 无向边
2.(x,y)与(y,x)意义相同，表示x和y之间有连接
无向图
图中任意两个顶点之间的边均是无向边，则称该图为无向图
有向边
1.顶点x和y之间的边有方向，则称该边为有向边
2.
有向图
图中任意两个顶点之间的边钧是有向边，则称该图为有向图
顶点邻接的定义
1.无向图--如果(x,y)属于E,则称x和y互为邻接
2.有向图--如果
度(Degree)的定义
1.顶点v的度是和v相关联的边的数目，记为TD(v)
a.入度:以v为头的边的数目，记为ID(v)
b.出度:以v为尾的边的数目，记为OD(v)
权(Weight)的定义
1.与图的边相关的数据元素叫权
2.权常用来表示图中顶点间的距离或者耗费
图的一些常用操作
1.设置顶点的值 2.获取顶点的值 3.获取邻接顶点 4.设置边的值
5.删除边 6.获取顶点数 等等
template
class Graph:public Object
{
public:
virtual V getVertex(int x)=0;
virtual bool getVertex(int x,V& value)=0;
virtual bool setVertex(int i,const V& value)=0;
virtual SharedPointer>getAdjacent(int i)=0;
virtual E getEdge(int i,int j)=0;
virtual bool getEdge(int i, int j,E& value)=0;
virtual bool setEdge(int i, int j,const E& value)=0;
virtual bool removeEdge(int i,int j)=0;
virtual int vCount()=0;
virtual int eCount()=0;
virtual int OD(int i)=0;
virtual int ID(int i)=0;
virtual int TD(int i);
}； 二 图的存储结构
基本思想
1.用一维数组存储顶点:描述顶点相关的数据
2.用二维数组存储边:描述顶点间的关系和权
邻接矩阵法
-设图A=(V,E)是一个有n个顶点的图，图的邻接矩阵为Edge[n][n],则
实现方法一：直接使用数组表示顶点集和边集
template
class MatrixGraph:public Graph
{
protected:
V m_vertexes[N];
E m_edges[N][N];
int m_eCount;
public:
//......
}; 问题：
1.构造效率低下--图对象初始化时，频繁调用顶点类型和边类型的构造函数
2.空间使用率低下--图对象占用大量空间，而大多数空间处于闲置状态
3.无法表示空值--无法用统一的方式表示为空的情形
实现方式二：使用指针数组表示顶点集和边集
template
class MatrixGraph:public Graph
{
protected:
V* m_vertexes[N];
E* m_edges[N][N];
int m_eCount;
public:
//......
}; 问题的解决：
1.构造效率--初始化图像时，只需要将数组元素赋值为空
2.空间使用率--顶点数据元素和边数据元素在需要时动态创建
3.空值的表示--任意的顶点类型和边类型都使用NULL表示空值
图的遍历
1.广度优先--以二叉树层次遍历的思想对图进行遍历
2.深度优先--以二叉树先序遍历的思想对图进行遍历
A.广度优先算法
-原料：队列 LinkQueue
-步骤
1.将起始顶点压入队列中
2.队头顶点v弹出，判断是否已经标记
3.标记顶点v，并将顶点v的邻接顶点压入队列中
4.判断队列是否为空
B.深度优先算法
-原料：class LinkStack
-步骤：
1.将起始点压入栈中
2.弹出栈顶顶点v，判断是否已经标记
3.标记顶点v，并将顶点v的邻接顶点压入栈中
4.判断栈是否为空
代码实现
SharedPointer>BFS(int i)
{
DynamicArray* ret=NULL;
if((0<=i)&&(iq;
LinkQueuer;
DynamicArrayvisited(vCount());
for(int i=0;i0)
{
int v=q.front();
q.remove();
if(!visited[v])
{
SharedPointer< Array >aj=getAdjacent(v);
for(int j=0;jlength();j++)
{
q.add((*aj)[j]);
}
r.add(v);
visited[v]=true;
}
}
ret=toArray(r);
}
else
{
THROW_EXCEPTION(InvalidParameterException,"0.0");
}
return ret;
}
SharedPointer>DFS(int i)
{
DynamicArray* ret=NULL;
if((0<=i)&&(is;
LinkQueuer;
DynamicArrayvisited(vCount());
for(int j=0;j0)
{
int v=s.top();
s.pop();
if(!visited[v])
{
SharedPointer>aj=getAdjacent(v);
for(int j=aj->length()-1;j>=0;j--)
{
s.push((*aj)[j]);
}
r.add(v);
visited[v]=true;
}
}
ret=toArray(r);
}
else
{
THROW_EXCEPTION(InvalidParameterException,"...");
}
return ret;
} 另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
分享名称：数据结构--图-创新互联
本文URL：http://lswzjz.com/article/ddihsc.html
