关于图的（邻接矩阵）创建 深度优先 广度优先

图的创建有两种方法，一种是邻接矩阵，一种是邻接表，邻接矩阵的相对比较好理解，它就是使用一个一维数组存放顶点信息，使用一个二维数组存放弧（边长）。而邻接表将它存放成了两个表的形式，一个叫做“边表”，一个叫做“表头节点表”。表头节点表中存放的就是各个节点的信息，而边表中存放的是与他临接的节点的序列号。
1：创建算法
也就是先用一个函数寻找这个节点在二维数组中的位置，然后返回，在这个新的函数中，先是各种初始化活动，如果有权值的话就设置权值，没有权值的话就采用“1”表示邻接，用”0“表示邻接不上。具体代码见下面例子。
2：深度优先,广度优先：
深度优先相当于从一条路一直走到无路可走。
广度优先相当于将每个节点的路都走过一遍，然后返回接着走。
具体算法见下面例子：

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

#define MAX 20
#define INFINITY  32768
#define ERROR 0
#define OK    1
typedef enum
{
    DG,DN,UDG,UDN
}GraphKind;

typedef char VetexData;
typedef struct ArcNode
{
    int adj;
    int info;
}ArcNode;

typedef struct
{
    VetexData vertex[MAX];//记录顶点的顶点数组
    ArcNode arcs[MAX][MAX];//记录邻接矩阵
    int vexnum,arcnum;//顶点数和弧数
    GraphKind kind;
}AdjMatrix;
typedef struct Node
{
    int data;
    struct Node *next;
}SeqNode;
typedef struct node
{
    SeqNode *front;
    SeqNode *rear;
}SeqQueue;
void InitQueue(SeqQueue *Q)
{
    Q->front=Q->rear=NULL;
}
int Isempty(SeqQueue *Q)
{
    if(Q->front==Q->rear)
        return OK;
    else
        return ERROR;
}
int EnterQueue(SeqQueue *Q,int x)
{
    SeqNode *NewNode;
    NewNode=(SeqNode *)malloc(sizeof(SeqNode));
    if(NewNode==NULL)
    {
        printf("内存分配失败!\n");
        return ERROR;
    }
    NewNode->data=x;
    NewNode->next=NULL;
    if(Q->rear==NULL)
        Q->front=Q->rear=NewNode;
    else
    {
        Q->rear->next=NewNode;
        Q->rear=NewNode;
    }
    return OK;
}
int DeleteQueue(SeqQueue *Q,int *x)
{
    SeqNode *p;
//    if(Q->front==Q->rear)
//        return ERROR;
    p=Q->front;
    Q->front=Q->front->next;
    if(Q->rear==p->next)
        Q->rear=Q->front;
    *x=p->data;
    free(p);
    return OK;
}
int LocateVetex(AdjMatrix *G,VetexData v)//寻找顶点位置
{
    int j=ERROR;
    int k;
    for(k=0;k<G->vexnum;k++)
        if(G->vertex[k]==v)
        {
            j=k;
            break;
        }
    return j;
}
void OutPut(AdjMatrix G)
{
    int i,j;
    for(i=0;i<G.vexnum;i++)
        printf("%c ",G.vertex[i]);
    printf("\n");
    for(i=0;i<G.vexnum;i++)
    {
        for(j=0;j<G.vexnum;j++)
            printf("%d  ",G.arcs[i][j].adj);
        printf("\n");
    }
}
int CreateDN(AdjMatrix *G)
{
    char ch;
    int i,j,k,weight;
    int m,n;
    VetexData v1,v2;
    printf("请输入图的顶点数目和弧数目:");
    scanf("%d %d",&G->vexnum,&G->arcnum);
    setbuf(stdin,NULL);
    printf("请输入顶点：");
    ch=getchar();
    i=0;
    while(i<G->vexnum)
    {
        G->vertex[i]=ch;
        i++;
        ch=getchar();
        fflush(stdin);
    }
    printf("顶点输入完毕，请输入邻接矩阵:\n");
    for(i=0;i<G->vexnum;i++)
        for(j=0;j<G->vexnum;j++)
            G->arcs[i][j].adj=INFINITY;
    OutPut(*G);
    m=0;
    n=0;
    for(k=0;k<G->arcnum;k++)
    {

        printf("请输入邻接矩阵:");
        fflush(stdin);
        scanf("%c%c%d",&v1,&v2,&weight);
        getchar();
        printf("%c %c %d\n",v1,v2,weight);
        m=LocateVetex(G,v1);
        n=LocateVetex(G,v2);
        printf("%d %d\n",m,n);
        G->arcs[m][n].adj=weight;
    }

    return OK;
}
//深度优先
int visited[MAX];
void DFS(AdjMatrix G,int v)
{
    int w;
    printf("%c ",G.vertex[v]);
    visited[v]=OK;
    for(w=0;w<G.vexnum;w++)
    {
        if(!visited[w]&&G.arcs[v][w].adj!=INFINITY)
            DFS(G,w);
    }
}
void DSF_Traverse(AdjMatrix G)
{
    int i;
    for(i=0;i<G.vexnum;i++)
        visited[i]=ERROR;
    for(i=0;i<G.vexnum;i++)
        if(!visited[i])
            DFS(G,i);
}

//广度优先
void BFS(AdjMatrix G,int v)
{
    int w,i;
    SeqQueue Q;
    InitQueue(&Q);
    printf("%c ",G.vertex[v]);
    visited[v]=OK;
    EnterQueue(&Q,v);
    while(Q.front!=NULL)
    {
        DeleteQueue(&Q,&w);
        for(i=0;i<G.vexnum;i++)
        {
            if(!visited[i]&&G.arcs[w][i].adj!=INFINITY)
            {
                printf("%c ",G.vertex[i]);
                visited[i]=OK;
                EnterQueue(&Q,i);
            }
        }
    }

}
int main()
{
    AdjMatrix G;
    int v;
    CreateDN(&G);
    OutPut(G);
    printf("深度优先遍历的结果:");
    DSF_Traverse(G);
    printf("\n");
    printf("广度优先遍历的结果：");
    for(v=0;v<G.vexnum;v++)
        BFS(G,v);
    printf("\n");

}