MENU

记一次邻接表DFS

• April 20, 2020 • Read: 69 • 编程问题

邻接表递归的深度优先搜索,拿着书瞎折腾几小时,终于会了,emmmmm
休息休息,记录下代码,2333

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
typedef struct node{
    int dest;           //储存箭头所指的顶点信息
    struct node* next;
} edge;
typedef struct{
    char data;
    int source;      //储存顶点在 顶点数组 中的下标
    edge* adj;
} adjlheight;
typedef struct{
    adjlheight a[5];   //顶点数组
    int numOfVert;
    int numOfEdge;
} adjlgraph;
adjlgraph* adjInit(){ //创建并初始化邻接表
    adjlgraph* G=(adjlgraph*)malloc(sizeof(adjlgraph));
    G->numOfEdge=0;
    G->numOfVert=0;
    for(int i=0;i<5;i++){
        G->a[i].source=i;
        G->a[i].adj=NULL;
    }
    return G;
}
void InsertVertex(adjlgraph* G,int i,char vertex){
    if(i>-1 && i<5){
        G->a[i].data=vertex;
        G->numOfVert++;
    } else printf("顶点位置无效\n");
}
void InsertEdge(adjlgraph* G,int v1,int v2){
    edge* p;
    if(v1<0 || v1>=G->numOfVert ||v2<0 || v2>=G->numOfVert)
        printf("不存在相关顶点\n");
    else {
        p=(edge*)malloc(sizeof(edge));
        p->dest=v2;
        p->next=G->a[v1].adj;
        G->a[v1].adj=p;
        G->numOfEdge++;
    }
}
void GreateGraph(adjlgraph* G){
    char vertex;
    printf("请输入5个顶点数据: \n");
    for(int i=0;i<5;i++){
        scanf("%c",&vertex);
        getchar();
        InsertVertex(G,i,vertex);
    }
    int v1,v2,numOfvertex;
    printf("请输入边个数: \n");
    scanf("%d",&numOfvertex);
    if(numOfvertex<1) return;
    printf("请输入边数据: \n");
    for(int i=0;i<numOfvertex;i++) {
        scanf("%d%d",&v1,&v2);
        InsertEdge(G,v1,v2);
    }
}
int GetFirstVex(adjlgraph* G,int v){
    edge* p;
    if(v<0 || v>=G->numOfVert){
        printf("参数越界\n");
        return -1;
    }
    else {
        p=G->a[v].adj;
        if(p!=NULL) return p->dest;
        else return -1;
    }
}
int GetNextVex(adjlgraph* G,int v1,const int v2){
    edge* p;
    p=G->a[v1].adj;
    while(p!=NULL){
        if(p->dest!=v2)
            p=p->next;
        else break;
    }
    p=p->next;
    if(p!=NULL) return p->dest;
    else return -1;
}
void DepthFSearch(adjlgraph* G,int v,int visited[]){
    visited[v]=1;
    printf("%c ",G->a[v].data);
    int w=GetFirstVex(G,v);

    while(w!=-1){
        if(visited[w]==0)
            DepthFSearch(G,w,visited);
        w=GetNextVex(G,v,w);
    }
}
int main()  {
    adjlgraph* G=adjInit();
    GreateGraph(G);
    int visited[5]={0};   //记录访问状态
    DepthFSearch(G,0,visited);
    return 0;
}
Archives QR Code Tip
QR Code for this page
Tipping QR Code