1图的概念

图的概念

2.图的存储结构

1.邻接矩阵

邻接矩阵

//邻接矩阵
#include <stdlib.h>
#include <stdio.h> 
#include <windwos.h>

typedef char VertexType;//定点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 100//最大顶点数
#define INFINITY 65535 //表示无穷大

typedef struct Graph
{
    VertexType vexs[MAXVEXS ];//顶点集合
    EdgeType arc[MAXVEXS][MAXVEXS];//邻接矩阵
    int numVexs,numEdge;//当前顶点数和边数
}Graph;

//创建无向图邻接矩阵 
void CreateGraph(Graph *G)
{
    int i,j,k,w;
    printf("请输入邻接图的顶点个数和边个数:\n");   
    scanf("%d,%d",&G->numVexs,&G->numEdge);
    printf("请输入顶点集合:\n");
    for(i=0;i<G->numVexs;i++)//初始化顶点
        scanf("%c",&G->vexs[i])；
    for(i=0;i<G->numVexs;i++)//初始化邻接矩阵
        for(j=0;j<G->numEdge;j++)
            G->arc[i][j]=INFINITY;//先初始化为无限大
    for(k=0;k<G->numEdge;k++)
    {
        printf("请输入(vi,vj)的i和j和权值w:");
        scanf("%d,%d,%d",&i,&j,&w);
        G->arc[i][j]=w;
        G->arc[j][i]=w;
    } 
}

2.邻接表

邻接表
带权值的邻接表

//邻接表 
#include <stdlib.h>
#include <stdio.h> 
#include <windwos.h>

typedef char VertexType;//顶点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 100//最大顶点数

typedef struct EdgeNode//边表节点 
{
    int adjvex;//邻接点下标
    EdgeType weight;//权值
    struct EdgeNode *next;//下一个邻接点 
}EdgeNode;

typedef struct VexNode//顶点表节点
{
    VertexType data;//顶点域 
    EdgeNode *firstedge;//边表头指针 
} VexNode,AdjList[MAXVEXS];

typedef struct
{
    AdjList list;
    int numVex,numEdge;//实际的顶点数和边数          
}GraphAdjList;

//创建无向图邻接表 
void CreateGraph(GraphAdjList *G)
{
    int i,j,k,w;
    EdgeNode *e;
    printf("请输入顶点数和边数:\n");
    scanf("%d,%d",&G->numVex,&G->numEdge);
    for(i=0;i<G->numVex;i++)//建立顶点表 
    {
        scanf("%c",G->list[i].data);//输入顶点的值
        G->list[i].firstedge = NULL;//先指向NULL 
    }
    
    for(k=0;k<G->numEdge;k++)
    {
        printf("请输入(vi,vj)下标i和j和权值w\n");
        scanf("%d,%d",&i,&j,&w);
        e =(EdgeNode*)malloc(sizeof(EdgeNode));
        e->weight=w;
        e->adjvex=j;
        e->next=G->list[i].firstedge;
        G->list[i].firstedge = e;
        
        //因为是无向图，i->j和j->i都是一样的
        e->weight=w;
        e->adjvex=i;
        e->next=G->list[j].firstedge;
        G->list[j].firstedge = e;        
            
    }
    
}

3.图的遍历

概念
1.深度优先遍历（Depth_First_Search）DFS
深度优先类似于树的前序遍历！！！
1.1邻接矩阵的深度优先算法

//邻接矩阵的深度优先算法 
#include <stdlib.h>
#include <stdio.h> 
#include <windwos.h>

typedef char VertexType;//定点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 20//最大顶点数
#define INFINITY 65535 //表示无穷大

//用于记录已经访问的节点,0->表示未访问过，1表示已访问 
int visited[MAXVEXS]; 

typedef struct Graph
{
    VertexType vexs[MAXVEXS ];//顶点集合
    EdgeType arc[MAXVEXS][MAXVEXS];//邻接矩阵
    int numVexs,numEdge;//当前顶点数和边数
}Graph;

//创建无向图邻接矩阵 
void CreateGraph(Graph *G)
{
    int i,j,k,w;
    printf("请输入邻接图的顶点个数和边个数:\n");   
    scanf("%d,%d",&G->numVexs,&G->numEdge);
    printf("请输入顶点集合:\n");
    for(i=0;i<G->numVexs;i++)
        scanf("%c",&G->vexs[i])
    for(i=0;i<G->numVexs;i++)
        for(j=0;j<G->numEdge;j++)
            G->arc[i][j]=INFINITY;//先初始化为无限大
    for(k=0;k<G->numEdge;k++)
    {
        printf("请输入(vi,vj)的i和j和权值w:");
        scanf("%d,%d,%d",&i,&j,&w);
        G->arc[i][j]=w;
        G->arc[j][i]=w;
    } 
}

//邻接矩阵深度优先递归算法 
void DFS(Graph *G,int i)
{
    int j;
    printf("%c ",G->vexs[i]);//访问顶点i
    visited[i]=1;//记录i节点访问过
    for(j=0;j<G->numVexs;j++)
    {
        if(G->arc[i][j] == 1&&visited[j]!=1)//下个连接点并且未访问过
        {
            DFS(G,j);
        } 
    }       
} 
//邻接矩阵的深度遍历操作
DFSTraverse(Graph *G)
{
    int i;
    for(i=0;i<G->numVexs;i++)
        visited[i]=0;//所有顶点默认未访问
    for(i=0;i<G->numVexs;i++)
    {
        if(visited[i]==0)
            DFS(G,i);
    } 
} 

1.2邻接表的深度优先算法

//邻接表 深度优先算法 
#include <stdlib.h>
#include <stdio.h> 
#include <windwos.h>

typedef char VertexType;//顶点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 100//最大顶点数

typedef struct EdgeNode//边表节点 
{
    int adjvex;//邻接点下标
    EdgeType weight;//权值
    struct EdgeNode *next;//下一个邻接点 
}EdgeNode;

typedef struct VexNode//顶点表节点
{
    VertexType data;//顶点域 
    EdgeNode *firstedge;//边表头指针 
} VexNode,AdjList[MAXVEXS];

typedef struct
{
    AdjList list;
    int numVex,numEdge;//实际的顶点数和边数          
}GraphAdjList;

int visited[MAXVEXS];//记录顶点的访问状态，0表示未访问，1表示已访问。 

//创建无向图邻接表 
void CreateGraph(GraphAdjList *G)
{
    int i,j,k,w;
    EdgeNode *e;
    printf("请输入顶点数和边数:\n");
    scanf("%d,%d",&G->numVex,&G->numEdge);
    for(i=0;i<G->numVex;i++)//建立顶点表 
    {
        scanf("%c",G->list[i].data);//输入顶点的值
        G->list[i].firstedge = NULL;//先指向NULL 
    }
    
    for(k=0;k<G->numEdge;k++)
    {
        printf("请输入(vi,vj)下标i和j和权值w\n");
        scanf("%d,%d",&i,&j,&w);
        e =(EdgeNode*)malloc(sizeof(EdgeNode));
        e->weight=w;
        e->adjvex=j;
        e->next=G->list[i].firstedge;
        G->list[i].firstedge = e;
        
        //因为是无向图，i->j和j->i都是一样的
        e->weight=w;
        e->adjvex=i;
        e->next=G->list[j].firstedge;
        G->list[j].firstedge = e;        
            
    }   
}
//深度优先递归算法 
void DFS(GraphAdjList G,int i)
{
    EdgeNode *p;
    printf("%c ",G->list[i].data);//访问顶点
    visited[i]; 
    p = G->list[i].firstedge;//指向下一个邻接点
    while(p!=NULL)
    {
        if(visited[p->adjvex]==0)//位访问
            DFS(G,p->adjvex);
        p=p->next;//指向下一个节点 
    }   
} 

//深度优先遍历
void DFSTraver(GraphAdjList *G) 
{
    int i;
    for(i=0;i<G->numVex;i++)
        visited[i]=0;//初始化所有顶点的状态为：未访问
    for(i=0;i<G->numVex;i++)
    {
        if(visited[i]==0)//如果未访问过
        {
            DFS(G,i);//深度优先访问 
        } 
    } 
}
 

1.3扩展:马踏棋盘算法(骑士周游问题)

马踏棋盘
马的走法

2.广度优先遍历（Breadth_First_Search）BFS
广度优先类似于树的层序遍历，用队列的形式去实现！！！

队列方式实现
1.1邻接矩阵的广度优先算法

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

typedef char VertexType;//顶点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 100//最大顶点数

int visited[MAXVEXS];//记录顶点的访问状态 

//邻接矩阵的广度优先算法
void BFSTraverse(Graph *G)
{
    int i,j;
    Queue Q;//队列
    InitQueue(&Q);//初始化队列 
    for(i=0;i<G->numVexs;i++)
        visited[i]=0;//初始化顶点的状态为0，表示未访问
    
    for(i=0;i<G->numVexs;i++)
    {
        if(visited[i]==0)//如果未被访问过
        {
            printf("%c ",G->vexs[i]);//访问顶点
            visited[i]=1;//记录该顶点被访问过
            EnQueue(&Q,i);//把顶点入队
            while(!IsEmpty(Q))//如果队列不为空 
            {
                DeQueue(&Q,&i);//出队
                for(j=0lj<G.numVexs;j++)
                {
                    //判断其他顶点与当前顶点存在边且未被访问过
                    if(G->arc[i][j]==1&&visited[j]==0)
                    {
                        printf("%c ",G->vexs[i]);//访问顶点
                        visited[i]=1;//记录该顶点被访问过
                        EnQueue(&Q,i);//把顶点入队   
                    } 
                } 
            }
        } 
    }
         
} 

1.2邻接表的广度优先算法

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

typedef char VertexType;//顶点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 100//最大顶点数

int visited[MAXVEXS];//记录顶点的访问状态 

//邻接表的广度优先算法
void BFSTraverse(GraphAdjList *G)
{
    int i,j;
    EdgeNode *p;
    Queue Q;//队列
    InitQueue(&Q);//初始化队列 
    for(i=0;i<G->numVexs;i++)
        visited[i]=0;//初始化顶点的状态为0，表示未访问
    
    for(i=0;i<G->numVexs;i++)
    {
        if(visited[i]==0)//如果未被访问过
        {
            printf("%c ",G->list[i].data);//访问顶点
            visited[i]=1;//记录该顶点被访问过
            EnQueue(&Q,i);//把顶点入队
            while(!IsEmpty(Q))//如果队列不为空 
            {
                DeQueue(&Q,&i);//出队
                p=G->list[i].firstedge;//指向头指针 
                while(p)//不为空 
                {
                    //判断当前顶点未被访问过
                    if(visited[p->adjvex]==0)
                    {
                        printf("%c ",G->vexs[i]);//访问顶点
                        visited[p->adjvex]=1;//记录该顶点被访问过
                        EnQueue(&Q,i);//把顶点入队   
                    } 
                    p=p->next;//指向下一个顶点 
                } 
            }
        } 
    }
         
}