设计并验证如下算法：带权图采用邻接表表示，实现无向图的广度优先搜索与有向图的深度优先搜索。

#define MAX_VERTEX_NUM 20 //图的邻接表存储表示
typedef struct ArcNode{
int adjvex； //该弧所指向的顶点的位置
struct ArcNode *nextarc； //指向下一条弧的指针
InfoType *info； //该弧相关信息的指针
}ArcNode；
typedef struct VNode {
VertexType data； //顶点信息
ArcNode *firstarc； //指向第一条依附该顶点弧的指针
}VNode，AdjList[MAX_VERTEX_NUM]
Typedef struct {
AdjList vertices；
int vexnum，arcnum； //图的当前顶点数和弧数
int kind； //图的种类标志
}ALGraph；

以上是题目以及题目给的提示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20	//图的邻接表存储表示
#define InfoType int
#define VertexType char

typedef struct ArcNode{
	int adjvex;	//该弧所指向的顶点的位置
	struct ArcNode *nextarc; 	//指向下一条弧的指针
	InfoType *info; 	//该弧相关信息的指针
}ArcNode;

typedef struct VNode {
	VertexType data;	//顶点信息
	ArcNode *firstarc; 	//指向第一条依附该顶点弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct {	
	AdjList vertices;
	int vexnum,arcnum; 	//图的当前顶点数和弧数
	int kind; 	//图的种类标志
}ALGraph;
int vs[20]={0,};

int LocateVex(ALGraph G,char v){//定位函数 
	for(int i=0;i<G.vexnum;i++){
		if(v==G.vertices[i].data)
			return i;
	} 
	printf("input error ! input again:\n");
	scanf("%c",&v);
	getchar();
	LocateVex(G,v);
	return -1;
}

void PrintUDG(ALGraph G){//输出邻接表 
    int i,j;
	for(i=0;i<G.vexnum;i++){
		printf("%d=%c:",i,G.vertices[i].data);
		ArcNode *p;
		p=G.vertices[i].firstarc;
		while(p!=NULL){
			printf("->%2d",p->adjvex);
			p=p->nextarc;
		}
		printf("\n");
	}
}

void create(ALGraph &p)
{
	printf("input the graph's kind (1 Undirected 2 Directed):\n");
	scanf("%d",&p.kind);
	printf("input the graph's vex and arc . \n");
	scanf("%d%d",&p.vexnum,&p.arcnum);
	getchar();
	for(int i=0;i<p.vexnum;i++){
		printf("vertex(%d): \n" ,i);
		scanf("%c",&p.vertices[i].data);
		getchar();
		p.vertices[i].firstarc=NULL;
	}
	char v1 ,v2;
	int k ,j;
	for(int i=0;i<p.arcnum;i++){
		printf("input two vertex :\n");
		v1 = getchar();
		getchar();
		v2 = getchar();
		getchar();
		j = LocateVex(p, v1);//定位 
		k = LocateVex(p, v2);
		ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode));//申请一个结点
		q->adjvex=k;//连接结点
		q->nextarc=p.vertices[j].firstarc;//连接结点
		p.vertices[j].firstarc=q;//连接结点
		if(p.kind==1){//如果是无向图 
			ArcNode *g = (ArcNode *)malloc(sizeof(ArcNode));//申请一个结点
			g->adjvex=j;//连接结点
			g->nextarc=p.vertices[k].firstarc;//连接结点
			p.vertices[k].firstarc=g;//连接结点
		}
	}
}

int visit[20]={0};
void DFS(AdjList G,int v){
	
	ArcNode *p;
	visit[v]=1;
	printf("%d ",v);
	p=G[v].firstarc;
	while(p!=NULL){
		if(visit[p->adjvex]==0){//若w=p->adjvex 顶点未访问，递归访问它
			DFS(G,p->adjvex);
			vs[p->adjvex]=2;
		}
		p=p->nextarc;//p指向顶点v的下一个邻接点
	}
}

void BFS(AdjList G,int v)
{
	ArcNode *p;
	int Qu[20],front,rear;//定义循环队列
	int visited[20]={0};//使用数组模拟队列
	int w;
	front=rear=0;//初始化队列
	printf("%d ",v);
	visited[v]=1;
	rear=(rear+1);
	Qu[rear]=v;//v进队
	while(front!=rear){
		front=(front+1);
		w=Qu[front];//出队并赋给w
		p=G[w].firstarc;//找与顶点w邻接的第一个顶点
		while(p){
			if(visited[p->adjvex]==0){//若当前顶点未被访问
				printf("%d ",p->adjvex);//访问邻接顶点
				visited[p->adjvex]=1;
				vs[p->adjvex]=2;
				rear=(rear+1);//该顶点进队
				Qu[rear]=p->adjvex;
			}
			p=p->nextarc;
		}
	}
}



程序运行说明：
1.先输入1或者2构造的图的类型。
2.然后输入顶点个数与弧的个数。
3.再依次输入顶点的名称例如：A B C
4.再输入两个顶点的名称，构造图。
5.最后输入一个起始的点的序号。
在这里插入图片描述
最后一个比如你想输入起始点为A点，那你就输入1.
有向图与无向图一样输入
有什么问题欢迎留言，看到就会回答。。