1、图的定义与操作

A 定义

图是有顶点集合(Vertex)及顶点间的关系集合(Edge)组成的一种数据结构

Graph=(V,E)

无向边

1.顶点x和y之间的边没有方向,则称该边为 无向边

2.(x,y)与(y,x)意义相同，表示x和y之间有连接

无向图

图中任意两个顶点之间的边均是无向边，则称该图为无向图

有向边

1.顶点x和y之间的边有方向，则称该边为有向边

2.与意义不同，前项表示从x连接到y，后项表示从y连接到x

有向图

图中任意两个顶点之间的边钧是有向边，则称该图为有向图

顶点邻接的定义

1.无向图–如果(x,y)属于E,则称x和y互为邻接

2.有向图–如果属于E,则称顶点x邻接到顶点y

度(Degree)的定义

1.顶点v的度是和v相关联的边的数目，记为TD(v)

a.入度:以v为头的边的数目，记为ID(v)

b.出度:以v为尾的边的数目，记为OD(v)

权(Weight)的定义

1.与图的边相关的数据元素叫权

2.权常用来表示图中顶点间的距离或者耗费

图的一些常用操作

1.设置顶点的值 2.获取顶点的值 3.获取邻接顶点 4.设置边的值

5.删除边 6.获取顶点数 等等

【领QT开发教程学习资料，点击→「链接」←莬费领取，先码住不迷路~】

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);
}；

2、图的存储结构

基本思想

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;
        }