图的抽象数据类型

类型名称：图

数据对象集：一个非空的顶点集合和一个边集合，每条边用对应的一对顶点表示。

操作集：

（1）：构造一个有N个顶点但是没有边的图G；

（2）：在G中增加新边E

（3）：从G中删除边E

（4）：判断是否为空

（5）：会使用深度优先遍历

（6）：会使用广度优先遍历

储存结构：

（1）：邻接矩阵：可以理解为二维数组

（2）：邻接表：链表的方式来表示

类似于树的孩子链表表示法

图的遍历：

（1）：深度优先遍历（DFS）

沿着一条路一直深入，到无路可走的时候开始原路返回，返回途中如果又有路可以走就继续深入，最后每个点都遍历完的时候循环结束。

伪代码部分：

void DFS(Graph G,Vertex V, Void(*Visit)(Vertex))

{

        Visit(V);    访问第V个顶点

        Visited[V]=true;     用来表示这个点已经走过了

         for(V的每个邻接点w)

                IF(!Visited[w])                    如果没有走过点W

                        DFS(G,W,Visit);          就以点W为起点再次调用这个函数

}

（2）：广度优先遍历（BFS）

先把一个点上所连接的点都遍历一遍，再去遍历下一个点

伪代码部分：

bool IsEdge(MGraph Graph,Vertex V,Vertex W)

{

        return Graph->G[V][W]<INFINITY?true:false;

}

Void BFS(MGraph Graph,Vertex S,void(*Visit)(Vertex))

{

        Queue Q;

        Vertex V,W;

        Q=CreateQueue(MaxSize);

        Visit(S);

        Visited[S]=true;

        AddQ(Q,S);

        while(!IsEmpty(Q))

        {

                V=DeleteQ(Q);

                for(W=0;W<Graph->Nv;W++)

                        if(!Visited[W]&&IsEdge(Graph,V,W)){

                                Visit(W);

                                Visited[W]=true;

                                AddQ(Q,W);

                         }

        }

}