无向图（无权值）的邻接矩阵与邻接表储存方式及其DFS，BFS遍历

求下图中无向图的邻接矩阵与邻接表储存方式及其DFS，BFS遍历

---

一、 无向图（无权值）的邻接矩阵存储方式及其DFS，BFS遍历

邻接矩阵的储存表示：

广度优先遍历需要用到队列操作，因此还需要定义一下队列的存储结构

---

具体代码：

#include <stdio.h>

#define MaxVex     100            //最大顶点数
#define TRUE       1
#define FALSE   0

typedef char    VertexType;    //顶点类型
typedef int     EdgeType;    //权值类型
typedef int     Bool;

Bool  visited[MaxVex];

typedef struct {
    VertexType vexs[MaxVex];            //顶点数组
    EdgeType   arc[MaxVex][MaxVex];    //邻接矩阵
    int        numVertexes, numEdges;   //当前图中的结点数以及边数
}MGraph;


//广度优先遍历需要的循环队列
typedef struct {
    int    data[MaxVex];
    int    front, rear;
}Queue;


/****************************************/
//队列的相关操作

//初始化
void InitQueue(Queue *Q)
{
    Q->front = Q->rear = 0;
}

//入队
void EnQueue(Queue *Q, int e)
{
    if ((Q->rear+1)%MaxVex == Q->front)
        return ;

    Q->data[Q->rear] = e;
    Q->rear = (Q->rear+1)%MaxVex;
}

//判空
Bool QueueEmpty(Queue *Q)
{
    if (Q->front == Q->rear)
        return TRUE;
    else
        return FALSE;
}

//出队
void DeQueue(Queue *Q, int *e)
{
    if (Q->front == Q->rear)
        return ;

    *e = Q->data[Q->front];
    Q->front = (Q->front+1)%MaxVex;
}
/****************************************/


//建立图的邻接矩阵
void CreateMGraph(MGraph *G){
    int i, j, k;

    printf("输入顶点数和边数: ");
    scanf("%d%d", &G->numVertexes,&G->numEdges);

    printf("==============================\n");
    scanf("%c", &G->vexs[i]); /*关键，必须先要输入一次*/
    printf("输入各个顶点:\n");
    for (i=0; i< G->numVertexes; ++i){
        scanf("%c", &G->vexs[i]);
    }

    for (i=0; i<G->numVertexes; ++i){
        for (j=0; j<G->numVertexes; ++j)
            G->arc[i][j] = 0;
        fflush(stdin);
    }

    printf("==============================\n");
    printf("输入边(vi, vj)中的下标i和j: \n");
    for (k=0; k< G->numEdges; ++k){
        scanf("%d%d", &i,&j);
        G->arc[i][j] = 1;
        G->arc[j][i] = G->arc[i][j];
    }
}

/****************************************/
//图的深度优先遍历
void DFS(MGraph G, int i){
    int j;
    visited[i] = TRUE;
    printf("%c ", G.vexs[i]);

    for (j=0; j<G.numVertexes; ++j){
        if (G.arc[i][j]!=0 && !visited[j])
            DFS(G, j);
    }
}

void DFSTraverse(MGraph G){
    int i;
    for (i=0; i<G.numVertexes; ++i)
        visited[i] = FALSE;

    for (i=0; i<G.numVertexes; ++i){
        if (!visited[i])
            DFS(G, i);
    }

}


//图的广度优先遍历
void BFSTraverse(MGraph *G){
    int i, j;
    Queue Q;

    for (i=0; i< G->numVertexes; ++i)
        visited[i] = FALSE;
    InitQueue(&Q);

    for (i=0; i< G->numVertexes; ++i){
        if (!visited[i]){
            visited[i] = TRUE;
            printf("%c ", G->vexs[i]);
            EnQueue(&Q, i);

            while (!QueueEmpty(&Q)){
                DeQueue(&Q, &i);
                for (j=0; j< G->numVertexes; ++j){
                    if (!visited[j] && G->arc[i][j]!=0){
                        visited[j] = TRUE;
                        printf("%c ", G->vexs[j]);
                        EnQueue(&Q, j);
                    }
                }
            }
        }
    }
}
/****************************************/

//程序入口
int main(){
    MGraph G;

    CreateMGraph(&G);

    printf("\n图的深度优先遍历为: ");
    DFSTraverse(G);

    printf("\n图的广度优先遍历为: ");
    BFSTraverse(&G);

    printf("\n");

    return 0;
}

结果展示：

---

二、 无向图（无权值）的邻接表存储方式及其DFS，BFS遍历

---

具体代码：

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

#define MaxVertexNum 50 /*定义最大顶点数*/

typedef struct node {
    /*边表节点*/
    int adjVex;  /*邻接点域*/
    struct node* next; /*链域*/
}EdgeNode;

typedef struct vNode {
    char verTex; /*顶点域*/
    EdgeNode *firstEdge; /*边表头指针*/
}verTexNode;

typedef verTexNode AdjList[MaxVertexNum]; /*AdjList是邻接表类型*/


typedef struct {
    AdjList adjList; /*邻接表*/
    int n,e; /*顶点数和边数*/
}ALGraph;


/*建立图的邻接表*/
void CreatALGraph(ALGraph *G) {
    char a;
    int i,j,k;
    EdgeNode *s; /*定义边表节点*/
    printf("Input VertexNum(n) and EdgesNum(e):");
    scanf("%d,%d",&G->n,&G->e); /*输入顶点数和边数*/
    scanf("%c",&a); /*避免 G->adjList[0].verTex = '\n' */
    printf("Input Vertex string: ");
    for (i = 0; i < G->n; ++i) {
        scanf("%c",&a);
        G->adjList[i].verTex = a; /*读入顶点信息*/
        G->adjList[i].firstEdge = NULL; /*边表置空*/
    }
    printf("Input edges, Creat Adjacency List\n");
    for ( k = 0; k < G->e; ++k) {
        scanf("%d%d",&i,&j); /*读入边（Vi, Vj ） 的顶点对序号*/
        s = (EdgeNode *) malloc(sizeof(EdgeNode)); /*生成边表节点*/
        s->adjVex = j;
        s->next = G->adjList[i].firstEdge;
        G->adjList[i].firstEdge = s;
        s = (EdgeNode *)malloc(sizeof(EdgeNode));
        s->adjVex = i;
        s->next = G->adjList[j].firstEdge;
        G->adjList[j].firstEdge = s;
    }
}

/*定义标志向量，为全局变量*/
typedef enum {FALSE, TRUE} Boolean;
Boolean visited[MaxVertexNum];

/*DFS遍历算法*/
void DFSM(ALGraph *G, int i){
    EdgeNode *p;
    printf("%c",G->adjList[i].verTex);
    visited[i] = TRUE;
    p = G->adjList[i].firstEdge;
    while (p) {
        if (!visited[p->adjVex])
            DFSM(G, p->adjVex);
        p = p->next;
    }
}

void DFS(ALGraph *G){
    int i;
    for (i = 0; i < G->n; ++i) {
        visited[i] = FALSE;
    }
    for ( i = 0; i < G->n; ++i) {
        if (!visited[i]) {
            DFSM(G,i);
        }
    }
}

/*BFS 遍历算法*/
void BFS(ALGraph *G, int k){
    int i, f=0, r= 0;
    EdgeNode *p;
    int cQueue[MaxVertexNum]; /*定义FIFO队列*/
    for (i = 0; i < G->n; ++i) {
        visited[i] = FALSE;
    }

    for ( i = 0; i < G->n; ++i) {
        cQueue[i] = -1; /*初始化标志向量*/
    }
    printf("%c", G->adjList[k].verTex);
    visited[k] = TRUE;
    cQueue[r] = k;
    while (cQueue[f] != -1){
        i = cQueue[f];
        f++;
        p = G->adjList[i].firstEdge;
        while (p) {
            if (!visited[p->adjVex]){
                printf("%c", G->adjList[p->adjVex].verTex);
                visited[p->adjVex] = TRUE;
                r++;
                cQueue[r] = p->adjVex;
            }
            p = p->next;
        }
    }
}


void main() {
    ALGraph *G = (ALGraph *)malloc(sizeof(ALGraph));
    CreatALGraph(G);
    printf("Print Graph DFS:");
    DFS(G);
    printf("\n");
    printf("Print Graph BFS:");
    BFS(G,0);
}

---

结果展示：

---

总结：

1. 邻接矩阵是实现各种算法最简单的一种方式，其简单性主要来自数组读取元素的简洁性。但是其空间效率不高，适用于稠密图的存储。
2. 邻接链表表示法，提高了空间的利用率，读取以某一节点为起点的所有边是比较简单的。但是链表的先天劣势就是随机读取方面需要移动指针，这就造成了算法的执行速度会比使用数组要慢许多。当然我们可以通过封装方法以及重载运算符的方式实现数组的功能，但是这只是代码层面的模仿，效率上是不可弥补的。除此之外，当要获得以某一节点为终点的所有边时，使用邻接表就显得十分无力了，算法实现显得十分笨拙：通过遍历所有节点的边链表，以检查是否存在满足条件的边。这里也突出了邻接矩阵的优势：它的随机读取方面的优势。
3. DFS,BFS遍历代码并不难理解，断点调试，分析代码运行过程，很快就能够理解。推荐工具： JetBrains公司旗下的C语言开发工具，Clion