摘要图(Gｒaph)是一种复杂的非线性结构。

图可以分为无向图、有向图。

若将图的每条边都赋上一个权，则称这种带权图网络。

在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。

在图结构中，对结点（图中常称为顶点)的前趋和后继个数都是不加以限制的,即结点之间的关系是任意的。

图中任意两个结点之间都可能相关。

图有两种常用的存储表示方法:邻接矩阵表示法和邻接表表示法。

在一个图中，邻接矩阵表示是唯一的，但邻接表表示不唯一。

在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍历）及求图中顶点的度。

当然对于图的广度优先遍历还利用了队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)来实现。

这不仅让我们巩固了之前学的队列的基本操作，还懂得了将算法相互融合和运用。

目录第一章课程设计目的..................................................................................... 错误!未定义书签。

第二章课程设计内容和要求....................................................................... 错误!未定义书签。

2．1课程设计内容.................................................................................. 错误!未定义书签。

2.1.1图的邻接矩阵的建立与输出ﻩ错误!未定义书签。

2．１.２图的邻接表的建立与输出............................................... 错误!未定义书签。

2.1.3图的遍历的实现.................................................................... 错误!未定义书签。

2.１．４图的顶点的度................................................................. 错误!未定义书签。

２.2 运行环境......................................................................................... 错误!未定义书签。

第三章课程设计分析..................................................................................... 错误!未定义书签。

3.1图的存储............................................................................................ 错误!未定义书签。

3.1．１图的邻接矩阵存储表示................................................. 错误!未定义书签。

3.1.2 图的邻接表存储表示........................................................... 错误!未定义书签。

3．２图的遍历..................................................................................... 错误!未定义书签。

３.2.1 图的深度优先遍历............................................................. 错误!未定义书签。

3.2.2 图的广度优先遍历ﻩ错误!未定义书签。

３.3图的顶点的度.................................................................................. 错误!未定义书签。

第四章算法（数据结构）描述ﻩ错误!未定义书签。

4．1 图的存储结构的建立。

ﻩ错误!未定义书签。

4.1.1 定义邻接矩阵的定义类型 (7)4.1.2定义邻接表的边结点类型以及邻接表类型........................ 错误!未定义书签。

4.１.3初始化图的邻接矩阵ﻩ错误!未定义书签。

４.1.４初始化图的邻接表ﻩ错误!未定义书签。

4．2 图的遍历ﻩ错误!未定义书签。

4.2.1 深度优先遍历图................................................................. 错误!未定义书签。

4.2.2 广度优先遍历图ﻩ错误!未定义书签。

4.３ main函数........................................................................................ 错误!未定义书签。

4.４图的大致流程表........................................................................... 错误!未定义书签。

第五章源代码ﻩ错误!未定义书签。

第六章测试结果............................................................................................. 错误!未定义书签。

第七章思想总结ﻩ错误!未定义书签。

第八章参考文献........................................................................................... 错误!未定义书签。

第一章课程设计目的本学期我们对《数据结构》这门课程进行了学习。

这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计。

数据结构是计算机软件和计算机应用专业的核心课程之一,在众多的计算机系统软件和应用软件中都要用到各种数据结构。

这次课程设计不但要求学习者掌握《数据结构》中的各方面知识，还要求学习者具备一定的C语言基础和编程能力。

具体说来,这次课程设计主要有两大方面目的:一是让学习者通过学习掌握《数据结构》中的知识。

对于《图的存储与遍历》这一课题来说，所要求掌握的数据结构知识主要有:图的邻接矩阵存储、图的邻接表存储、队列的基本运算实现、邻接矩阵的算法实现、邻接表的算法实现、图的广度优先遍历算法实现、图的深度优先遍历算法实现。

二是通过学习巩固并提高学习者的C语言知识,并初步了解Ｖｉｓｕal C＋＋的知识,提高其编程能力与专业水平。

第二章课程设计内容和要求２．1课程设计内容该课题要求以邻接矩阵和邻接表的方式存储图,输出邻接矩阵和邻接表，并要求实现图的深度、广度两种遍历及顶点的度。

2.1.１图的邻接矩阵的建立与输出对任意输入顶点数和边数的图，若对无向图进行讨论,根据邻接矩阵的存储结构建立图的邻接矩阵并输出。

要求输出的格式是矩阵形式，这样便于直观的了解。

2．1．2图的邻接表的建立与输出对任意给定的图(顶点数和边数可以宏定义)，若对无向图进行讨论，根据邻接表的存储结构建立图的邻接表并输出。

2.1.3图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。

对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空)来实现。

首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。

并以队列是否为空作为循环控制条件。

对于深度优先遍历则采用递归算法来实现。

当然,若存储图的表示不一样，进行两种遍历的方式也不一样。

2．1.４图的顶点的度在图中，可以求顶点的度。

在无向图用邻接矩阵表示，Vｉ顶点的度即是该矩阵第ｉ行或第ｊ列中非0元素的个数之和。

若无向图用邻接表表示，顶点Vi的度则是第i个边表中的结点个数。

2．2 运行环境该程序的运行环境为Windoｗs xp系统,Mｉｃrｏｓｏft Vｉsual Ｃ+＋6.0版本。

第三章课程设计分析3.1图的存储图的存储表示方法很多,但常用的是：图的矩阵表示和邻接表表示。

至于在遇到问题具体选择哪一种表示法,主要取决于具体的应用和欲施加的操作。

3.1.1 图的邻接矩阵存储表示本课题有邻接矩阵存储表示，邻接矩阵是表示顶点之间相邻关系的矩阵。

设G=(V,E) 是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵:A[ｉ,j]=1：若(Vｉ，V ｊ）是E（G)中的边;A[i,j]=0:若（Vi,Ｖj）不是Ｅ(G)中的边。

用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外,通常还需要用一个顺序表存储顶点信息。

因此，我们就要进行定义数据类型。

由于无向图的邻接矩阵是对称的,故采用压缩存储方式，仅存储上三角阵（不包括对角线上的元素）中的元素即可。

显然,邻接矩阵表示法的空间杂度S（ｎ)=O（n＾２）。

开始进行类型定义,用输入的方式来控制图的顶点数和边数，并对邻接矩阵进行初始化,将G->arｃs[i]［ｊ]=0,再从键盘上获得顶点信息，建立顶点表，在此同时G->aｒcs[i][j]=1，G->aｒcｓ[ｊ］[i]=1,最后输出邻接矩阵，用两层ｆor循环语句来控制。

３.1.2 图的邻接表存储表示另外还有邻接表的存储表示。

邻接表是一种链式的存储结构，在邻接表中,对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Ｖi的边。

每个结点由2个域组成，其中邻接点域（aｄjveｘ）指示与顶点Ｖｉ邻接的点在图中的位置，链域（ｎext)指示下一条边的结点。

所以一开始必须先定义邻接表的边结点类型以及邻接表类型,并对邻接表进行初始化,然后根据所输入的相关信息,包括图的顶点数、边数以及各条边的起点与终点序号，建立图的邻接表。

对于无向图，一条边的两的个顶点,互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。

同时将终点的单链表表头插入一边结点,即起点。

对于邻接表的输出,采用for语句输出各结点。

３．2 图的遍历和树的遍历类似,图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有的顶点各作一次访问。

若给定的图是连通图,则从图中任一顶点出发顺着边可以访问到该图的所有顶点。

图的遍历比树的遍历复杂得多，这是因为图中的任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后,可能顺着某条回路又回到了顶点。