作业帮编写算法：a 从键盘读入有向图的顶点和弧,创建有向图的邻接表存储结构 b 判断图的连通性
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/03 00:29:21
编写算法：a 从键盘读入有向图的顶点和弧,创建有向图的邻接表存储结构 b 判断图的连通性
编写算法：a 从键盘读入有向图的顶点和弧,创建有向图的邻接表存储结构 b 判断图的连通性
编写算法：a 从键盘读入有向图的顶点和弧,创建有向图的邻接表存储结构 b 判断图的连通性
#include "stdio.h"
#include "stdlib.h"
#define MaxVertexNum 100
typedef char VertexType;
typedef struct node
{
\x09int adjvex;
\x09struct node *next;
}EdgeNode;
typedef struct vnode
{
\x09VertexType vertex;
\x09EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
typedef struct
{
\x09AdjList adjlist;
\x09int n,e;
}ALGraph;
void CreatALGraph(ALGraph *G)
{
\x09int i,j,k;
\x09EdgeNode *s;
\x09scanf("%d%d",&G->n,&G->e);
\x09for(i = 0;i < G->n;i++)
\x09{
\x09\x09G->adjlist[i].vertex = getchar();
\x09\x09G->adjlist[i].firstedge = NULL;
\x09}
\x09for(k = 0;k < G->e;k++)
\x09{
\x09\x09scanf("%d%d",&i,&j);
\x09\x09s = (EdgeNode *)malloc(sizeof(EdgeNode));
\x09\x09s->adjvex = j;
\x09\x09s->next = G->adjlist[i].firstedge;
\x09\x09G->adjlist[i].firstedge = s;
\x09}
}
bool visited[MaxVertexNum];
void DFS(ALGraph *G,int i)
{
\x09EdgeNode *p = G->adjlist[i].firstedge;
\x09visited[i] = true;
\x09while(p)
\x09{
\x09\x09if(!visited[p->adjvex])
\x09\x09\x09DFS(G,p->adjvex);
\x09\x09p = p->next;
\x09}
}
bool IsConnected(ALGraph *G)
{
\x09int i,j;
\x09for(i = 0;i < G->n;i++)
\x09{
\x09\x09for(j = 0;j < G->n;j++)
\x09\x09\x09visited[j] = false;
\x09\x09DFS(G,i);
\x09\x09for(j = 0;j < G->n;j++)
\x09\x09\x09if(!visited[j])
\x09\x09\x09\x09return false;
\x09}
\x09return true;
}
int main()
{
\x09ALGraph G;
\x09CreatALGraph(&G);
\x09if(IsConnected(&G))
\x09\x09printf("连通\n");
\x09else
\x09\x09printf("不连通\n");
\x09system("pause");
}
//输入序列为"4 3abcd0 1 1 2 2 3",输出为"不连通"
//输入序列为"4 4abcd0 1 1 2 2 3 3 0",输出为"连通"