图的邻接表&深度优先搜索

图的邻接表&深度优先搜索

• 图的邻接表
• 深度优先搜索

代码

#include <stdio.h>
#include <stdlib.h>

#define MAX 30
#define TRUE 1
#define FALSE 0

int book[MAX] = {0,};

typedef struct edgenode{
    int adjvex;
    char info;
    struct edgenode *next;
}edgeNode;

typedef struct vexnode{
    char data;
    struct edgenode *link;
}adjlist[MAX];

typedef struct{
    adjlist vertices;
    int vexnum, arcnum;
}Graph ;

void GreateGraph(Graph &L){
    int vexnum,p;
    edgeNode *edgeNode_p,*temp;
    printf("请输入顶点个数:\n");
    scanf("%d%*c",&vexnum);
    L.vexnum = vexnum;
    L.arcnum = 0;
    for (int i = 0; i < vexnum; ++i) {
        L.vertices[i].link = NULL;
    }
    for (int i = 0; i < vexnum; ++i) {
        
        printf("请输入第%d个顶点的值:\n",i+1);
        scanf("%c%*c",&L.vertices[i].data);
        printf("请输入第%d个顶点的邻接点(-1代表结束):\n",i+1);
        scanf("%d%*c",&p);
        while (p>=0){
            if(p>vexnum||p==i+1){
                printf("%s，请重新输入(-1代表结束):\n",p==i+1?"邻接点不能是自身":"没有这个邻接点");
                scanf("%d%*c",&p);
                continue;
            }
            
            //使用头插法加入边表结点
            
            edgeNode_p = (edgeNode*)malloc(sizeof(edgeNode));
            edgeNode_p->adjvex = p-1;
            edgeNode_p->next = NULL;
            temp = L.vertices[i].link;
            edgeNode_p->next = temp;
            L.vertices[i].link = edgeNode_p;
            
//            edgeNode_p2 = (edgeNode*)malloc(sizeof(edgeNode));
//            edgeNode_p2->adjvex = i;
//            edgeNode_p2->next = NULL;
//            temp = L.vertices[p-1].link;
//            edgeNode_p2->next = temp;
//            L.vertices[p-1].link = edgeNode_p2;
            
            L.arcnum++;
            scanf("%d%*c",&p);
        }
    }
}

void DFS(Graph L,int point){
    book[point] = TRUE;
    edgenode *p = L.vertices[point].link;
    printf("%c     ",L.vertices[point].data);
    while (p) {
        if (book[p->adjvex]!=TRUE)
            DFS(L, p->adjvex);
        p = p->next;
    }
}

void DFS_Tra(Graph L){
    int nodenum = L.vexnum;
    int start;
    for (int i = 0; i<nodenum; i++) {//标记访问状态
        book[i] = FALSE;
    }
    printf("请输入搜索起始点:\n");
    scanf("%d",&start);
    while (start<1||start>nodenum) {
        printf("没有这个点，请重新输入:\n");
        scanf("%d",&start);
    }
    DFS(L, start-1);
}

int main(){
    Graph L;
    GreateGraph(L);
    DFS_Tra(L);
    return 0;
}

图用例

//v1即表示1，懒得再画图了

输入

请输入顶点个数:
8
请输入第1个顶点的值:
1
请输入第1个顶点的邻接点(-1代表结束):
2
3
-1
请输入第2个顶点的值:
2
请输入第2个顶点的邻接点(-1代表结束):
1
4
5
-1
请输入第3个顶点的值:
3
请输入第3个顶点的邻接点(-1代表结束):
1
6
7
-1
请输入第4个顶点的值:
4
请输入第4个顶点的邻接点(-1代表结束):
2
8
-1
请输入第5个顶点的值:
5
请输入第5个顶点的邻接点(-1代表结束):
2
8
-1
请输入第6个顶点的值:
6
请输入第6个顶点的邻接点(-1代表结束):
3
7
-1
请输入第7个顶点的值:
7
请输入第7个顶点的邻接点(-1代表结束):
3
6
-1
请输入第8个顶点的值:
8
请输入第8个顶点的邻接点(-1代表结束):
4
5
-1
请输入搜索起始点:
1

输出

1     3     7     6     2     5     8     4     Program ended with exit code: 0

//程序从右到左开始遍历，与参考答案不一样，但都正确.
参考答案遍历结果为:1→2→4→8→5→3→6→7