@TOC

图

这几周忙着国旗班训练，写博客估计也暂时慢下来，目前我就看什么就学什么吧。
最近想把书上的数据结构基本功能先实现了，再慢慢学一些算法，目前在看图，这部分不是很熟练，我就将我认为比较好理解的大佬的文章链接分享在这了 图的基本知识.，希望对大家学习图有帮助。

题目

第一行输入有向图的顶点数n和边数m，第二行输入顶点，分m行输入有向图边的信息，eg 1 2 表示点1到点2的一条弧，最后一行输入带判别的顶点vi vj
存在路径输出yes，否则输出no

代码

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

#define MAX 200

typedef struct EgdeNode
{
    int endvex; //相邻顶点字段
    int weight;//边的权
    struct EdgeNode *nextedge;//链字段
}EdgeList;//边表

typedef struct {
int vertex;//顶点信息
EdgeList *edgelist;//边表头指针
}VexNode;//顶点表

typedef struct {
VexNode vexs[MAX];
int vexNum,edgeNum;//图的顶点和边个数

}GraphList;

void CreatGraphList(GraphList *G,int n,int m)
{
    G->vexNum=n;
    G->edgeNum=m;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&G->vexs[i].vertex);//创建顶点表
        G->vexs[i].edgelist=NULL;
    }
    int v1,v2;
    for(int j=0;j<m;j++)
    {
        scanf("%d %d",&v1,&v2);//创建边表
        EdgeList *g=(EdgeList*)malloc(sizeof(EdgeList));
        g->endvex=v2;
        g->nextedge=G->vexs[v1].edgelist;//头插法
        G->vexs[v1].edgelist=g;

    }
}


int DFS(GraphList *G,int v1,int v2)//和树的先，中，后序遍历很像
{
    int visited[MAX]={0};
    visited[v1]=1;
    EdgeList *g=G->vexs[v1].edgelist;
    while(g)
    {
        if(g->endvex==v2)
        {
            return 1;
        }
        if(!(visited[g->endvex])&&DFS(G,g->endvex,v2))
        {
            return 1;
            g=g->nextedge;
        }
    }
    return 0;
}

int main()
{
    int m,n;
    scanf("%d %d",&m,&n);
    GraphList *G;
    G=(GraphList*)malloc(sizeof(GraphList));
    CreatGraphList(G,n,m);
    int v1,v2;
    scanf("%d %d",&v1,&v2);
    if(DFS(G,v1,v2)){
        printf("yes\n");
    }
    else{
        printf("no\n");
    }
    return 0;

}

结果：

若题目为深度和广度搜素并输出数据（利用矩阵，其实用邻接表一样可以转化为邻接矩阵），代码入下：
输入n个顶点，
输入n-1个边，
输出dfs和bfs结果。
（这里写的时候，创建矩阵的函数必须要用指针引地址，不能直接引入，不然无法修改其中矩阵的值（好像用结构体里创建的数组初始全为0））

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

typedef struct map
{
    int num;
    int Map[100][100];
} map;

typedef struct queue
{
    int front ;
    int  near ;
    int elem[100];
} queue;
int visit[100] = {0};
void createmap(map *p,int n)
{
    int u,v;
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= n;j++)
            p->Map[i][j] = 1000;
    for(int i = 1; i <= n;i++)
        p->Map[i][i] = 0;
        for (int i = 1; i < n; i++)
        {
            scanf("%d %d", &u, &v);
            p->Map[u][v] = 1;
        }
}

void dfsmap(map p,int n,int m)
{


    visit[m] = 1;
    printf("%d ", m);
    for (int i = 1; i <= n;i++)
    {
        if(visit[i]==0&&p.Map[m][i]==1)
            dfsmap(p, n, i);
    }
}

void initqueue(queue *Q)
{
    Q->front = -1;
    Q->near = -1;
}
void putin(queue *Q,int n)
{
    Q->near++;
    Q->elem[Q->near] = n;
}

int output(queue *Q)
{
    Q->front++;
    return Q->elem[Q->front];
}

int Isempty(queue *Q)
{
    return (Q->front == Q->near);
}

void bfsmap(map p,int i)
{
    int k;
    queue Q;
    initqueue(&Q);
    visit[1] = 1;
    putin(&Q, 1);

    while(!Isempty(&Q))
    {
        k = output(&Q);
        visit[k] = 1;
        printf("%d ", k);
        for (int j = 1; j <= i;j++)
            {
                if(visit[j]==0&&p.Map[k][j]==1)
                    putin(&Q, j);
            }
    }

}

int main()
{
    queue Q;
    map p;
    int i;
    scanf("%d", &i);
    createmap(&p, i);
    printf("dfs：");
    dfsmap(p, i,1);
    // for (int n = 1; n <= i;n++)
    //         {for (int m = 1; m <= i;m++)
    //             printf("%d ", p.Map[n][m]);
    //             printf("\n");}
    //printf("   bfs：");
    //bfsmap(p, i);

    return 0;
}