编辑代码

#include <stdio.h>
#include "windows.h"

#define MaxVertex 6     // 规定矩阵最大可存多少个结点

typedef char C;

// 存边节点
typedef struct Node {
    int edge;
    struct Node *next;
} *node;

// 存节点头节点
typedef struct Head {
    C element;
    struct Node *next;
} *head;

// 图
typedef struct matrixGraph {
    int vertexCount, edgeCount;     //存放 结点总数与边总数
    struct Head vertex[MaxVertex];
} *Graph;

// create一个新的图
Graph create() {
    Graph graph = malloc(sizeof(struct matrixGraph));
    graph->vertexCount = graph->edgeCount = 0;
    return graph;
}

// 添加结点
void addVertex(Graph graph, C element) {
    if (graph->vertexCount != MaxVertex) {
        graph->vertex[graph->vertexCount].element = element;
        graph->vertex[graph->vertexCount++].next = NULL;
    }
}

//添加边，往邻接表添加
void addEdge(Graph graph, int a, int b) {
    node tmp = graph->vertex[a].next;   //取结点下一个
    node E = malloc(sizeof(struct Node));  // 创建新的存边节点
    E->edge = b;
    E->next = NULL;
    // 如果结点下一个为NULL ，则直接添加在后面
    while (tmp) {
        // 如果 边已经存在则直接返回，(可以释放内存E)不过我懒的写
        if (tmp->edge == b) return;
        // 如果下个为NULL ， 则直接添加
        if (!tmp->next) {
            tmp->next = E;
            graph->edgeCount++;
            return;
        }
        tmp = tmp->next;
    }
    // 直接添加
    graph->vertex[a].next = E;
    graph->edgeCount++;
}

typedef int E;

struct LNode {
    E element;
    struct LNode *Next;
};

typedef struct LNode *Node;

struct Queue {
    Node front, rear;
};

typedef struct Queue *LQueue;

BOOL initQueue(LQueue queue) {
    queue->front = queue->rear = malloc(sizeof(struct LNode));
    if (queue->front == NULL) return 0;
    return 1;
}

// 链表队push方法
BOOL pushQueue(LQueue queue, E element) {
    Node NewNode = malloc(sizeof(struct LNode));    //  申请Node空间
    if (NewNode == NULL) return 0;  //空间不足返回Null
    NewNode->element = element;
    queue->rear->Next = NewNode;
    queue->rear = NewNode; //rear加指向NewNode
    return 1;
}

// 判断链表队是否为空
BOOL isEmpty(LQueue queue) {
    return queue->rear == queue->front;
}

E popQueue(LQueue queue) {
    if (isEmpty(queue)) return -1; //判断队是否空，队空则返回-1
    queue->front = queue->front->Next;
    return queue->front->element;
}

// 打印邻接矩表
void f(Graph graph) {
    for (int i = 0; i < graph->vertexCount; ++i) {
        printf("%d | %c", i, graph->vertex[i].element);
        node tmp = graph->vertex[i].next;
        while (tmp) {
            printf("-> %d", tmp->edge);
            tmp = tmp->next;
        }
        printf("\n");
    }
}
 BOOL dfs(Graph graph, int startVertex, int targetVertex, int *visited) {
//    printf("%c ->",graph->vertex[startVertex].element);
    visited[startVertex] = 1;
    if (startVertex == targetVertex) return 1;
    node node1 = graph->vertex[startVertex].next;
    while (node1) {
        if (!visited[node1->edge])
            if (dfs(graph, node1->edge, targetVertex, visited))
                return 1;
        node1 = node1->next;
    }
     return 0;
}

BOOL bfs(Graph graph,  int startVertex, int targetVertex, int *visited, LQueue queue){
    pushQueue(queue,startVertex);
    visited[startVertex] = 1;
    while (!isEmpty(queue)){
        int next = popQueue(queue);
        printf("%c ->",graph->vertex[next].element);
        node node1 = graph->vertex[next].next;
        while (node1){
            if (targetVertex == node1->edge) return 1;
            if (!visited[node1->edge]){
                pushQueue(queue,node1->edge);
                visited[node1->edge] = 1;
            }
            node1 = node1->next;
        }
    }
    return 0;
}

int main() {
    Graph graph = create();

    for (int i = 'A'; i <= 'F'; i++) {
        addVertex(graph, (char) i);
    }

    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 4, 5);

//    f(graph);
    int v[graph->vertexCount];
    for (int i = 0; i < graph->vertexCount; ++i) {
        v[i] = 0;
    }

//    printf("%d",dfs(graph,0,5,v));
    struct Queue queue;
    initQueue(&queue);
    printf("\n%d",bfs(graph,0,5,v,&queue));
}