当前位置:文档之家› 邻接矩阵表示图_深度_广度优先遍历

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

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

.

*问题描述:

建立图的存储结构(图的类型可以是有向图、无向图、有向网、无向网,学生可以任选两种类型),能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵。

1、邻接矩阵表示法:

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

1,若(Vi,Vj)∈E 或∈E;

A[i,j]={

0,反之

图5-2中有向图G1和无向图G2的邻接矩阵分别为M1和M2:

M1=┌0 1 0 1 ┐

│1 0 1 0 │

│1 0 0 1 │

└0 0 0 0 ┘

M2=┌0 1 1 1 ┐

│1 0 1 0 │

│1 1 0 1 │

└1 0 1 0 ┘

注意无向图的邻接是一个对称矩阵,例如M2。

用邻接矩阵表示法来表示一个具有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的度是邻接矩阵中第i行元素之和,即

n n

D(Vi)=∑A[i,j] (或∑A[i,j])

j=1 i=1

对于有向图,顶点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为权类型} 图5-6列出一个网和它的邻接矩阵。

┌∞31∞∞┐

│∞∞51∞│

│∞∞∞∞∞│

│∞∞6∞∞│

└∞322∞┘

(a)网(b)邻接矩阵

图5-6 网及其邻接矩阵

对无向图或无向网络,由于其邻接矩阵是对称的,故可采用压缩存贮的方法,仅存贮下三角或上三角中的元素(但不含对角线上的元素)即可。显然,邻接矩阵表示法的空间复杂度O()。

无向网邻接矩阵的建立方法是:首先将矩阵A的每个元素都初始化成∞。然后,读入边及权值(i,j,wij),将A的相应元素置成Wij。

2、图的遍历:

*深度优先搜索

深度优先搜索遍历类似于树的先根遍历,是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问,则深度优先遍历可从图的某个顶点V出发,

访问此顶点,然后依次从V的未被访问的邻接点出发深度优先遍历图,直至图中所有和V有路径相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中的一个未被访问的顶点,重复上述过程,直至图中所有顶点都被访问到为止。

以图7.13(a)中无向图G4为例,深度优先遍历图的过程如图7.13(b)所示。假设从顶点V1出发进行搜索,在访问了顶点V1后,选择邻接点V2。因为V2未曾访问,则从V2出发进行搜索。依次类推,接着从V4,V8,V5出发进行搜索。在访问了V5之后,由于V5的邻接点已都被访问,则搜索回到V8。由于同样的理由,搜索继续回到V4,V2直至V1,此时由于V1的另一个邻接点为被访问,则搜索又从V1到V3,再继续进行下去。由此得到顶点的访问序列为:V1 V V4 V8 V5 V3 V6 V7

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

*广度优先搜索

假设从图中某顶点v出发,在访问了v之后一次访问v的各个未曾访问的扩大邻接点,然后分别从这些邻接点出发依次访问他们的邻接点,并使“先被访问的邻接点”先于“后被访问的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直到图中的顶点都被访问为止。换句话说,广度优先遍历图的过程就是以v为起始点,有远至近,依次访问和v有路径相通且路径长度为1、2……的顶点。例如,对图G4进行广度优先搜索遍历的过程如图7.13(3)

所示,首先访问v1和v1的邻接点v2和v3,然后依次访问v2的邻接点v4和v5及v3的邻接点v6和v7,最后访问v4的邻接点v8。由于这些顶点的邻接点均已被访问,并且图中所有顶点都被访问,由此完成了图的遍历。得到的顶点访问序列为

V 1 V 2 V 3 V 4 V 5 V 6 V

7 V 8

和深度优先搜索类似,在遍历的过程中也需要一个访问标志数组。并且,为了顺次访问路径长度为2、3、…的顶点,需附设队列以存储已被访问的路径长

度为1、2…的顶点。

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

2、无向网邻接矩阵的建立算法如下:

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] =maxint;

{将邻接矩阵的每个元素初始化成maxint,计算机内∞用最大事数maxint表示} for k:=1 to e do {e为边的数目}

[ read(i,j,w) {读入边和权}G.arcs[i][j]:=w; G.arcs[i][j]:=w] end;

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

3、图的深度优先遍历算法分析

begin

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

while (i

{for:i=1 to n do{按要求访问邻接点}}

end

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

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

begin

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

while (i

{for:i=1 to n do{if…..if…..}}

end

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

#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 */

int LocateVertex(MGraph G,VertexType v)

{//用于返回输弧端点所表示的数值

int j=0,k;

for(k=0;k

if(G.vertex[k]==v)

{j=k;break;}

return(j);

}

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

for(j=0;j

{

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

for(j=0;j

{

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[i]=0;

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[i]=0;

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 */

void main()

{

int i;

MGraph G;

CreateGraph(G);

DepthFirstSearch1(G);

BreadthFirstSearch1(G);

Display(G);

scanf("%d",&i);

}

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

请输入要构造的图的类型(有向图:0,有向网:1,无向图:2,无向网:3): 为了测试输入为:2

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

输入:5

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

输入:6

显示:请输入无向图G的弧是否含相关信息(是:1,否:0):

输入:0

显示:请输入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、程序运行结果如图:

图的邻接矩阵存储结构建立汇总

课程名称: 《数据结构》课程设计课程设计题目:图的邻接矩阵存储结构建立 姓名:XXX 院系:计算机学院 专业:计算机科学技术 年级:11级 学号:XXXXXXXX 指导教师:XXX 2013年9月28日

目录 1 课程设计的目的 (3) 2需求分析 (3) 3 课程设计报告内容 (3) 3.1 概要设计 (3) 3.2 详细设计 (4) 3.3 调试分析 (5) 3.4 用户手册 (5) 3.5 程序清单 (5) 3.6 测试结果 (10) 4 小结 (12) 5 参考文献 (12)

1.课程设计的目的 (1) 熟练使用 C 语言编写程序,解决实际问题; (2) 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 2.需求分析 问题描述:建立图的邻接矩阵存储结构(图的类型可以是有向图或有向网、无向图或无向网,学生可以任选一种类型),能够输入图的顶点和边的信息,并存储到相应存储结构中,而后给出图的DFS,BFS次序。 要求: ①先任意创建一个图; ②图的DFS,BFS的递归和非递归算法的实现。 3.课程设计报告内容 3.1概要设计 1.函数 ①主函数:main( ) ②创建无向图:CreateGraph( )

③深度优先遍历图:DFS( ) ④广度优先遍历图:BFS( ) 3.2详细设计 1.使用邻接矩阵作为图的存储结构,程序中主要用到的抽象数据类型: typedef struct { char vexs[MAX]; //顶点向量 int arcs[MAX][MAX]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数}Graph; 2.程序流程图:

连通图深度优先遍历

#include #include #define MAXLEN 20 typedef struct node3 { int adjvex; struct node3 *next; }ARCNODE; typedef struct { char data; ARCNODE *firstarc; int id; } VEXNODE; typedef struct { VEXNODE vertices[MAXLEN]; int vexnum, arcnum; int kind; }ALGRAPH; int visited[MAXLEN]; ALGRAPH creat_graph() { ARCNODE *p; int i, s, d; ALGRAPH g; printf("\n\n输入顶点数和边数(用逗号隔开) : "); scanf("%d,%d", &s, &d);fflush(stdin); g.vexnum = s; /*存放顶点数在g.vexnum 中 */ g.arcnum = d; /*存放边点数在g.arcnum 中*/ printf("\n\n"); for(i = 0; i < g.vexnum; i++) /*输入顶点的值*/ {printf("输入顶点 %d 的值 : ", i + 1); scanf("%c", &g.vertices[i].data); fflush(stdin); g.vertices[i].firstarc = NULL;} printf("\n"); for(i = 0; i < g.arcnum; i++) {printf("输入第 %d 条边的起始顶点和终止顶点下标(用逗号隔开): ", i+1);

图的邻接矩阵存储及遍历

实验五 图的邻接矩阵存储及遍历 一、实验学时 2学时 二、背景知识 1.图的邻接矩阵存储结构 设图G =(V ,E )有 n>=1个顶点,其编号分别为1,2,…,n 。描述图G 的邻接矩阵 为二维数组A[1…n ,1…n],A 的元素定义为: A []j i ,=???,,01否则)属于)或(若(E ,,i j j i v v v v 显然无向图的邻接矩阵一定是对称的。 对于网,其邻接矩阵A 的元素定义为: A []j i ,=?? ???∞=无邻接边到顶点若顶点若为该边上的权有邻接边,到顶点若顶点j i j i w j i w j i j i 0,, 2.图的遍历 深度优先遍历(DFS )法: 算法步骤: 1)初始化: (1)置所有顶点“未访问”标志; (2)打印起始顶点; (3)置起始顶点“已访问”标志; (4)起始顶点进栈。 2)当栈非空时重复做: (1)取栈顶点; (2)如栈顶顶点存在被访问过的邻接顶点,则选择一个顶点做: ① 打印该顶点; ② 置顶点为“已访问”标志; ③ 该顶点进栈; 否则,当前栈顶顶点退栈。 3)结束。 广度优先遍历(BFS )法: 算法步骤: 1) 初始化: (1)置所有顶点“未访问”标志; (2)打印起始顶点; (3)置起始顶点“已访问”标志; (4)起始顶点入队。 2)当队列非空时重复做: (1)取队首顶点; (2)对与队首顶点邻接的所有未被访问的顶点依次做: ① 打印该顶点; ② 置顶点为“已访问”标志; ③ 该顶点入队;

否则,当前队首顶点出队。 3) 结束。 三、目的要求 1.掌握图的基本存储方法; 2.掌握有关图的操作算法并用高级语言实现; 3.熟练掌握图的两种搜索路径的遍历方法。 四、实验内容 编写程序实现下图的邻接矩阵表示及其基础上的深度和广度优先遍历。 五、程序实例 图的邻接矩阵表示法的C语言描述: #include #include #include #define INFINITY 32767 #define MAX_VERTEX_MUN 20 int visited[20]; typedef struct ArcCell { int adj; char *info; }ArcCell,AdjMatrix[20][20]; typedef struct { char vexs[20]; AdjMatrix arcs; int vexnum,arcnum; }MGragh; typedef struct QNode { int data; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue;

图的深度优先遍历实验报告

一.实验目的 熟悉图的存储结构,掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法,并能运用图的深度优先搜索遍历一个图,对其输出。 二.实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问,则深度优先搜索可从图中某个顶点v出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,直至图中所有与v有路径相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未曾访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。 图的邻接表的存储表示: #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三.实验内容 编写LocateVex函数,Create函数,print函数,main函数,输入要构造的图的相关信息,得到其邻接表并输出显示。 四。实验步骤 1)结构体定义,预定义,全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20

图的邻接矩阵和邻接表相互转换

图的邻接矩阵和邻接表相互转换 图的邻接矩阵存储方法具有如下几个特征:1)无向图的邻接矩阵一定是一个对称矩阵。 2)对于无向图的邻接矩阵的第i 行非零元素的个数正好是第i 个顶点的度()i v TD 。3)对于有向图,邻接矩阵的第i 行非零元素的个数正好是第i 个顶点的出度()i v OD (或入度 ()i v ID ) 。4)用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连;但是,要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所发费得时间代价大。 邻接表是图的一种顺序存储与链式存储相结合的存储方法。若无向图中有n 个顶点、e 条边,则它的邻接表需n 个头结点和2e 个表结点。显然,在边稀疏的情况下,用邻接表表示图比邻接矩阵存储空间。在无向图的邻接表中,顶点i v 的度恰好是第i 个链表中的结点数,而在有向图中,第i 个链表中结点个数是顶点i v 的出度。 在建立邻接表或邻逆接表时,若输入的顶点信息即为顶点的编号,则建立临接表的时间复杂度是)(e n O +;否则,需要通过查找才能得到顶点在图中位置,则时间复杂度为)*(e n O 。在邻接表上容易找到任意一顶点的第一个邻接点和下一个邻接点,但要判断任意两个顶点之间是否有边或弧,则需要搜索第i 个或第j 个链表,因此,不及邻接矩阵方便。 邻接矩阵和邻接表相互转换程序代码如下: #include #define MAX 20 //图的邻接表存储表示 typedef struct ArcNode{ int adjvex; //弧的邻接定点 char info; //邻接点值 struct ArcNode *nextarc; //指向下一条弧的指针 }ArcNode; typedef struct Vnode{ //节点信息 char data; ArcNode *link; }Vnode,AdjList[MAX]; typedef struct{ AdjList vertices; int vexnum; //节点数 int arcnum; //边数

深度优先遍历(邻接矩阵)

上机实验报告 学院:计算机与信息技术学院 专业:计算机科学与技术(师范)课程名称:数据结构 实验题目:深度优先遍历(邻接矩阵)班级序号:师范1班 学号:201421012731 学生姓名:邓雪 指导教师:杨红颖 完成时间:2015年12月25号

一、实验目的: 1﹒掌握图的基本概念和邻接矩阵存储结构。 2﹒掌握图的邻接矩阵存储结构的算法实现。 3﹒掌握图在邻接矩阵存储结构上遍历算法的实现。 二、实验环境: Windows 8.1 Microsoft Visual c++ 6.0 二、实验内容及要求: 编写图的深度优先遍历邻接矩阵算法。建立图的存储结构,能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵。 四、概要设计: 深度优先搜索遍历类似于树的先根遍历,是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问,则深度优先遍历可从图的某个顶点V出发,访问此顶点,然后依次从V的未被访问的邻接点出发深度优先遍历图,直至图中所有和V有路径相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中的一个未被访问的顶点,重复上述过程,直至图中所有顶点都被访问到为止。 以图中无向图G4为例,深度优先遍历图的过程如图所示。假设从顶点V1出发进行搜索,在访问了顶点V1后,选择邻接点V2。因为V2未曾访问,则从V2出发进行搜索。依次类推,接着从V4,V8,V5出发进行搜索。在访问了V5之后,由于V5的邻接点已都被访问,则搜索回到V8。由于同样的理由,搜索继续回到V4,V2直至V1,此时由于V1的另一个邻接点为被访问,则搜索又从V1到V3,再继续进行下去。由此得到顶点的访问序列为: V1 V2 V4 V8 V5 V3 V6 V7 五、代码 #include #include #define n 8 #define e 9 typedef char vextype; typedef float adjtype; int visited[n]; //定义结构体

数据结构课程设计-图的邻接矩阵

数据结构 课程设计报告 设计题目:图的邻接矩阵存储结构 院系计算机学院 年级x 级 学生xxxx 学号xxxxxxxxxx 指导教师xxxxxxxxx 起止时间10-6/10-10 2013年10月10日

目录 1 需求分析 (4) 2 概要设计 (4) 2.1 ADT描述 (4) 2.2程序模块结构 (5) 2.3各功能模块 (6) 3详细设计 (7) 3.1类的定义 (7) 3.2 初始化 (8) 3.3 图的构建操作 (8) 3.4 输出操作 (9) 3.5 get操作 (9) 3.6 插入操作 (10) 3.7 删除操作 (100) 3.8 求顶点的度操作 (111) 3.9 深度遍历作 (11) 3.10 判断连通操作 (12) 3.11 主函数 (13) 4 调试分析 (16) 4.1调试问题 (16) 4.2 算法时间复杂度 (16) 5用户手册 (16) 5.1主界面 (16) 5.2 创建图 (17) 5.3插入节点 (17) 5.4 深度优先遍历 (17) 5.5 求各顶点的度 (18) 5.6 输出图 (18) 5.7 判断是否连通 (19) 5.8 求边的权值 (19) 5.9 插入边 (19) 5.10 删除边 (20) 结论 (20) 参考文献 (20)

摘要 随着计算机的普及,涉及计算机相关的科目也越来越普遍,其中数据结构是计算机专业重要的专业基础课程与核心课程之一,为适应我国计算机科学技术的发展和应用,学好数据结构非常必要,然而要掌握数据结构的知识非常难,所以对“数据结构”的课程设计比不可少。本说明书是对“无向图的邻接矩阵存储结构”课程设计的说明。 首先是对需求分析的简要阐述,说明系统要完成的任务和相应的分析,并给出测试数据。其次是概要设计,说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系,以及ADT描述。然后是详细设计,描述实现概要设计中定义的基本功操作和所有数据类型,以及函数的功能及代码实现。再次是对系统的调试分析说明,以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述,然后是测试的数据和结果的分析,最后是对本次课程设计的结论。 关键词:网络化;计算机;对策;图;储存。

图的遍历实验报告

实验四:图的遍历 题目:图及其应用——图的遍历 班级:姓名:学号:完成日期: 一.需求分析 1.问题描述:很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序,演示在连通的无向图上访问全部结点的操作。 2.基本要求:以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据:教科书图7.33。暂时忽略里程,起点为北京。 4.实现提示:设图的结点不超过30个,每个结点用一个编号表示(如果一个图有n个结点,则它们的编号分别为1,2,…,n)。通过输入图的全部边输入一个图,每个边为一个数对,可以对边的输入顺序作出某种限制,注意,生成树的边是有向边,端点顺序不能颠倒。 5.选作内容: (1).借助于栈类型(自己定义和实现),用非递归算法实现深度优先遍历。 (2).以邻接表为存储结构,建立深度优先生成树和广度优先生成树,再按凹入表或树形打印生成树。 二.概要设计 1.为实现上述功能,需要有一个图的抽象数据类型。该抽象数据类型的定义为: ADT Graph { 数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。 数据关系R: R={VR} VR={ | v,w v且P(v,w),表示从v到w得弧,谓词P(v,w)定义了弧的意义或信息} } ADT Graph 2.此抽象数据类型中的一些常量如下: #define TRUE 1 #define FALSE 0 #define OK 1 #define max_n 20 //最大顶点数 typedef char VertexType[20]; typedef enum{DG, DN, AG, AN} GraphKind; enum BOOL{False,True}; 3.树的结构体类型如下所示:

数据结构与算法-图的邻接矩阵

实验报告实验日期:数据结构与算法课程: 图的邻接矩阵实验名称: 一、实验目的掌握图的邻接矩阵 二、实验内容必做部分 、给出图的邻接矩阵存储结构的类型定义。1 -1。v,返回其在vexs数组中的下标,否则返回2、实现LocateVex(G,v)操作函数:若找到顶点。、实现算法7.2(构造无向网)3&G) Status CreateUDN(MGraph 设计并实现无向网的输出算法,要求能显示顶点以及顶点之间的邻接关系(方式自定)4、 并进行输出。要求给出至少两组测试数据。在主函数中调用CreateUDN创建一个无向网,5、 选做部分 类型)编写下述操作函数:基于图的邻接矩阵存储结构(即MGraph若找不到这样返回该邻接点在顶点数组中的下标;1个邻接点,1、求下标为v的顶点的第-1。的邻接点,返回int FirstAdjVex(MGraph G,int v) 的顶点的下一个邻接点,返回该邻接点的下标;若w求下标为v的顶点相对于下标为2、找不到这样的邻接点,返回-1。 int NextAdjVex(MGraph G,int v,int w) 在主函数调用上述函数,给出测试结果。 三、实验步骤 必做部分 给出图的邻接矩阵存储结构的类型定义。、 1.

2、实现LocateVex(G,v)操作函数:若找到顶点v,返回其在vexs数组中的下标,否则返回-1。 3、实现算法7.2(构造无向网)。 &G) CreateUDN(MGraph Status

设计并实现无向网的输出算法,要求能显示顶点以及顶点之间的邻接关系(方式自定)、

4. 要求给出至少两组测试数据。并进行输出。、在主函数中调用CreateUDN创建一个无向网,5

实现图的邻接矩阵和邻接表存储

实现图的邻接矩阵和邻接表存储 1.需求分析 对于下图所示的有向图G,编写一个程序完成如下功能: 1.建立G的邻接矩阵并输出之 2.由G的邻接矩阵产生邻接表并输出之 3.再由2的邻接表产生对应的邻接矩阵并输出之 2.系统设计 1.图的抽象数据类型定义: ADT Graph{ 数据对象V:V是具有相同特性的数据元素的集合,称为顶点集 数据关系R: R={VR} VR={|v,w∈V且P(v,w),表示从v到w的弧, 谓词P(v,w)定义了弧的意义或信息} 基本操作P: CreatGraph(&G,V,VR) 初始条件:V是图的顶点集,VR是图中弧的集合 操作结果:按V和VR的定义构造图G DestroyGraph(&G) 初始条件:图G存在 操作结果:销毁图G InsertVex(&G,v) 初始条件:图G存在,v和图中顶点有相同特征 操作结果:在图G中增添新顶点v …… InsertArc(&G,v,w) 初始条件:图G存在,v和w是G中两个顶点 操作结果:在G中增添弧,若G是无向的则还增添对称弧 …… DFSTraverse(G,Visit()) 初始条件:图G存在,Visit是顶点的应用函数 操作结果:对图进行深度优先遍历,在遍历过程中对每个顶点调用函数Visit一次且仅一次。

一旦Visit()失败,则操作失败 BFSTraverse(G,Visit()) 初始条件:图G存在,Visit是顶点的应用函数 操作结果:对图进行广度优先遍历,在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败,则操作失败 }ADT Graph 2.主程序的流程: 调用CreateMG函数创建邻接矩阵M; 调用PrintMatrix函数输出邻接矩阵M 调用CreateMGtoDN函数,由邻接矩阵M创建邻接表G 调用PrintDN函数输出邻接表G 调用CreateDNtoMG函数,由邻接表M创建邻接矩阵N 调用PrintMatrix函数输出邻接矩阵N 3.函数关系调用图: 3.调试分析 (1)在MGraph的定义中有枚举类型 typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网} 赋值语句G.kind(int)=M.kind(GraphKind);是正确的,而反过来M.kind=G.kind则是错误的,要加上那个强制转换M.kind=GraphKind(G.kind);枚举类型enum{DG,DN,UDG,UDN} 会自动赋值DG=0;DN=1,UDG=2,UDN=3;可以自动从GraphKind类型转换到int型,但不会自动从int型转换到GraphKind类型

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

*问题描述: 建立图的存储结构(图的类型可以是有向图、无向图、有向网、无向网,学生可以任选两种类型),能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图,其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵: 1,若(Vi,Vj)∈E 或∈E; A[i,j]={ 0,反之 图5-2中有向图G1和无向图G2的邻接矩阵分别为M1和M2: M1=┌0 1 0 1 ┐ │ 1 0 1 0 │ │ 1 0 0 1 │ └0 0 0 0 ┘ M2=┌0 1 1 1 ┐ │ 1 0 1 0 │ │ 1 1 0 1 │ └ 1 0 1 0 ┘ 注意无向图的邻接是一个对称矩阵,例如M2。 用邻接矩阵表示法来表示一个具有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的度是邻接矩阵中第i行元素之和,即 n n D(Vi)=∑A[i,j](或∑A[i,j]) j=1 i=1 对于有向图,顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和,顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)=∑A[i,j],OD(Vi)=∑A[j,i]) j=1j=1 用邻接矩阵也可以表示带权图,只要令 Wij, 若或(Vi,Vj) A[i,j]={ ∞, 否则。 其中Wij为或(Vi,Vj)上的权值。相应地,网的邻接矩阵表示的类型定义应作如下的修改:adj:weightype ; {weightype为权类型} 图5-6列出一个网和它的邻接矩阵。 ┌∞31∞∞┐ │∞∞51∞│ │∞∞∞∞∞│ │∞∞6∞∞│ └∞322∞┘ (a)网(b)邻接矩阵 图5-6 网及其邻接矩阵 对无向图或无向网络,由于其邻接矩阵是对称的,故可采用压缩存贮的方法,

用邻接矩阵表示法创建有向图(数据结构)

#include #include #include #define MAX_VERTEX_NUM 20 //定义最多顶点个数 #define INFINITY32768 //定义无穷大 //描述图的类型,用枚举型类型来说明 typedef enum{DG,DN,UDG,UDN}GraphKind; //定义顶点数据类型 typedef char V ertexData; //定义邻接矩阵中元素值(即边信息)的数据类型 typedef int ArcNode; //定义图的邻接矩阵类型:一个顶点信息的一维数组,一个邻接矩阵、当前图中包含的顶点数、边数以及图类型(有向图、有向网、无向图、无向网) typedef struct { V ertexData vertex[MAX_VERTEX_NUM]; ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vertexnum,arcnum; GraphKind kind; } AdjMatrix;//图的邻接矩阵表示类型 int LocateV ertex(AdjMatrix *G,V ertexData v) //求顶点位置函数 { int j=-1,k; for(k=0;kvertexnum;k++) { if(G->vertex[k]==v) { return k; } } return j; } int CreateDN(AdjMatrix *G) //创建一个又向网 { int i,j,k,weight; V ertexData v1,v2; printf("输入图的顶点数和弧数,以逗号分隔\n"); //输入图的顶点数和弧数 scanf("%d,%d",&G->vertexnum,&G->arcnum); for(i=0;ivertexnum;i++) //初始化邻接矩阵(主对角线元素全为零,其余元素为无穷大) {

图的实现及遍历

数据结构【第六次】实验报告学院: 班级: 学号: 姓名:

实验六 (一)实验名称:图的实现及遍历 (二)实验目的: 1) 掌握有向图和无向图的概念; 2) 掌握邻接矩阵和邻接链表建立图的存储结构; 3) 掌握DFS及BFS对图的遍历操作和过程; 4) 了解图结构在人工智能、工程等领域的广泛应用。(三)实验要求: 1) 采用邻接矩阵作为图的存储结构,完成有向图和无向图的DFS和BFS操作; 2) 采用邻接链表作为图的存储结构,完成有向图和无向图的DFS和BFS操作。 (四)源代码: 1)邻接矩阵作为存储结构的程序 #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 typedef struct{ char vexs[MaxVertexNum]; int edges[MaxVertexNum][MaxVertexNum]; int n,e; }MGraph;

void CreatMGraph(MGraph *G) { int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); scanf("%c",&a); printf("Input Vertex string:"); for(i=0;in;i++) { scanf("%c",&a); G->vexs[i]=a; } for(i=0;in;i++) for(j=0;jn;j++) G->edges[i][j]=0; printf("Input edges,Creat Adjacency Matrix\n"); for(k=0;ke;k++) { scanf("%d%d",&i,&j); G->edges[i][j]=1; G->edges[j][i]=1; } } typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum]; //========DFS: void DFSM(MGraph *G,int i) { int j; printf("%c",G->vexs[i]); visited[i]=TRUE; for(j=0;jn;j++) if(G->edges[i][j]==1 && ! visited[j]) DFSM(G,j); } void DFS(MGraph *G) { int i; for(i=0;in;i++) visited[i]=FALSE; for(i=0;in;i++) if(!visited[i]) DFSM(G,i); } void BFS(MGraph *G,int k)

邻接矩阵创建有向网的实现

韩山师范学院 实验题目: 邻接矩阵创建有向网算法实现 班级:2015级软工班作者:黄俊聪 #include using namespace std; #define MaxInt 32767 //表示极大值,即∞ #define MVNum 100 //最大顶点数 #define OK 1 #define ERROR 0; typedef char VerTexType;//假设顶点的数据类型为字符型 typedefintArcType;//假设边的权值类型为整型 typedefint Status; typedefstruct { VerTexTypevexs[MVNum];//顶点表 ArcType arcs[MVNum][MVNum];//邻接矩阵 intvexnum,arcnum;//图的当前点数和边数 }AMGraph; Status LocateVex(AMGraphG,char v) {

for(i=0; i>G.vexnum>>G.arcnum;//输入总定点数,总边数 cout<<"次输入点的信息:"<>G.vexs[i]; for(int i=0;i>v1>>v2>>w;//输入一条边依附的顶点及权值 i=LocateVex(G,v1); j=LocateVex(G,v2);//确定v1和v2在G中的位置,即顶点数组的下表 G.arcs[i][j]=w;//边的权值置为w } return OK; } void PrintMatrix(AMGraph&G)//输出邻接矩阵 { inti,j; printf("邻接矩阵为:\n"); for(i=0;i

实验12 图的基本操作-邻接矩阵

浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十二图的基本操作—邻接矩阵存储结构 实验成绩指导老师(签名)日期 一.实验目的和要求 1、掌握图的存储结构:邻接矩阵。 2、学会对图的存储结构进行基本操作。 二.实验内容 1、图的邻接矩阵定义及实现:建立头文件AdjMatrix.h,在该文件中定义图的邻接矩阵存储结构,并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test5_1.cpp,编译并调试程序,直到正确运行。 2、选做:编写图的深度优先遍历函数与广度优先遍历函数,要求把这两个函数添加到头文件AdjMatrix.h中,并在主函数文件test5_1.cpp中添加相应语句进行测试。 3、填写实验报告,实验报告文件取名为report12.doc。 4、上传实验报告文件report12.doc及源程序文件test5_1.cpp、AdjMatrix.h 到Ftp服务器上自己的文件夹下。 三. 函数的功能说明及算法思路 (包括每个函数的功能说明,及一些重要函数的算法实现思路) 函数:void CreateGraph(MGraph &G, GraphKind kd) 功能:采用数组邻接矩阵表示法,构造图G 思路:按照输入值确定图的顶点数、弧数、类型,并按照类型初始化邻接矩阵,其中图的构造初值赋为0,网的构造初值赋为之前定义好的MaxValue值,再按照输入构造邻接矩阵。 函数:void PrintMGraph(MGraph &G) 功能:输出邻接矩阵 思路:根据已有矩阵信息(顶点数=行列数),控制格式进行输出 函数:void countdig(MGraph G,int comp) 功能:计算图的入度或出度

图的深度优先遍历和广度优先遍历

华北水利水电学院数据结构实验报告 20 10 ~20 11 学年第一学期2008级计算机专业 班级:107学号:200810702姓名:王文波 实验四图的应用 一、实验目的: 1.掌握图的存储结构及其构造方法 2.掌握图的两种遍历算法及其执行过程 二、实验内容: 以邻接矩阵或邻接表为存储结构,以用户指定的顶点为起始点,实现无向连通图的深度优先及广度优先搜索遍历,并输出遍历的结点序列。 提示:首先,根据用户输入的顶点总数和边数,构造无向图,然后以用户输入的顶点为起始点,进行深度优先和广度优先遍历,并输出遍历的结果。 三、实验要求: 1.各班学号为单号的同学采用邻接矩阵实现,学号为双号的同学采用邻接表实现。 2.C/ C++完成算法设计和程序设计并上机调试通过。 3.撰写实验报告,提供实验结果和数据。 4.写出算法设计小结和心得。 四、程序源代码: #include #define MaxVerNum 50 struct edgenode { int endver; int inform; edgenode* edgenext; }; struct vexnode { char vertex; edgenode* edgelink; }; struct Graph { vexnode adjlists[MaxVerNum]; int vexnum; int arcnum; }; //队列的定义及相关函数的实现 struct QueueNode

{ int nData; QueueNode* next; }; struct QueueList { QueueNode* front; QueueNode* rear; }; void EnQueue(QueueList* Q,int e) { QueueNode *q=new QueueNode; q->nData=e; q->next=NULL; if(Q==NULL) return; if(Q->rear==NULL) Q->front=Q->rear=q; else { Q->rear->next=q; Q->rear=Q->rear->next; } } void DeQueue(QueueList* Q,int* e) { if (Q==NULL) return; if (Q->front==Q->rear) { *e=Q->front->nData; Q->front=Q->rear=NULL; } else { *e=Q->front->nData; Q->front=Q->front->next; } } //创建图 void CreatAdjList(Graph* G) { int i,j,k; edgenode* p1; edgenode* p2;

采用邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操作

/* 采用邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操作 */ #include "stdio.h" #include "string.h" #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int Status; #define INFINITY INT_MAX /*最大值“无穷”*/ #define MAX_VERTEX_NUM 20 /*最大顶点个数*/ typedef int Boolean; typedef char VertexType[20]; typedef int VRType; /**************以下为队列的操作************/ /****队列的类型定义****/ typedef int QElemType; typedef struct QNode {QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; /****初始化队列****/ Status InitQueue(LinkQueue *Q) { (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if (!(*Q).front) exit(OVERFLOW); (*Q).front->next=NULL; return OK; } /****判断队列是否为空****/ Status QueueEmpty (LinkQueue Q) { if (Q.front==Q.rear) return TRUE; else

建立图的邻接矩阵或邻接表存储并在此基础知识上实现图的深度和广度优先遍历

#include "stdafx.h" #include "conio.h" #include "stdio.h" #include "stdlib.h" typedef enum {FALSE, TRUE} BOOLEAN; #define OVERFLOW -1 #define OK 1 #define ERROR 0 #define INFINITY INT_MAX /* 最大值∞ */ /* 根据图的权值类型,分别定义为最大整数或实数 */ #define MAX_VERTEX_NUM 20 /* 最大顶点数目 */ typedef enum {DG, DN, UDG,UDN} GraphKind ; /* {有向图,有向网,无向图,无向网} */ BOOLEAN Visited[MAX_VERTEX_NUM]; BOOLEAN visited[MAX_VERTEX_NUM]; #define VEX_NUM 20 #define MAXSIZE 50 typedef char Vextype; typedef int ElemType; typedef int Status; ////////////////////////////// 邻接矩阵结构定义typedef struct { Vextype vexs[VEX_NUM]; int adj[VEX_NUM][VEX_NUM]; /*邻接矩阵*/ int n,e; /*顶点数和边数*/ }Mgraph;

////////////////////////////// 邻接表结构定义 typedef struct node { /*边结点*/ int adjvex; /*邻接点域*/ struct node * nextarc; /*指向下一个边结点的指针域*/ } EdgeNode; typedef struct vnode { //顶点结构,2个域,结点信息和第一个邻接点Vextype vertex; EdgeNode *firstedge; }VertexNode; typedef struct { //图结构 VertexNode adjlist[MAXSIZE]; int n,e; } ALGraph; //// int FirstAdjVex(ALGraph G,int v) {//在图G中寻找第v个顶点的第一个邻接顶点 if(!G.adjlist[v].firstedge) return -1; else return(G.adjlist[v].firstedge->adjvex); } int NextAdjVex(ALGraph G,int v,int w) {//在图G中寻找第v个顶点的相对于w的下一个邻接顶点 EdgeNode *p; int vi; p=G.adjlist[v].firstedge; if(!p) return -1;

图的邻接矩阵结构上实现图的广度优先遍历

图的邻接矩阵结构上实现图的广度优先遍历: 广搜的实现相对而言比较难,它需要用到数据结构中另一个抽象:队列 [c-sharp]view plaincopy 1.void bfs(graph *g,int i){ 2.int j,k; 3. printf("%d点被访问/n",i);//i已经被访问 4. visited[i] = 1;//标记i边已经被访问 5. cirqueue *p = (cirqueue*)malloc(sizeof(cirqueue));//申请一个对队列 6. p->front = p->rear = p->count = 0;//表示队列为空 7.//以下三行代码使得i进入队列 8. p->q[p->rear] = i; 9. p->rear = (p->rear++)/maxnum; 10. p->count++; 11. 12.while(p->count!=0){//假如队列不空 13.//以下三行代码是去队列元素 14. j = p->q[p->front]; 15. p->front = (p->rear++)/maxnum; 16. p->count--; 17.//寻找序号为i顶点的邻接点,并做如下处理 18.for(k=0;kvNum;k++){ 19.if(g->e[j][k]!=0&&visited[k]==0){//假如j点与i点相连,并且j点还没 有被访问过 20. printf("%d点被访问/n",k);//i已经被访问 21. visited[k] = 1;//标记i边已经被访问 22. 23.//以下三行代码使得k进入队列 24. p->q[p->rear] = k; 25. p->rear = (p->rear++)/maxnum; 26. p->count++; 27. } 28. } 29. } 30.} 31. 32. 33.void BFS(graph *g){ 34.int i; 35.//首先把所有点都设置成没有访问过 36.for(i=0;ivNum;i++){

相关主题
相关文档 最新文档