图的遍历:深度优先搜索(邻接矩阵存放)
发布网友
发布时间：2022-05-13 18:25
我来回答
共3个回答
热心网友
时间：2023-10-20 12:43
程序如下，编译环境vs2005和dev-c++，将图中顶点数和边线数组改为实际值。
/* 图的深度优先遍历 */
#include <stdlib.h>
#include <stdio.h>
struct node /* 图顶点结构定义 */
{
int vertex; /* 顶点数据信息 */
struct node *nextnode; /* 指下一顶点的指标 */
};
typedef struct node *graph; /* 图形的结构新型态 */
struct node head[9]; /* 图形顶点数组 */
int visited[9]; /* 遍历标记数组 */
/*根据已有的信息建立邻接表*/
void creategraph(int node[20][2],int num)/*num指的是图的边数*/
{
graph newnode; /*指向新节点的指针定义*/
graph ptr;
int from; /* 边的起点 */
int to; /* 边的终点 */
int i;
for ( i = 0; i < num; i++ ) /* 读取边线信息，插入邻接表*/
{
from = node[i][0]; /* 边线的起点 */
to = node[i][1]; /* 边线的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 建立顶点内容 */
newnode->nextnode = NULL; /* 设定指标初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入节点 */
}
}
/* 图的深度优先搜寻法 */
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* 记录已遍历过 */
printf("vertex[%d]\n",current); /* 输出遍历顶点值 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr->vertex); /* 递回遍历呼叫 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
int main()
{
graph ptr; /* 边线数组 */
int node[20][2] = { {1, 2}, {2, 1},
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} };
int i;
for ( i = 1; i <= 8; i++ ) /* 顶点数组初始化 */
{
head[i].vertex = i; /* 设定顶点值 */
head[i].nextnode = NULL; /* 指针为空 */
visited[i] = 0; /* 设定遍历初始标志 */
}
creategraph(node,20); /* 建立邻接表 */
printf("Content of the gragh's ADlist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf("vertex%d ->",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 印出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}
printf("\nThe end of the dfs are:\n");
dfs(1); /* 打印输出遍历过程 */
printf("\n"); /* 换行 */
system("pause");
return 0;
}
热心网友
时间：2023-10-20 12:43
程序如下，编译环境vs2005和dev-c++，将图中顶点数和边线数组改为实际值。
/*
图的深度优先遍历
*/
#include
<stdlib.h>
#include
<stdio.h>
struct
node
/*
图顶点结构定义
*/
{
int
vertex;
/*
顶点数据信息
*/
struct
node
*nextnode;
/*
指下一顶点的指标
*/
};
typedef
struct
node
*graph;
/*
图形的结构新型态
*/
struct
node
head[9];
/*
图形顶点数组
*/
int
visited[9];
/*
遍历标记数组
*/
/*根据已有的信息建立邻接表*/
void
creategraph(int
node[20][2],int
num)/*num指的是图的边数*/
{
graph
newnode;
/*指向新节点的指针定义*/
graph
ptr;
int
from;
/*
边的起点
*/
int
to;
/*
边的终点
*/
int
i;
for
(
i
=
0;
i
<
num;
i++
)
/*
读取边线信息，插入邻接表*/
{
from
=
node[i][0];
/*
边线的起点
*/
to
=
node[i][1];
/*
边线的终点
*/
/*
建立新顶点
*/
newnode
=
(
graph
)
malloc(sizeof(struct
node));
newnode->vertex
=
to;
/*
建立顶点内容
*/
newnode->nextnode
=
NULL;
/*
设定指标初值
*/
ptr
=
&(head[from]);
/*
顶点位置
*/
while
(
ptr->nextnode
!=
NULL
)
/*
遍历至链表尾
*/
ptr
=
ptr->nextnode;
/*
下一个顶点
*/
ptr->nextnode
=
newnode;
/*
插入节点
*/
}
}
/*
图的深度优先搜寻法
*/
void
dfs(int
current)
{
graph
ptr;
visited[current]
=
1;
/*
记录已遍历过
*/
printf("vertex[%d]\n",current);
/*
输出遍历顶点值
*/
ptr
=
head[current].nextnode;
/*
顶点位置
*/
while
(
ptr
!=
NULL
)
/*
遍历至链表尾
*/
{
if
(
visited[ptr->vertex]
==
0
)
/*
如过没遍历过
*/
dfs(ptr->vertex);
/*
递回遍历呼叫
*/
ptr
=
ptr->nextnode;
/*
下一个顶点
*/
}
}
int
main()
{
graph
ptr;
/*
边线数组
*/
int
node[20][2]
=
{
{1,
2},
{2,
1},
{1,
3},
{3,
1},
{1,
4},
{4,
1},
{2,
5},
{5,
2},
{2,
6},
{6,
2},
{3,
7},
{7,
3},
{4,
7},
{4,
4},
{5,
8},
{8,
5},
{6,
7},
{7,
6},
{7,
8},
{8,
7}
};
int
i;
for
(
i
=
1;
i
<=
8;
i++
)
/*
顶点数组初始化
*/
{
head[i].vertex
=
i;
/*
设定顶点值
*/
head[i].nextnode
=
NULL;
/*
指针为空
*/
visited[i]
=
0;
/*
设定遍历初始标志
*/
}
creategraph(node,20);
/*
建立邻接表
*/
printf("Content
of
the
gragh's
ADlist
is:\n");
for
(
i
=
1;
i
<=
8;
i++
)
{
printf("vertex%d
->",head[i].vertex);
/*
顶点值
*/
ptr
=
head[i].nextnode;
/*
顶点位置
*/
while
(
ptr
!=
NULL
)
/*
遍历至链表尾
*/
{
printf("
%d
",ptr->vertex);
/*
印出顶点内容
*/
ptr
=
ptr->nextnode;
/*
下一个顶点
*/
}
printf("\n");
/*
换行
*/
}
printf("\nThe
end
of
the
dfs
are:\n");
dfs(1);
/*
打印输出遍历过程
*/
printf("\n");
/*
换行
*/
system("pause");
return
0;
}
热心网友
时间：2023-10-20 12:44
程序如下，编译环境vs2005和dev-c++，将图中顶点数和边线数组改为实际值。
/*
图的深度优先遍历
*/
#include
#include
struct
node
/*
图顶点结构定义
*/
{
int
vertex;
/*
顶点数据信息
*/
struct
node
*nextnode;
/*
指下一顶点的指标
*/
};
typedef
struct
node
*graph;
/*
图形的结构新型态
*/
struct
node
head[9];
/*
图形顶点数组
*/
int
visited[9];
/*
遍历标记数组
*/
/*根据已有的信息建立邻接表*/
void
creategraph(int
node[20][2],int
num)/*num指的是图的边数*/
{
graph
newnode;
/*指向新节点的指针定义*/
graph
ptr;
int
from;
/*
边的起点
*/
int
to;
/*
边的终点
*/
int
i;
for
(
i
=
0;
i
<
num;
i++
)
/*
读取边线信息，插入邻接表*/
{
from
=
node[i][0];
/*
边线的起点
*/
to
=
node[i][1];
/*
边线的终点
*/
/*
建立新顶点
*/
newnode
=
(
graph
)
malloc(sizeof(struct
node));
newnode->vertex
=
to;
/*
建立顶点内容
*/
newnode->nextnode
=
NULL;
/*
设定指标初值
*/
ptr
=
&(head[from]);
/*
顶点位置
*/
while
(
ptr->nextnode
!=
NULL
)
/*
遍历至链表尾
*/
ptr
=
ptr->nextnode;
/*
下一个顶点
*/
ptr->nextnode
=
newnode;
/*
插入节点
*/
}
}
/*
图的深度优先搜寻法
*/
void
dfs(int
current)
{
graph
ptr;
visited[current]
=
1;
/*
记录已遍历过
*/
printf("vertex[%d]\n",current);
/*
输出遍历顶点值
*/
ptr
=
head[current].nextnode;
/*
顶点位置
*/
while
(
ptr
!=
NULL
)
/*
遍历至链表尾
*/
{
if
(
visited[ptr->vertex]
==
0
)
/*
如过没遍历过
*/
dfs(ptr->vertex);
/*
递回遍历呼叫
*/
ptr
=
ptr->nextnode;
/*
下一个顶点
*/
}
}
int
main()
{
graph
ptr;
/*
边线数组
*/
int
node[20][2]
=
{
{1,
2},
{2,
1},
{1,
3},
{3,
1},
{1,
4},
{4,
1},
{2,
5},
{5,
2},
{2,
6},
{6,
2},
{3,
7},
{7,
3},
{4,
7},
{4,
4},
{5,
8},
{8,
5},
{6,
7},
{7,
6},
{7,
8},
{8,
7}
};
int
i;
for
(
i
=
1;
i
<=
8;
i++
)
/*
顶点数组初始化
*/
{
head[i].vertex
=
i;
/*
设定顶点值
*/
head[i].nextnode
=
NULL;
/*
指针为空
*/
visited[i]
=
0;
/*
设定遍历初始标志
*/
}
creategraph(node,20);
/*
建立邻接表
*/
printf("Content
of
the
gragh's
ADlist
is:\n");
for
(
i
=
1;
i
<=
8;
i++
)
{
printf("vertex%d
->",head[i].vertex);
/*
顶点值
*/
ptr
=
head[i].nextnode;
/*
顶点位置
*/
while
(
ptr
!=
NULL
)
/*
遍历至链表尾
*/
{
printf("
%d
",ptr->vertex);
/*
印出顶点内容
*/
ptr
=
ptr->nextnode;
/*
下一个顶点
*/
}
printf("\n");
/*
换行
*/
}
printf("\nThe
end
of
the
dfs
are:\n");
dfs(1);
/*
打印输出遍历过程
*/
printf("\n");
/*
换行
*/
system("pause");
return
0;
}
图的遍历:深度优先搜索(邻接矩阵存放)
程序如下，编译环境vs2005和dev-c++，将图中顶点数和边线数组改为实际值。/* 图的深度优先遍历 */ include <stdlib.h> include <stdio.h> struct node /* 图顶点结构定义 */ { int vertex; /* 顶点数据信息 */ struct node *nextnode; /* 指下一顶点的指标 */ };type...
图的深度优先搜索的时间复杂度
因为在邻接矩阵上遍历，一般至少需要将矩阵中元素一半给过一下，由于矩阵元素个数为n^2，因此时间复杂度就是O(n^2)至于在邻接表上遍历时，过程与这个类似，但是邻接表中只是存储了边结点(e条边，无向图也只是2e个结点)，加上表头结点为n（也就是顶点个数），因此时间复杂度为O(n+e)另外，在邻...
求一个C语言编程,图的遍历,深度优先和广度优先搜索的程序。要浅显易懂...
define MAX_VEX 20 //最大顶点个数 define QUEUE_SIZE (MAX_VEX+1) //队列长度 using namespace std;bool *visited; //访问标志数组 //图的邻接矩阵存储结构 typedef struct{ char *vexs; //顶点向量 int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧...
...即邻接矩阵存储)的无向图进行深度优先遍历, 时间复杂度为...
【答案】：A图的邻接矩阵是指用一个矩阵来表示图中顶点之间的关系。对有 n 个结点的图，其邻接矩阵是一个n阶方阵。对于无向图来说，其邻接矩阵如下图所示当采用深度优先进行遍历的时候，查找所有邻接点所需要的时间是O(n^2) 。
试以邻接矩阵为存储结构,写出连通图的深度优先搜索算法。
/* MGraph.cc: 图的邻接矩阵存储表示和实现 */ /* 包含图类型Graph定义；创建图；深度优先遍历；广度优先遍历 */ /* 用到引用型参数，在TC下无法通过编译，VC等C++编译器可通过 */ include <stdio.h> include <string.h> include <limits.h> //含INT_MAX define VType char //顶点...
典型数据结构-图,图的存储、基本操作和遍历
图的基本操作涉及对图中顶点和边的操作，这些操作是理解图结构和应用的基础。图的存储方式多种多样，常见的有邻接矩阵和邻接表，它们各有优缺点，适应不同场景下的查询和操作效率需求。图的遍历是通过从特定顶点出发，系统地访问其他顶点，确保每个顶点只被访问一次的过程。深度优先搜索（DFS）和广度优先...
在用邻接表表示图时,对图进行深度优先搜索遍历的算法的时间复杂度为...
e的边或弧的数量。设有n个点，e条边 邻接矩阵：矩阵包含n＾2个元素，在算法中共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O（n＾2）。邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为O（n+e）顺便，对于广度优先算法的时间复杂度，也是这样。
邻接表是如何实现图的邻接表存储方法的呢?
用邻接表表示图进行深度优先遍历时，通常采用栈来实现算法。邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头...
从邻接矩阵怎么看出深度优先遍历结果
先由邻接矩阵把图画出来呀。深度优先遍历使用递归，对于一个结点，递归访问他没有访问过的相邻节点。就像走迷宫一样，已知走到无路可走，然后回溯，找下一个路口。广度优先遍历使用队列，当一个节点出队的时候，把他的相邻未访问节点入队。就像重度近视的人眼镜掉了找眼镜，会先找自己最近的一圈，然后...
如何根据带权邻接矩阵推出深度优先遍历
深度优先遍历，先访问第一行不为0的点为1，让后转至1行，找到第二个不为0 的点，3，转至3所在的行，同理找到4，再找到2 。2行中的3与前面重复，无其他不为0的点，剩下的点选5，再找到5行中不为0的点6。深度优先遍历的特点是遍历与这个点相邻的点，了解了邻接表的特点后就会觉得简单了。
