1、实验七 图的存储与操作 1. 实验内容 建立无向图的邻接矩阵存储；对建立的无向图，进行深度优先遍历；对建立的无向图，进行广度优先遍历。 建立一个有向图的邻接表存储结构；对建立的有向图，进行深度优先遍历； 对建立的有向图，进行广度优先遍历。 2. 无向图建立和遍历的 实现提示 本题采用图的邻接矩阵存储，即用一维数组存储图中顶点的信息，用二维数组存储图中边的信息（即各顶点之间的邻接关系）。 假设无向图 G（ V， E）有 n个顶点，则邻接矩阵是一个 n n的方阵，定义为： 设计实验用邻接矩阵类 MGraph，包括遍历操作。 const int MaxSize=10; /图中最多顶点个数 templ
2、ate class MGraph public: MGraph(T a , int n, int e); /构造函数，初始化具有 n个顶点 e 条边的无向图 void DFSTraverse(int v); /深度优先遍历图 void BFSTraverse(int v); /广度优先遍历图 private: T vertexMaxSize; /存放图中顶点的数组 int arcMaxSizeMaxSize; /存放图中边的数组 int vertexNum, arcNum; /图的顶点数和边数 ; 设计构造函数，建立一个无向图的邻接矩阵存储。 假设图的顶点信息存放在数组 an中，边的信息（即边
3、所依附的顶点）由键盘输入，建立一个无向图的邻接矩阵存储的算法如下： 深度优先遍历算法 广度优先遍历算法 3. 有向图建立和遍历的 实现提示 邻接表存储结构是基于顺序存储与链接存储相结合的存储方法，基本思想是：对于图的每个顶点 vi，将所有邻接于 vi 的顶点链成一个单链表，称为顶点 vi 的边表（对于有向图则称为出边表），所有顶点的边表的头指针和存储顶点信息的一维数组构成了顶点表 。所以，在邻接表中存在两种结点结构，分别是顶点表结点和边表结点，如图 6-1 所示。 用 C+中的结构类型描述上述结点。 struct ArcNode /定义边表结点 int adjvex; /邻接点域 ArcNod
4、e *next; ; template struct VertexNode /定义顶点表结点 T vertex; ArcNode *firstedge; ; 设计实验用邻接表类 ALGraph，包括遍历操作。 const int MaxSize=10; /图的最大顶点数 template class ALGraph public: ALGraph(T a , int n, int e); /构造函数，初始化一个有 n个顶点 e 条边的有向图 ALGraph( ); /析构函数，释放邻接表中各边表结点的存储空间 void DFSTraverse(int v); /深度优先遍历图 void BFS
5、Traverse(int v); /广度优先遍历图 private: VertexNode adjlistMaxSize; /存放顶点表的数组 int vertexNum, arcNum; /图的顶点数和边数 ; 设计构造函数，建立有向图的邻接表存储。 深度优先遍历算法如下： 广度优先遍历算法如下： #include“stdio.h“ #include“stdlib.h“ #include #define MaxVertexNum 100 /定义最大顶点数 typedef struct char vexsMaxVertexNum; /顶点表 int edgesMaxVertexNumMaxVe
6、rtexNum; /邻接矩阵，可看作边表 int n, e; /图中的顶点数 n和边数 e MGraph; /用邻接矩阵表示的图的类型 /=建立邻接矩阵 = void CreatMGraph(MGraph *G) int i, j, k; char a; printf(“InputVertexNum(n) and EdgesNum(e): “); scanf_s(“%d,%d“, /输入顶点数和边数 scanf_s(“%c“, printf(“InputVertex string:“); for (i = 0; in; i+) scanf_s(“%c“, G-vexsi = a; /读入顶点信
7、息，建立顶点表 for (i = 0; in; i+) for (j = 0; jn; j+) G-edgesij = 0; /初始化邻接矩阵 printf(“Inputedges,Creat Adjacency Matrixn“); for (k = 0; ke; k+) /读入 e条边，建立邻接矩阵 scanf_s(“%d%d“, /输入边（ Vi， Vj）的顶点序号 G-edgesij = 1; G-edgesji = 1; /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 /=定义标志向量，为全局变量 = typedef enum FALSE, TRUE Boolean; Bo
8、olean visitedMaxVertexNum; /=DFS：深度优先遍历的递归算法 = void DFSM(MGraph *G, int i) /以 Vi为出发点对邻接矩阵表示的图 G进行 DFS搜索，邻接矩阵是，矩阵 int j; printf(“%c“, G-vexsi); /访问顶点 Vi visitedi = TRUE; /置已访问标志 for (j = 0; jn; j+) /依次搜索 Vi的邻接点 if (G-edgesij = 1 /（ Vi， Vj） E，且 Vj未访问过，故 Vj为新出发点 void DFS(MGraph *G) int i; for (i = 0; i
9、n; i+) visitedi = FALSE; /标志向量初始化 for (i = 0; in; i+) if (!visitedi) /Vi未访问过 DFSM(G, i); /以 Vi为源点开始 DFS搜索 /=BFS：广度优先遍历 = void BFS(MGraph *G, int k) /以 Vk为源点对用邻接矩阵表示的图 G进行广度优先搜索 int i, j, f = 0, r = 0; int cqMaxVertexNum; /定义队列 for (i = 0; in; i+) visitedi = FALSE; /标志向量初始化 for (i = 0; in; i+) cqi =
10、-1; /队列初始化 printf(“%c“, G-vexsk); /访问源点 Vk visitedk = TRUE; cqr = k; /Vk已访问，将其入队。注意，实际上是将其序号入队 while (cqf != -1) /队非空则执行 i = cqf; f = f + 1; /Vf出队 for (j = 0; jn; j+) /依次 Vi的邻接点 Vj if (G-edgesij = 1 /访问 Vj visitedj = TRUE; r = r + 1; cqr = j; /访问过 Vj入队 /=main= void main() int i; MGraph *G; G = (MGraph *)malloc(sizeof(MGraph); /为图 G申请内存空间 CreatMGraph(G); /建立邻接矩阵 printf(“PrintGraph DFS: “); DFS(G); /深度优先遍历 printf(“n“); printf(“PrintGraph BFS: “); BFS(G, 3); /以序号为的顶点开始广度优先遍历 printf(“n“); system(“pause“);
