1. 图的邻接矩阵结构体定义
#include<stdio.h>
# define Maxvertices 20
typedef struct Seqlist {
int length; //存储顶点总数
char* data; // 等价于 char data[Maxvertices]
}Seqlist;
typedef struct {
Seqlist vertices; //存放顶点的顺序表(顶点值和顶点的总数)
int edge[Maxvertices][Maxvertices];//存放边的领接矩阵
int numOfEdges;//存放边的条数
}AdjMGraph;
2. 连通图的bfs
//连通图的bfs
int bfs(AdjMGraph g) {
int queue[Maxvertices]; //存贮顶点的序号 ，也就是 顶点在数组中的下标。
int front = 0;
int rear = 0;
int visit[Maxvertices] = { 0 };
//设把0号顶点作为启动点。
rear = (rear + 1) % Maxvertices;
queue[rear] = 0;
visit[0] = 1;
while (rear != front)
{
front = (front + 1) % Maxvertices;
int number = queue[front];
printf("%c,", g.vertices.data[number]);
for (int i = 0; i < g.vertices.length; i++)
{
if (g.edge[number][i] == 1 && visit[i] == 0)
{
rear = (rear + 1) % Maxvertices;
queue[rear] = i;
visit[i] = 1;
}
}
}
return 0;
}
3. 连通图的dfs
int dfs(AdjMGraph g) {
int arr[Maxvertices];
int top = -1;
int visit[Maxvertices] = { 0 };
visit[0] = 1;
top++;
arr[top] = 0;
printf("%c", g.vertices.data[0]);
while (top != -1)
{
int number = arr[top];
top--;
for (int i = 0; i < g.vertices.length; i++)
{
if (g.edge[number][i] == 1 && visit[i] == 0)
{
top++;
arr[top] = number;
top++;
arr[top] = i;
printf("%c", g.vertices.data[i]);
visit[i] = 1;
break;
}
}
}
return 0;
}
4. 一般图的bfs
//一般图的bfs
int bfs2(AdjMGraph g) {
int queue[Maxvertices];
int front = 0;
int rear = 0;
int visit[Maxvertices] = { 0 };
for (int i = 0; i < g.vertices.length; i++)
{
if (visit[i] == 0)
{
rear = (rear + 1) % Maxvertices;
queue[rear] = i;
visit[i] = 1;
while (rear != front) {
front = (front + 1) % Maxvertices;
int number = queue[front];
printf("%c", g.vertices.data[number]);
for (int i = 0; i < g.vertices.length; i++)
{
if (g.edge[number][i] == 1 && visit[i] == 0)
{
rear = (rear + 1) % Maxvertices;
queue[rear] = i;
visit[i] = 1;
}
}
}
}
}
return 0;
}
5. 一般图的dfs
//一般图的dfs
int dfs2(AdjMGraph g) {
int arr[Maxvertices];
int top = -1;
int visit[Maxvertices] = { 0 };
for (int i = 0; i < g.vertices.length; i++)
{
if (visit[i] == 0)
{
top++;
arr[top] = i;
visit[i] = 1;
printf("%c", g.vertices.data[i]);
while (top != -1) {
int number = arr[top];
top--;
for (int j = 0; j < g.vertices.length; j++)
{
if (g.edge[number][j] == 1 && visit[j] == 0)
{
top++;
arr[top] = number;
top++;
arr[top] = j;
visit[j] = 1;
printf("%c", g.vertices.data[j]);
break;
}
}
}
}
}
}
6. 1 判断图上任意点v点到达j点是否有路径可达
以v点作为启动点，通过深度遍历或者宽度遍历 如果遇到了k说明有可达的路径，否则没有
////
int v_j_lu_jing_dfs(AdjMGraph g, char v, char k) {
int res = -1;
int arr[Maxvertices];
int top = -1;
int visit[Maxvertices] = { 0 };
//遍历 顶点数组，找到v点在数组中的下表，以加入栈中，作为启动点
int index_v = -1;
for (int i = 0; i < g.vertices.length; i++)
{
if (g.vertices.data[i] == v)
{
index_v = i;
break;
}
}
if (index_v == -1)
{
return -1;
}
top++;
arr[top] = index_v;
visit[index_v] = 1;
while (top != -1)
{
int number = arr[top];
top--;
for (int i = 0; i < g.vertices.length; i++)
{
if (g.edge[number][i] == 1 && visit[i] == 0)
{
top++;
arr[top] = number;
top++;
arr[top] = i;
visit[i] = 1;
if (g.vertices.data[i] == k)
{
return 1;
}
}
}
}
return res;
}
int v_j_lu_jing_bfs(AdjMGraph g, char v, char k) {
int res = -1;
int queue[Maxvertices];
int front = 0;
int rear = 0;
int visit[Maxvertices] = { 0 };
int index_v = -1;
for (int i = 0; i < g.vertices.length; i++)
{
if (g.vertices.data[i] == v)
{
index_v = i;
break;
}
}
if (index_v == -1)
{
return -1;
}
rear = (rear + 1) % Maxvertices;
queue[rear] = index_v;
visit[index_v] = 1;
while (rear != front)
{
front = (front + 1) % Maxvertices;
int number = queue[front];
if (g.vertices.data[number] == k)
{
return 1;
}
for (int i = 0; i < g.vertices.length; i++)
{
if (g.edge[number][i] == 1 && visit[i] == 0)
{
rear = (rear + 1) % Maxvertices;
queue[rear] = i;
visit[i] = 1;
}
}
}
return res;
}
6.2 是否存在一个从v点到j点路径长度为k的路径
int v_j_lu_jing_changdu_k_bfs(AdjMGraph g, char v, char j, int k) {
int res = 1;//保存最后要返回的结果 ，是否从在长度为k的路径，从v到j
int queue[Maxvertices];
int front = 0;
int rear = 0;
int visit[Maxvertices] = { 0 };
//定义一个数组，用来存贮每个节点所在的层号。用顶点的序号作为存贮在数组的索引。通过顶点的序号，来取出顶点的层号
int level_number[Maxvertices] = { 0 };
int index_v = -1; //保存v点的下标 也就是v点的序号。
for (int i = 0; i < g.vertices.length; i++)
{
if (g.vertices.data[i] == v)
{
index_v = i;
break;
}
}
if (index_v == -1)
{
return -1;
}
rear = (rear + 1) % Maxvertices;
queue[rear] = index_v;
visit[index_v] = 1;
//设置启动顶点所在的层为第1层
level_number[index_v] = 1;
while (rear != front)
{
front = (front + 1) % Maxvertices;
int number = queue[front];
int cur_level_number = level_number[number];
if (g.vertices.data[number] == j && k == cur_level_number - 1)
{
return 1;
}
for (int i = 0; i < g.vertices.length; i++)
{
if (g.edge[number][i] == 1 && visit[i] == 0)
{
rear = (rear + 1) % Maxvertices;
queue[rear] = i;
visit[i] = 1;
level_number[i] = cur_level_number + 1;
}
}
}
}
6.3 问无向图是不是一个连通图
实际上是问 极大连通分量是不是1，如果是的话就是连通图，如果不是就不是
6.4求无向图的连图分量个数
int lian_tong_fen_liang_ge_shu_bfs(AdjMGraph g) {
int count = 0;
int queue[Maxvertices];
int front = 0;
int rear = 0;
int visit[Maxvertices] = { 0 };
for (int i = 0; i < g.vertices.length; i++)
{
if (visit[i] == 0)
{
count++;
rear = (rear + 1) % Maxvertices;
queue[rear] = i;
visit[i] = 1;
while (rear != front)
{
front = (front + 1) % Maxvertices;
int number = queue[front];
for (int i = 0; i < g.vertices.length; i++)
{
if (g.edge[number][i] == 1 && visit[i] == 0)
{
rear = (rear + 1) % Maxvertices;
queue[rear] = i;
visit[i] = 1;
}
}
}
}
}
return count;
}
6.5 求无向图的连同分量，并打印各个连同分量的顶点。
int liang_tong_fen_liang_ge_shu_dayin_ding_dian_bfs(AdjMGraph g) {
int count = 0;
int queue[Maxvertices];
int front = 0;
int rear = 0;
int visit[Maxvertices] = { 0 };
for (int i = 0; i < g.vertices.length; i++)
{
if (visit[i] == 0)
{
count++;
printf("第%d个连通分量:", count);
rear = (rear + 1) % Maxvertices;
queue[rear] = i;
visit[i] = 1;
while (rear != front)
{
front = (front + 1) % Maxvertices;
int number = queue[front];
printf("%c", g.vertices.data[number]);
for (int i = 0; i < g.vertices.length; i++)
{
if (g.edge[number][i] == 1 && visit[i] == 0)
{
rear = (rear + 1) % Maxvertices;
queue[rear] = i;
visit[i] = 1;
}
}
}
}
}
return count;
}
6.6 求距离顶点v最远的顶点
以v点做启动点 进行宽度遍历，最后退出的点就是 距离v最远的点
char ju_v_zui_yuan_ju_li(AdjMGraph g, char v) {
char res;
int queue[Maxvertices];
int front = 0;
int rear = 0;
int visit[Maxvertices] = { 0 };
int index_v = -1;
for (int i = 0; i < g.vertices.length; i++)
{
if (g.vertices.data[i] == v)
{
index_v = i;
break;
}
}
if (index_v == -1)
{
return -1;
}
rear = (rear + 1) % Maxvertices;
queue[rear] = index_v;
visit[index_v] = 1;
while (rear != front)
{
front = (front + 1) % Maxvertices;
int number = queue[front];
res = g.vertices.data[number];
for (int i = 0; i < g.vertices.length; i++)
{
if (g.edge[number][i] == 1 && visit[i] == 0)
{
rear = (rear + 1) % Maxvertices;
queue[rear] = i;
visit[i] = 1;
}
}
}
return res;
}
6.7判断一个图是否存在环
标签：int,visit,number,邻接矩阵,Maxvertices,front,rear From： https://www.cnblogs.com/lwh2017/p/16993104.html利用深度遍历 某个节点在未退站之前 ，又通过其他顶点的相邻顶点找到了该顶点