图的遍历c语言

图是一种常见的数据结构，其节点和边的关系可以表示复杂的问题和现实场景。在实际应用中，对图的遍历是一项关键任务，这篇文章将从多个角度分析图的遍历C语言实现的方法和技巧。

一、广度优先遍历

广度优先遍历是一种基于队列的遍历方法，其核心思想是从图的某一个节点出发，依次将其相邻的节点加入队列，再将队列中的节点依次出队并遍历。由于广度优先遍历遵循先进先出的原则，因此可以保证遍历到的节点与出队的顺序相同。C语言实现该方法的代码如下：

```c

void BFS(int s)

{

queue q;

q.push(s);

vis[s] = true;

while(!q.empty())

{

int u = q.front();

q.pop();

for(int i = head[u]; i != -1; i = e[i].next)

{

int v = e[i].to;

if(!vis[v])

{

q.push(v);

vis[v] = true;

}

}

}

}

```

其中，head数组表示节点u的第一条边，e数组表示第i条边从from节点到to节点，vis数组表示各节点是否被遍历过。

二、深度优先遍历

深度优先遍历是一种基于栈的遍历方法，其核心思想是从图的某一个节点出发，沿着一个子树一直往下遍历，直到遇到没有未被访问的子节点时，再往回退一步。由于深度优先遍历遵循后进先出的原则，因此可以保证每个节点的子节点在其父节点之前被遍历。C语言实现该方法的代码如下：

```c

void DFS(int u)

{

vis[u] = true;

for(int i = head[u]; i != -1; i = e[i].next)

{

int v = e[i].to;

if(!vis[v])

{

DFS(v);

}

}

}

```

其中，head数组和e数组的含义同广度优先遍历，vis数组表示各节点是否被遍历过。

三、最短路径算法

最短路径算法用于计算从一个节点到其他所有节点的最短距离。其中最经典的算法是Dijkstra算法和Floyd算法。Dijkstra算法是一种贪心算法，其核心思想是从起始节点出发，依次确定每个节点到起始节点的最短距离，并更新其他节点的最短距离。C语言实现Dijkstra算法的代码如下：

```c

void Dijkstra(int s)

{

priority_queue ,vector >,greater >> q;

q.push(make_pair(0,s));

dis[s] = 0;

while(!q.empty())

{

int u = q.top().second;

q.pop();

if(vis[u])

{

continue;

}

vis[u] = true;

for(int i = head[u]; i != -1; i = e[i].next)

{

int v = e[i].to;

int w = e[i].w;

if(dis[v] > dis[u] + w)

{

dis[v] = dis[u] + w;

q.push(make_pair(dis[v],v));

}

}

}

}

```

其中，priority_queue可以自动按照pair 的第一个元素排序，greater表示从小到大排序。

Floyd算法是一种动态规划算法，其核心思想是将每个节点的最短距离初始化为其相邻节点之间的距离，然后逐步扩展节点集合，更新任意两个节点之间的最短距离。C语言实现Floyd算法的代码如下：

```c

for(int k = 1; k <= n; k++)

{

for(int i = 1; i <= n; i++)

{

for(int j = 1; j <= n; j++)

{

if(dis[i][j] > dis[i][k] + dis[k][j])

{

dis[i][j] = dis[i][k] + dis[k][j];

}

}

}

}

```

其中，dis[i][j]表示从节点i到节点j的最短距离，n表示节点个数。

四、图的存储方式

在实际应用中，图通常以邻接表或邻接矩阵的形式进行存储。邻接表是一种以链表的形式存储每个节点的出边的方式，相比邻接矩阵可以更好地处理稀疏图。在邻接表存储方式下，每个节点都对应一个链表，存储其出边的信息。C语言实现邻接表存储方式代码如下：

```c

struct edge

{

int to,w,next;

}e[maxn];

int head[maxn]; // head[i]表示节点i的第一条出边

int cnt = 0; // cnt表示当前边数

void add(int u,int v,int w)

{

e[cnt].to = v;

e[cnt].w = w;

e[cnt].next = head[u];

head[u] = cnt++;

}

```

邻接矩阵是一种以矩阵的形式存储节点之间关系的方式，可以更好地处理稠密图。在邻接矩阵存储方式下，通常使用二维数组来表示节点之间的距离信息。C语言实现邻接矩阵存储方式代码如下：

```c

int dis[maxn][maxn]; // dis[i][j]表示从节点i到节点j的最短距离，初始化为inf（无穷大）

void init()

{

memset(dis,inf,sizeof(dis));

for(int i = 1; i <= n; i++)

{

dis[i][i] = 0;

}

}

void add(int u,int v,int w)

{

dis[u][v] = w;

}

```

其中，inf表示无穷大。

综上所述，图的遍历是一项重要的任务，C语言提供了广度优先遍历和深度优先遍历两种方法，以及Dijkstra算法和Floyd算法进行最短路径计算。在实际应用中，图通常以邻接表或邻接矩阵的形式进行存储。可以根据实际情况选择不同的方法和存储方式进行处理。