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

如果你的题目与我完全一样，就不要一个字都不修改地照抄我的代码。

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；

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

#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.
有向图与无向图一样输入
有什么问题欢迎留言，看到就会回答。。