编写算法:a 从键盘读入有向图的顶点和弧,创建有向图的邻接表存储结构 b 判断图的连通性
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:综合作业 时间:2024/07/18 16:11:55
编写算法: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",输出为"连通"
#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",输出为"连通"
设计一个非递归算法判断以邻接方式存储的向图中是否存在由顶点Vi到Vj的路径.急.有哪位高手帮忙.
数据结构 :假设图G采用邻接表存储,试设计一个算法,求不带权无向连通图G中距离顶点v的最远的顶点?
数据结构题.假定无向图G有6个结点和9条边,.(1) 画出G的邻接距阵和邻接表(2) 根据邻接表从顶点3
编写算法,判断有向图中是否存在从顶点v出发的简单网络,若有则输出该回路.
设计一个算法,求无向图G(采用邻接表存储)的连通分量的个数
在拓扑排序中,对有向图的存储,为什么要把邻接矩阵转化为邻接表
设汁一个算法,建立无向图(n个顶点,e条边)的邻接表
假设图G采用邻接表存储,设计一个算法,输出图G中从顶点u到v的所有简单路径.
在线急求熟悉图的两种常用的存储结构,邻接矩阵和邻接表.
编写算法,判断图中顶点A和顶点B之间是否有边
以邻接表作存储结构实现求从源点到其余各顶点的最短路径的Dijkstra算法
具体实现要求:1.通过键盘输入图的顶点和边信息,分别构造一个无向图的邻接矩阵和一个有向图的邻接表.2.分别对建立好的两个