图的表示和深度优先搜索
时间: 2023-07-23 15:11:44 浏览: 48
图可以用两种方式来表示:邻接矩阵和邻接表。
邻接矩阵是一个二维数组,其中每个元素表示两个顶点之间是否有边。对于一张有n个节点的图,其邻接矩阵是一个n×n的矩阵。如果顶点i和顶点j之间有边,则邻接矩阵中第i行第j列的元素为1;否则为0。如果该图是带权图,那么邻接矩阵中的元素可以表示边的权值。
邻接表则是用链表来表示每个顶点的邻居节点。对于每个顶点i,邻接表中有一个以i为头节点的链表,链表中存储该节点的所有邻居节点。如果该图是带权图,那么链表节点可以存储边的权值。
深度优先搜索是一种用于遍历图或树的算法,它从起点开始,沿着一条路径尽可能深地访问节点,直到无法继续为止,然后回溯到最近的未访问节点,并继续访问。重复这个过程,直到所有节点都被访问。深度优先搜索通常用递归或者栈来实现。
下面是深度优先搜索的伪代码:
```
DFS(G, v):
visited[v] = true // 标记v已经被访问
for each neighbor w of v: // 访问v的所有邻居节点
if w is not visited:
DFS(G, w) // 递归访问w
```
其中G表示图,v表示起点。
深度优先搜索可以用来判断图是否连通,寻找图的割点,检测图中是否有环等问题。
相关问题
用c语言写出图的表示和深度优先搜索
图的表示:
在C语言中,可以使用邻接矩阵或邻接表来表示图。
邻接矩阵表示法:
```c
#define MAXVEX 100 // 最大顶点数
typedef int EdgeType; // 边的权值类型
typedef struct {
int vexs[MAXVEX]; // 存放顶点信息
EdgeType arc[MAXVEX][MAXVEX]; // 存放边的权值
int numVertexes, numEdges; // 图的顶点数和边数
} MGraph;
```
邻接表表示法:
```c
#define MAXVEX 100 // 最大顶点数
typedef int EdgeType; // 边的权值类型
typedef struct EdgeNode { // 边表结点
int adjvex; // 邻接点域,存储该顶点对应的下标
EdgeType weight; // 边的权值
struct EdgeNode *next; // 链域,指向下一个邻接点
} EdgeNode;
typedef struct VertexNode { // 顶点表结点
int data; // 顶点域,存储顶点信息
EdgeNode *first; // 边表头指针
} VertexNode, AdjList[MAXVEX];
typedef struct {
AdjList adjList; // 邻接表
int numVertexes, numEdges; // 图的顶点数和边数
} GraphAdjList;
```
深度优先搜索:
深度优先搜索(DFS)是一种用于遍历或搜索树或图的算法。从一个根节点开始,它首先遍历根节点的所有子节点,然后遍历每个子节点的所有子节点,依此类推,直到遍历完整棵树或图。
深度优先搜索可以用递归或栈来实现。
以邻接表为例,递归实现深度优先搜索:
```c
#define MAXVEX 100 // 最大顶点数
typedef int EdgeType; // 边的权值类型
typedef struct EdgeNode { // 边表结点
int adjvex; // 邻接点域,存储该顶点对应的下标
EdgeType weight; // 边的权值
struct EdgeNode *next; // 链域,指向下一个邻接点
} EdgeNode;
typedef struct VertexNode { // 顶点表结点
int data; // 顶点域,存储顶点信息
EdgeNode *first; // 边表头指针
} VertexNode, AdjList[MAXVEX];
typedef struct {
AdjList adjList; // 邻接表
int numVertexes, numEdges; // 图的顶点数和边数
} GraphAdjList;
int visited[MAXVEX]; // 访问标记数组
void DFS(GraphAdjList G, int i) {
visited[i] = 1; // 标记该顶点已访问
printf("%d ", G.adjList[i].data); // 打印顶点值
EdgeNode *p = G.adjList[i].first; // 指向第一个邻接点
while (p != NULL) {
if (!visited[p->adjvex]) { // 如果邻接点未被访问,则递归访问它
DFS(G, p->adjvex);
}
p = p->next; // 访问下一个邻接点
}
}
void DFSTraverse(GraphAdjList G) {
int i;
for (i = 0; i < G.numVertexes; i++) {
visited[i] = 0; // 初始化标记数组
}
for (i = 0; i < G.numVertexes; i++) {
if (!visited[i]) { // 如果该顶点未被访问,则对它进行深度优先搜索
DFS(G, i);
}
}
}
```
邻接矩阵表示图的深度优先搜索原理
邻接矩阵是一种常用的表示图的方式,它把图中的每个节点与其他节点的相邻关系用一个矩阵来表示。在深度优先搜索中,我们从图中某个节点出发,依次遍历它的每一个未被访问过的相邻节点,直到遍历到无法继续遍历的节点为止。
具体实现时,我们可以使用一个数组来记录每个节点是否被访问过,然后从起始节点开始,递归地访问它的每个未被访问过的相邻节点,标记为已访问,直到遍历完所有可达节点为止。
在基于邻接矩阵表示的图上进行深度优先搜索的时间复杂度为O(V^2),其中V表示节点数,因为需要遍历每个节点,并查找它的相邻节点。