邻接矩阵表示图_深度_广度优先遍历

*问题描述：

建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

1、邻接矩阵表示法:

设G=(V,E) 是一个图，其中V={V1,V2,V3…,Vn}。G 的邻接矩阵是一个他有下述性质的n 阶方阵：

1，若(Vi,Vj)∈E 或∈E ； A[i,j]={

0，反之

图5-2中有向图G1的邻接矩阵为 M1 M1=┌ 0 1 0 1 ┐

│ 1 0 1 0 │ │ 1 0 0 1 │ └ 0 0 0 0 ┘

用邻接矩阵表示法来表示一个具有n 个顶点的图时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n 个顶点的信息。因此其类型定义如下：

VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量

AdjMatrix arcs; // 邻接矩阵

int vexnum, arcnum; // 图的当前顶点数和弧(边) 数 GraphKind kind; // 图的种类标志

若图中每个顶点只含一个编号i(1≤i ≤vnum) ，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： type adjmatrix=array[1..vnum,1..vnum]of adj;

利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。

对于有向图，顶点Vi 的出度OD(Vi)为邻接矩阵第i 行元素之和，顶点Vi 的入度ID(Vi)为第i 列元素之和。即 n n OD(Vi)＝∑A[i,j]， OD(Vi)＝∑A[j,i]） j=1 j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若或(Vi,Vj) A[i,j]＝{

∞ , 否则。

其中Wij 为或(Vi,Vj)上的权值。相应地，网的邻接矩阵表示的类型定义应作如下的修改： adj:weightype ; {weightype为权类型}

2、图的遍历： *深度优先搜索

深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V 出发，访问此顶点，然后依次从V 的未被访问的邻接点出发深度优先遍历图，直至图中所有和V 有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。

以图中无向图G 4为例，深度优先遍历图的过程如图所示。假设从顶点V 1出发进行搜索，在访问了顶点V 1后，选择邻接点V 2。因为V 2未曾访问，则从V 2出发进行搜索。依次类推，接着从V 4,V 8,V 5出发进行搜索。在访问了V 5之后，由于V 5的邻接点已都被访问，则搜索回到V 8。由于同样的理由，搜索继续回到V 4，V 2直至V 1，此时由于V 1的另一个邻接点为被访问，则搜索又从V 1到V 3，再继续进行下去。由此得到顶点的访问序列为：

V V V V V V V 7

显然，这是一个递归的过程。为了在遍历过程中便于区别顶点是否已被访问，需附设访问标志数组visted[0...n-1],其初值为0，一但某个顶点被访问，则其相应的分量置为1。

2、图的输出

图的邻接矩阵是一个二维数组，运用for 语句的嵌套依次输出。

主程序流程图

图的构造流程图

1、无向图邻接矩阵的建立算法如下：

procedure build-graph; {建立无向图的邻接矩阵} begin

for i:=1 to n do read(G.vertex[i])； {读入n 个顶点的信息} for i:=1 to n do for j:=1 to e do G.arcs[i][j] =0；

{将邻接矩阵的每个元素初始化成0 } for k:=1 to e do {e为边的数目}

[ read(i,j,w) {读入边和权}G.arcs[i][j]:=w] G.arcs[i][j]＝G.arcs[i][i]｛置对称弧｝ end ；

该算法的执行时间是O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是O(n2), 而e

4、图的广度优先遍历算法分析 begin

for i:=1 to n do(visited[i]){初始化标志数组} while （i

｛for ：i ＝1 to n do｛if …..if ….. ｝｝

end

二维数组表示邻接矩阵作图的存储结构，其中n 为图中顶点数, 查找每个顶点的邻接点所需时间为O(n2) 。

/* Graph.h */

#include #include #include #include #include

#define ERROR 0 #define OK 1

#define MAX_VERTEX_NUM 20 //定义最大值 #define INFINITY 32768 //定义极大值 #define MAX_INFO 20

typedef int VrType; //定义新的类型 typedef int InfoType; typedef char VertexType;

typedef enum

{DG,DN,UDG,UDN}GraphKind;//有向图, 有向网, 无向图, 无向网 typedef struct ArcCell

{//邻接矩阵表示法的各个数据结构

VrType adj; // 顶点关系类型。对无权图，用或表示相邻否；对带权图，则为权值类型。

InfoType *info; // 该弧相关信息的指针

} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {

VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵

int vexnum, arcnum; // 图的当前顶点数和弧(边) 数 GraphKind kind; // 图的种类标志 } MGraph;

typedef struct {//设置栈

int elem1[MAX_VERTEX_NUM]; int top; }SeqStack;

int LocateVertex(MGraph G,VertexType v); void CreateUDG(MGraph &G);

void CreateUDN(MGraph &G); void DepthFirstSearch1(MGraph G); void BreadthFirstSearch1(MGraph G); int CreateGraph(MGraph &G); void Display(MGraph G);

/* Graph.cpp */

#include"Graph.h"

int LocateVertex(MGraph G,VertexType v) {//用于返回输弧端点所表示的数值 int j=0,k;

for (k=0;k

void CreateUDG(MGraph &G)

{ // 采用数组(邻接矩阵) 表示法, 构造无向图 int i,j,k,IncInfo;

//i，j ，k 为计数器,IncInfo 为标志符 char ch; //用于吃掉多余的字符

VertexType v1,v2; //用于放置输入的弧的两个顶点 printf(" 请输入无向图G 的顶点数, 边数, 弧是否含相关信息（是：，否：）: \n"); scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo); ch=getchar(); //用于吃掉回车

printf(" 请输入%d个顶点的值(1个字符，空格隔开):\n",G.vexnum); for (i=0;i

scanf("%c",&G.vertex[i]);ch=getchar(); }

printf(" 请输入%d条边的顶点顶点(以空格作为间隔): \n",G.arcnum); for (i=0;i

G.arcs[i][j].adj=0;

G.arcs[i][j].info=NULL; // {adj,info} }

for (k=0;k

scanf("%c %c",&v1,&v2);

ch=getchar();// ch吃掉回车符

i=LocateVertex(G,v1); j=LocateVertex(G,v2); if (IncInfo)scanf("%d",&G.arcs[i][j].info);

G.arcs[i][j].adj=G.arcs[j][i].adj=1; // 置的对称弧 }

}//CreateUDG

void CreateUDN(MGraph &G)

{ // 采用数组(邻接矩阵) 表示法, 构造无向网 int i,j,k,w,IncInfo;

//i，j ，k 为计数器，w 用于放置权值,IncInfo 为标志符 char ch; //用于吃掉多余的字符

VertexType v1,v2; //用于放置输入的弧的两个顶点

printf(" 请输入无向图G 的顶点数, 边数, 弧是否含相关信息（是：，否：）:\n " );

scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo); ch=getchar(); //用于吃掉回车

printf(" 请输入%d个顶点的值(1个字符，空格隔开):\n",G.vexnum); for (i=0;i

scanf("%c",&G.vertex[i]);ch=getchar(); }

printf(" 请输入%d条边的顶点顶点(以空格作为间隔): \n",G.arcnum); for (i=0;i

G.arcs[i][j].adj=0;

G.arcs[i][j].info=NULL; //{adj,info} }

for (k=0;k

scanf("%c %c",&v1,&v2);

ch=getchar();// ch吃掉回车符 printf(" 请输入该边的权值: "); scanf("%d",&w); ch=getchar();

i=LocateVertex(G,v1); j=LocateVertex(G,v2); G.arcs[i][j].adj=w;

if (IncInfo)scanf("%d",&G.arcs[i][j].info);

G.arcs[i][j]=G.arcs[j][i]; // 置的对称弧 }

}//CreateUDN

void DepthFirstSearch1(MGraph G) {//无向图、无向网深度优先遍历

int i,j,k,visited[20],t=1,a=1; //i,j,k为计数器，visited[20]为标志符用于表示是否已经访问过 SeqStack p;

for (i=0;i

visited[0]=1; //规定以第一个字符开始遍历 printf(" 深度优先遍历开始：\n"); k=0;i=0;

printf("%c ",G.vertex[0]); while (i

{//不断以行循环在遇到符合条件时打印，每打印出一个就让t 加，把合适的值用栈来表示，把指针指向新的项 for (j=0;j

if (G.arcs[i][j].adj!=0&&G.arcs[i][j].adj!=INFINITY&&visited[j]==0) {

printf("%c ",G.vertex[j]); visited[j]=1; p.elem1[k]=i; p.top=k;

k++;i++;a++;t++; break ; } }

if (j==G.vexnum)

{//当在某一行无法找到合适值时，输出栈内的值，返回上一行重新开始循环

i=p.elem1[p.top]; p.top--; k--; }

if (t==G.vexnum)break ; //当全部的定点都打印出来了就退出循环

}

printf("\n"); }

void BreadthFirstSearch1(MGraph G) {//无向图、无向网广度优先遍历

int i,j,k,visited[20],t=1; //i,j为计数器，visited[20]为标志符用于表示是否已经访问过 SeqStack p;

for (i=0;i

visited[0]=1; //规定以第一个字符开始遍历 printf(" 广度优先遍历开始：\n"); k=0;i=0;

printf("%c ",G.vertex[0]); while (i

for (j=0;j

if (G.arcs[i][j].adj!=0&&G.arcs[i][j].adj!=INFINITY&&visited[j]==0) {

printf("%c ",G.vertex[j]); visited[j]=1; p.elem1[k]=i; p.top=k; k++; t++; } }

i++; //换行，重新开始循环 if (t==G.vexnum)break ; }

printf("\n"); }

int CreateGraph(MGraph &G) { //构造图

printf(" 请输入要构造的图的类型(有向图:0,有向网:1,无向图:2,无向网:3):\n");

scanf ("%d",&G.kind); switch (G.kind) {

case 2: CreateUDG(G);break ;

case 3: CreateUDN(G);break ; default : return ERROR; }

}//CreateGraph

void Display(MGraph G) {//输出图的邻接矩阵 int i,j;

printf(" 该图的邻接矩阵为：\n"); for (i=0;i

{for (j=0;j

printf("%d ",G.arcs[i][j].adj); }

printf("\n"); } }

/* main.cpp */

#include"Graph.h" void main() {

int i; MGraph G;

CreateGraph(G);

DepthFirstSearch1(G); BreadthFirstSearch1(G); Display(G);

scanf("%d",&i);

1、程序开始运行时输出：

显示：请输入无向图G 的顶点数: 输入：5

显示：请输入无向图G 的边数: 输入：6

显示：请输入无向图G 的弧是否含相关信息（是：输入：0

，否：0）: 1

显示：请输入5个顶点的值(1个字符，空格隔开): 输入：1 2 3 4 5

显示：请输入%d条边的顶点1 顶点2(以空格作为间隔): 输入：1 2 1 4 2 3 2 5 3 4 3 5 显示：深度优先遍历开始：

1 2 3 4 5

广度优先遍历开始：

1 2 4 3 5

该图的邻接矩阵为：

0 1 0 1 0

1 0 1 0 1

0 1 0 1 1

1 0 1 0 0

0 1 1 0 0

请输入任意键退出

2、程序运行结果如图：

10

*问题描述：

建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

1、邻接矩阵表示法:

设G=(V,E) 是一个图，其中V={V1,V2,V3…,Vn}。G 的邻接矩阵是一个他有下述性质的n 阶方阵：

1，若(Vi,Vj)∈E 或∈E ； A[i,j]={

0，反之

图5-2中有向图G1的邻接矩阵为 M1 M1=┌ 0 1 0 1 ┐

│ 1 0 1 0 │ │ 1 0 0 1 │ └ 0 0 0 0 ┘

用邻接矩阵表示法来表示一个具有n 个顶点的图时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n 个顶点的信息。因此其类型定义如下：

VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量

AdjMatrix arcs; // 邻接矩阵

int vexnum, arcnum; // 图的当前顶点数和弧(边) 数 GraphKind kind; // 图的种类标志

若图中每个顶点只含一个编号i(1≤i ≤vnum) ，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： type adjmatrix=array[1..vnum,1..vnum]of adj;

利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。

对于有向图，顶点Vi 的出度OD(Vi)为邻接矩阵第i 行元素之和，顶点Vi 的入度ID(Vi)为第i 列元素之和。即 n n OD(Vi)＝∑A[i,j]， OD(Vi)＝∑A[j,i]） j=1 j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若或(Vi,Vj) A[i,j]＝{

∞ , 否则。

其中Wij 为或(Vi,Vj)上的权值。相应地，网的邻接矩阵表示的类型定义应作如下的修改： adj:weightype ; {weightype为权类型}

2、图的遍历： *深度优先搜索

深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V 出发，访问此顶点，然后依次从V 的未被访问的邻接点出发深度优先遍历图，直至图中所有和V 有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。

以图中无向图G 4为例，深度优先遍历图的过程如图所示。假设从顶点V 1出发进行搜索，在访问了顶点V 1后，选择邻接点V 2。因为V 2未曾访问，则从V 2出发进行搜索。依次类推，接着从V 4,V 8,V 5出发进行搜索。在访问了V 5之后，由于V 5的邻接点已都被访问，则搜索回到V 8。由于同样的理由，搜索继续回到V 4，V 2直至V 1，此时由于V 1的另一个邻接点为被访问，则搜索又从V 1到V 3，再继续进行下去。由此得到顶点的访问序列为：

V V V V V V V 7

显然，这是一个递归的过程。为了在遍历过程中便于区别顶点是否已被访问，需附设访问标志数组visted[0...n-1],其初值为0，一但某个顶点被访问，则其相应的分量置为1。

2、图的输出

图的邻接矩阵是一个二维数组，运用for 语句的嵌套依次输出。

主程序流程图

图的构造流程图

1、无向图邻接矩阵的建立算法如下：

procedure build-graph; {建立无向图的邻接矩阵} begin

for i:=1 to n do read(G.vertex[i])； {读入n 个顶点的信息} for i:=1 to n do for j:=1 to e do G.arcs[i][j] =0；

{将邻接矩阵的每个元素初始化成0 } for k:=1 to e do {e为边的数目}

[ read(i,j,w) {读入边和权}G.arcs[i][j]:=w] G.arcs[i][j]＝G.arcs[i][i]｛置对称弧｝ end ；

该算法的执行时间是O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是O(n2), 而e

4、图的广度优先遍历算法分析 begin

for i:=1 to n do(visited[i]){初始化标志数组} while （i

｛for ：i ＝1 to n do｛if …..if ….. ｝｝

end

二维数组表示邻接矩阵作图的存储结构，其中n 为图中顶点数, 查找每个顶点的邻接点所需时间为O(n2) 。

/* Graph.h */

#include #include #include #include #include

#define ERROR 0 #define OK 1

#define MAX_VERTEX_NUM 20 //定义最大值 #define INFINITY 32768 //定义极大值 #define MAX_INFO 20

typedef int VrType; //定义新的类型 typedef int InfoType; typedef char VertexType;

typedef enum

{DG,DN,UDG,UDN}GraphKind;//有向图, 有向网, 无向图, 无向网 typedef struct ArcCell

{//邻接矩阵表示法的各个数据结构

VrType adj; // 顶点关系类型。对无权图，用或表示相邻否；对带权图，则为权值类型。

InfoType *info; // 该弧相关信息的指针

} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {

VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵

int vexnum, arcnum; // 图的当前顶点数和弧(边) 数 GraphKind kind; // 图的种类标志 } MGraph;

typedef struct {//设置栈

int elem1[MAX_VERTEX_NUM]; int top; }SeqStack;

int LocateVertex(MGraph G,VertexType v); void CreateUDG(MGraph &G);

void CreateUDN(MGraph &G); void DepthFirstSearch1(MGraph G); void BreadthFirstSearch1(MGraph G); int CreateGraph(MGraph &G); void Display(MGraph G);

/* Graph.cpp */

#include"Graph.h"

int LocateVertex(MGraph G,VertexType v) {//用于返回输弧端点所表示的数值 int j=0,k;

for (k=0;k

void CreateUDG(MGraph &G)

{ // 采用数组(邻接矩阵) 表示法, 构造无向图 int i,j,k,IncInfo;

//i，j ，k 为计数器,IncInfo 为标志符 char ch; //用于吃掉多余的字符

VertexType v1,v2; //用于放置输入的弧的两个顶点 printf(" 请输入无向图G 的顶点数, 边数, 弧是否含相关信息（是：，否：）: \n"); scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo); ch=getchar(); //用于吃掉回车

printf(" 请输入%d个顶点的值(1个字符，空格隔开):\n",G.vexnum); for (i=0;i

scanf("%c",&G.vertex[i]);ch=getchar(); }

printf(" 请输入%d条边的顶点顶点(以空格作为间隔): \n",G.arcnum); for (i=0;i

G.arcs[i][j].adj=0;

G.arcs[i][j].info=NULL; // {adj,info} }

for (k=0;k

scanf("%c %c",&v1,&v2);

ch=getchar();// ch吃掉回车符

i=LocateVertex(G,v1); j=LocateVertex(G,v2); if (IncInfo)scanf("%d",&G.arcs[i][j].info);

G.arcs[i][j].adj=G.arcs[j][i].adj=1; // 置的对称弧 }

}//CreateUDG

void CreateUDN(MGraph &G)

{ // 采用数组(邻接矩阵) 表示法, 构造无向网 int i,j,k,w,IncInfo;

//i，j ，k 为计数器，w 用于放置权值,IncInfo 为标志符 char ch; //用于吃掉多余的字符

VertexType v1,v2; //用于放置输入的弧的两个顶点

printf(" 请输入无向图G 的顶点数, 边数, 弧是否含相关信息（是：，否：）:\n " );

scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo); ch=getchar(); //用于吃掉回车

printf(" 请输入%d个顶点的值(1个字符，空格隔开):\n",G.vexnum); for (i=0;i

scanf("%c",&G.vertex[i]);ch=getchar(); }

printf(" 请输入%d条边的顶点顶点(以空格作为间隔): \n",G.arcnum); for (i=0;i

G.arcs[i][j].adj=0;

G.arcs[i][j].info=NULL; //{adj,info} }

for (k=0;k

scanf("%c %c",&v1,&v2);

ch=getchar();// ch吃掉回车符 printf(" 请输入该边的权值: "); scanf("%d",&w); ch=getchar();

i=LocateVertex(G,v1); j=LocateVertex(G,v2); G.arcs[i][j].adj=w;

if (IncInfo)scanf("%d",&G.arcs[i][j].info);

G.arcs[i][j]=G.arcs[j][i]; // 置的对称弧 }

}//CreateUDN

void DepthFirstSearch1(MGraph G) {//无向图、无向网深度优先遍历

int i,j,k,visited[20],t=1,a=1; //i,j,k为计数器，visited[20]为标志符用于表示是否已经访问过 SeqStack p;

for (i=0;i

visited[0]=1; //规定以第一个字符开始遍历 printf(" 深度优先遍历开始：\n"); k=0;i=0;

printf("%c ",G.vertex[0]); while (i

{//不断以行循环在遇到符合条件时打印，每打印出一个就让t 加，把合适的值用栈来表示，把指针指向新的项 for (j=0;j

if (G.arcs[i][j].adj!=0&&G.arcs[i][j].adj!=INFINITY&&visited[j]==0) {

printf("%c ",G.vertex[j]); visited[j]=1; p.elem1[k]=i; p.top=k;

k++;i++;a++;t++; break ; } }

if (j==G.vexnum)

{//当在某一行无法找到合适值时，输出栈内的值，返回上一行重新开始循环

i=p.elem1[p.top]; p.top--; k--; }

if (t==G.vexnum)break ; //当全部的定点都打印出来了就退出循环

}

printf("\n"); }

void BreadthFirstSearch1(MGraph G) {//无向图、无向网广度优先遍历

int i,j,k,visited[20],t=1; //i,j为计数器，visited[20]为标志符用于表示是否已经访问过 SeqStack p;

for (i=0;i

visited[0]=1; //规定以第一个字符开始遍历 printf(" 广度优先遍历开始：\n"); k=0;i=0;

printf("%c ",G.vertex[0]); while (i

for (j=0;j

if (G.arcs[i][j].adj!=0&&G.arcs[i][j].adj!=INFINITY&&visited[j]==0) {

printf("%c ",G.vertex[j]); visited[j]=1; p.elem1[k]=i; p.top=k; k++; t++; } }

i++; //换行，重新开始循环 if (t==G.vexnum)break ; }

printf("\n"); }

int CreateGraph(MGraph &G) { //构造图

printf(" 请输入要构造的图的类型(有向图:0,有向网:1,无向图:2,无向网:3):\n");

scanf ("%d",&G.kind); switch (G.kind) {

case 2: CreateUDG(G);break ;

case 3: CreateUDN(G);break ; default : return ERROR; }

}//CreateGraph

void Display(MGraph G) {//输出图的邻接矩阵 int i,j;

printf(" 该图的邻接矩阵为：\n"); for (i=0;i

{for (j=0;j

printf("%d ",G.arcs[i][j].adj); }

printf("\n"); } }

/* main.cpp */

#include"Graph.h" void main() {

int i; MGraph G;

CreateGraph(G);

DepthFirstSearch1(G); BreadthFirstSearch1(G); Display(G);

scanf("%d",&i);

1、程序开始运行时输出：

显示：请输入无向图G 的顶点数: 输入：5

显示：请输入无向图G 的边数: 输入：6

显示：请输入无向图G 的弧是否含相关信息（是：输入：0

，否：0）: 1

显示：请输入5个顶点的值(1个字符，空格隔开): 输入：1 2 3 4 5

显示：请输入%d条边的顶点1 顶点2(以空格作为间隔): 输入：1 2 1 4 2 3 2 5 3 4 3 5 显示：深度优先遍历开始：

1 2 3 4 5

广度优先遍历开始：

1 2 4 3 5

该图的邻接矩阵为：

0 1 0 1 0

1 0 1 0 1

0 1 0 1 1

1 0 1 0 0

0 1 1 0 0

请输入任意键退出

2、程序运行结果如图：

10


相关文章

  • 数据结构--图的基本操作

    • 1．实验题目 图的基本操作 2．实验目的 1) 掌握图的邻接矩阵.邻接表的表示方法. 2) 掌握建立图的邻接矩阵的算法. 3) 掌握建立图的邻接表的算法. 4) 加深对图的理解,逐步培养解决实际问题的编程能力 3．需求分析 (1)编写图基本 ...查看


  • 数据结构答案

    • 第一章 一.选择题 1 从逻辑上可以把数据结构分为( C)两大类. A ．动态结构.静态结构 B．顺序结构.链式结构 C ．线性结构.非线性结构 D．初等结构.构造型结构 2在下面的程序段中,对x 的赋值语句的频度为(C ) FOR i:= ...查看


  • 图的遍历与最小生成树

    • 二中信息学奥赛培训讲义 图论1--图的遍历与图的最小生成树 一.图的遍历 图的遍历:从图的某顶点出发,访问图中所有顶点,并且每个顶点仅访问一次.在图中,访问部分顶点后,可能又沿着其他边回到已被访问过的顶点.为保证每一个顶点只被访问一次,必须 ...查看


  • 数据结构A教学大纲

    • 数据结构A 教学大纲 (Data Structures A) 课程编号: 06311360 学 分: 5.0 学 时: 75 (其中:讲课学时:60 实验学时:0 上机学时:15) 先修课程:离散数学.程序设计基础.面向对象程序设计 适用专 ...查看


  • 数据结构导论试题1

    • 全国2004年10月高等教育自学考试 1.要将现实生活中的数据转化为计算机所能表示的形式,其转化过程依次为( ) A.逻辑结构.存储结构.机外表示 B.存储结构.逻辑结构.机外表示 C.机外表示.逻辑结构.存储结构 D.机外表示.存储结构. ...查看


  • 数据结构与算法试卷A答案

    • 滁州学院2013/2014学年度第一学期期末考试试卷参考答案 1开始的按照所画的邻接矩阵写出深度优先遍历和广度优先遍历顺序. :号学 :名姓 :班级/级年 :业专 级<数据结构与算法>A 卷 邻接矩阵 0101000 (时间12 ...查看


  • 04年工硕数据结构试题及答案

    • 注:1.除第九题外,其他各题每题10分,第九题20分. 2.所有试题的答案写在答题纸上. 一.判断下列叙述的对错. (1)线性表的逻辑顺序与物理顺序总是一致的. (2)线性表的顺序存储表示优于链式存储表示. (3)线性表若采用链式存储表示时 ...查看


  • 邻接矩阵的深度优先遍历

    • #include #include using namespace std; #define INFINITY 32767 #define MAX_VEX 50 #define OK 1 #define FALSE 0 #define TR ...查看


  • [数据结构]期末考试题及答案

    • 2011-2012学年第一学期期末考查 <数据结构>试卷 (答案一律写在答题纸上,在本试卷上做答无效) 一.选择(每题1分,共10分) 1. 长度为n 的线性表采用顺序存储结构,一个在其第i 个位置插入新元素的算法时间复杂度为( ...查看


热门内容