2022-07-01 10:55

# C语言图的连通性求解

###### 问题遇到的现象和发生背景

【问题描述】：如下图所示，分别采用基于深度优先边历和广度优先边历算法判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。 注意，算法中涉及的图的基本操作必须在此存储结构上实现。

###### 问题相关代码，请勿粘贴截图

``````#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 1
typedef struct Node
{
int index;
struct Node* next;
}node;

{
int data;
node* first;

void visit(headnode G[], int v,int end,int*status)
{
if (G[v].data == end)
*status = 1;
}

static int visited[6];
void DFS(headnode G[],int v,int end,int*status)
{
visited[v] = 1;
visit(G, v, end,status);
node* p = G[v].first;
while (p != NULL)
{
if (visited[p->index] == 0&&G[v].data != p->index + 1)
DFS(G, v, end, status);
p = p->next;
}
}

{
int start, end, * status = 0;
scanf("%d %d", &start, &end);
DFS(G, start, end, status);
}

int main()
{
char str[100] = "1/1/3\n2/4\n3/5/4\n4/1\n5/3\n6/6";
node* node1, * node2, * node3, * node4, * node5, * node6, * node7, * node8;
node1 = (node*)malloc(sizeof(node));
node1->index = 1;
node2 = (node*)malloc(sizeof(node));
node2->index = 3;
node1->next = node2;
node2->next = NULL;
G[0].first = node1;
node3 = (node*)malloc(sizeof(node));
node3->index = 4;
G[1].first = node3;
node3->next = NULL;
node4 = (node*)malloc(sizeof(node));
node4->index = 5;
node5 = (node*)malloc(sizeof(node));
node5->index = 4;
node4->next = node5;
node5->next = NULL;
G[2].first = node4;
node6 = (node*)malloc(sizeof(node));
node6->index = 1;
node6->next = NULL;
G[3].first = node6;
node7 = (node*)malloc(sizeof(node));
node7->index = 3;
node7->next = NULL;
G[4].first = node7;
node8 = (node*)malloc(sizeof(node));
node8->index = 5;
node8->next = NULL;
G[5].first = node8;
G[0].data = 1;
G[1].data = 2;
G[2].data = 3;
G[3].data = 4;
G[4].data = 5;
G[5].data = 6;
search(G);
return 0;
}

``````