假设图G采用邻接表存储,设计一个算法,输出图G中从顶点u到v的所有简单路径.
来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/05/09 13:58:25
假设图G采用邻接表存储,设计一个算法,输出图G中从顶点u到v的所有简单路径.
#include "stdio.h"
#define MAX 5
typedef struct ArcNode
{
\x09/*单链表中的结点的类型*/
\x09int adjvex; /*该边指向的顶点在顺序表中的位置*/
\x09struct ArcNode *next; /*下一条边*/
}ArcNode;
typedef struct VNode
{
\x09/*顶点类型*/
\x09int data; /*顶点中的数据信息*/
\x09ArcNode *firstarc; /*指向单链表,即指向第一条边*/
}VNode;
int visited[5]={0,0,0,0,0};\x09//标记数组
//先创建顶点,再创建指向
CreatGraph(int n ,VNode G[] )
{
\x09int i,e;
\x09ArcNode *p ,*q;
\x09printf("Input the information of the vertex\n");
\x09for(i=0;iadjvex = e;
\x09\x09\x09if(G[i].firstarc == NULL)
\x09\x09\x09\x09G[i].firstarc = p; /*i结点的第一条边*/
\x09\x09\x09else
\x09\x09\x09\x09q->next = p; /*下一条边*/
\x09\x09\x09q = p;
\x09\x09\x09scanf("%d",&e);
\x09\x09}
\x09}
}
int FirstAdj(VNode G[],int v)
{
\x09if(G[v].firstarc != NULL)
\x09\x09return (G[v].firstarc)->adjvex;
\x09return -1;
}
int NextAdj(VNode G[],int v)
{
\x09ArcNode *p;
\x09
\x09p = G[v].firstarc;
\x09while( p!= NULL)
\x09{
\x09\x09if(visited[p->adjvex]) //如果访问过了就继续找下一个结点
\x09\x09\x09p = p->next;
\x09\x09else
\x09\x09\x09return p->adjvex;\x09//如果找到未访问过的就返回
\x09}
\x09return -1;
}
void DFS(VNode G[],int v)
{
\x09int w;
\x09
\x09printf("%d ",G[v].data); /*访问当前顶点,打印出该顶点中的数据信息*/
\x09visited[v] = 1; /*将顶点v对应的访问标记置1*/
\x09w = FirstAdj(G,v); /*找到顶点v的第一个邻接点,如果无邻接点,返回-1*/
\x09while(w != -1)
\x09{//退出递归条件有二:一是直到某节点无指向,二是该深度没有可以访问的顶点
\x09\x09if(visited[w] == 0) /*该顶点未被访问*/
\x09\x09\x09DFS(G,w); /*递归地进行深度优先搜索*/
\x09\x09w = NextAdj(G,v); /*找到顶点v的下一个邻接点,如果无邻接点,返回-1*/
\x09}
}
int main(void)
{
\x09int i = 0,n;
\x09VNode G[5];\x09//顶点容器
\x09
\x09printf("Input vertex:\n");
\x09scanf("%d",&n);
\x09CreatGraph(n,G);
\x09for (i;i
#define MAX 5
typedef struct ArcNode
{
\x09/*单链表中的结点的类型*/
\x09int adjvex; /*该边指向的顶点在顺序表中的位置*/
\x09struct ArcNode *next; /*下一条边*/
}ArcNode;
typedef struct VNode
{
\x09/*顶点类型*/
\x09int data; /*顶点中的数据信息*/
\x09ArcNode *firstarc; /*指向单链表,即指向第一条边*/
}VNode;
int visited[5]={0,0,0,0,0};\x09//标记数组
//先创建顶点,再创建指向
CreatGraph(int n ,VNode G[] )
{
\x09int i,e;
\x09ArcNode *p ,*q;
\x09printf("Input the information of the vertex\n");
\x09for(i=0;iadjvex = e;
\x09\x09\x09if(G[i].firstarc == NULL)
\x09\x09\x09\x09G[i].firstarc = p; /*i结点的第一条边*/
\x09\x09\x09else
\x09\x09\x09\x09q->next = p; /*下一条边*/
\x09\x09\x09q = p;
\x09\x09\x09scanf("%d",&e);
\x09\x09}
\x09}
}
int FirstAdj(VNode G[],int v)
{
\x09if(G[v].firstarc != NULL)
\x09\x09return (G[v].firstarc)->adjvex;
\x09return -1;
}
int NextAdj(VNode G[],int v)
{
\x09ArcNode *p;
\x09
\x09p = G[v].firstarc;
\x09while( p!= NULL)
\x09{
\x09\x09if(visited[p->adjvex]) //如果访问过了就继续找下一个结点
\x09\x09\x09p = p->next;
\x09\x09else
\x09\x09\x09return p->adjvex;\x09//如果找到未访问过的就返回
\x09}
\x09return -1;
}
void DFS(VNode G[],int v)
{
\x09int w;
\x09
\x09printf("%d ",G[v].data); /*访问当前顶点,打印出该顶点中的数据信息*/
\x09visited[v] = 1; /*将顶点v对应的访问标记置1*/
\x09w = FirstAdj(G,v); /*找到顶点v的第一个邻接点,如果无邻接点,返回-1*/
\x09while(w != -1)
\x09{//退出递归条件有二:一是直到某节点无指向,二是该深度没有可以访问的顶点
\x09\x09if(visited[w] == 0) /*该顶点未被访问*/
\x09\x09\x09DFS(G,w); /*递归地进行深度优先搜索*/
\x09\x09w = NextAdj(G,v); /*找到顶点v的下一个邻接点,如果无邻接点,返回-1*/
\x09}
}
int main(void)
{
\x09int i = 0,n;
\x09VNode G[5];\x09//顶点容器
\x09
\x09printf("Input vertex:\n");
\x09scanf("%d",&n);
\x09CreatGraph(n,G);
\x09for (i;i
假设图G采用邻接表存储,设计一个算法,输出图G中从顶点u到v的所有简单路径.
数据结构 :假设图G采用邻接表存储,试设计一个算法,求不带权无向连通图G中距离顶点v的最远的顶点?
设计一个算法,求无向图G(采用邻接表存储)的连通分量的个数
设计一个非递归算法判断以邻接方式存储的向图中是否存在由顶点Vi到Vj的路径.急.有哪位高手帮忙.
以邻接表作存储结构实现求从源点到其余各顶点的最短路径的Dijkstra算法
数据结构题.假定无向图G有6个结点和9条边,.(1) 画出G的邻接距阵和邻接表(2) 根据邻接表从顶点3
图改用邻接表表示,重写Dijkstra算法.输入任意带权有向图,输出每一对顶点间的最短路径及其权值.
编写算法,判断有向图中是否存在从顶点v出发的简单网络,若有则输出该回路.
1.设简单图G是一个Euler图.证明:G中每一个顶点u,均有w(G–u)≤(1/2)d(u).
(用Dijkstra算法)求出图中顶点1到其余各顶点的最短路径
设汁一个算法,建立无向图(n个顶点,e条边)的邻接表
数据结构作业 求最短路径 试设计一个算法求图中一个源点到其他个顶点的最短路径.