图相关代码

图相关代码

1.邻接矩阵存储结构定义

#define MaxVertexNum 100                   //顶点数目的最大值
typedef char VertexType;                   //顶点的数据类型
typedef int EdgeType;                      //带权图中边上权值的数据类型
typedef struct{
    char Vex[MaxVertexNum];                //顶点表
    int Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵，边表
    int vexnum,arcnum;                     //图的当前顶点数和弧数
}MGraph;

2.邻接表存储结构定义

#define MaxVertexNum 100                   //顶点数目的最大值
typedef struct ArcNode{                    //边表结点
    int adjvex;                            //邻接顶点
    struct ArcNode *nextarc;                  //指向下一条边
    //InfoType info;                       //网的边权值
}ArcNode;//邻接表的边类型
typedef struct VNode{                      //顶点表结点
    char data;                             //顶点信息
    ArcNode *firstarc;                        //指向第一条邻接边的指针
}VNode;//邻接表的顶点类型
typedef struct{
    VNode vexset[MaxSize];   //顶点集，每个顶点都有指向第一条边的指针，所以不用定义边集
    int vexnum,arcnum;                     //顶点数和边数
}ALGraph;                                  //ALGraph是以邻接表存储的图类型

3.广度优先搜索（BFS）

bool visited[MAX_VERTEX_NUM];        //标记访问数组
void BFSTraverse(Graph G){           //对图G进行广度优先遍历
    for(i=0;i<G.vexnum;++i){
        visited[i] = FALSE;          //访问标记数组初始化
    }
    InitQueue(Q);                    //初始化辅助队列Q
    for(i=0;i<G.vexnum;==i){         //从0号顶点开始遍历
        if(!visited[i]){             //对每个连通分量调用一次BFS
            BFS(G,i);                //vi从未被访问过，从vi开始BFS
        }
    }
}
void BFS(Graph G,int v){             //从定点v出发，广度优先遍历图G
    visit(v);                        //访问初始顶点v
    visited[v] = TRUE;               //对v做已访问标记
    Enqueue(Q,v);                    //顶点v入队列Q
    while(!IsEmpty(Q)){
        Dequeue(Q,v);                //顶点v出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
                                     //检测v所有邻接点
            if(!visited[w]){         //w为v的尚未访问的邻接结点
                visit(w);            //访问顶点w
                visited[w] = TRUE;   //对w做已访问标记
                Enqueue(Q,w);        //顶点w入队列
            }//if
        }
    }//while
}

4.BFS算法求解单元最短路径

void BFS_MIN_Distance(Graph G,int u){
    int d[G.vexnum];
    //d[i]表示从u到i的最短路径
    for(int i=0;i<G.vexnum;i++){
        d[i] = 1000000;              //初始化路径长度
    }
    visited[u] = TRUE;
    d[u] = 0;
    EnQueue(Q,u);
    while(!IsEmpty(Q)){              //BFS算法主过程
        Dequeue(Q,u);                //对头元素u出队
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
                                     //检测u所有邻接点
            if(!visited[w]){         //w为u的尚未访问的邻接结点
                visit(w);            //访问顶点w
                visited[w] = TRUE;   //对w做已访问标记
                d[w] = d[u] + 1;     //路径长度加1
                Enqueue(Q,w);        //顶点w入队列
            }//if
        }
    }//while
}

5.深度优先搜索（DFS）递归

bool visited[MAX_VERTEX_NUM];        //标记访问数组
void DFSTraverse(Graph G){           //对图G进行广度优先遍历
    for(v=0;v<G.vexnum;++v){
        visited[v] = FALSE;          //访问标记数组初始化
    }
    for(v=0;v<G.vexnum;++v){         //从0号顶点开始遍历
        if(!visited[i]){             //对每个连通分量调用一次BFS
            DFS(G,i);                //vi从未被访问过，从vi开始BFS
        }
    }
}
void DFS(Graph G,int v){
    visit(v);                        //访问顶点v
    visited[v] = TRUE;               //设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
                                     //检测v所有邻接点
            if(!visited[w]){         //w为v的尚未访问的邻接结点
                DFS(G,w);
            }//if
        }
}

6.深度优先搜索（DFS）非递归

• 因为使用了栈，使得遍历的方式从右到左进行，但仍然是深度优先遍历

void DFS_Non_Rc(Graph G,int v){
    //从顶点v开始进行深度优先搜索，一次遍历一个连通分量的所有顶点
    int w;                             //顶点序号
    InitStack(S);                      //初始化栈S
    for(int i=0;i<G.vexnum;i++){
        visited[i] = FALSE;            //初始化visited
    }
    push(S,v);                         //v入栈
    visited[v] = TRUE;                 //并且置visited[v]为真
    while(!IsEmpty(S)){
        k = Pop(S);                    //栈中退出一个顶点
        visit(k);                      //先访问，再将其子结点入栈
        for(w=FirstNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w)){
                                       //检测k所有邻接点
            if(!visited[w]){           //w为k的尚未访问的邻接结点
                Push(S,w);             //访问顶点w
                visited[w] = TRUE;     //对w做已访问标记
            }//if
        }
    }//while
}//DFS_Non_Rc

7.判断图是否为一棵树

• 如果有环，则失败，不是一棵树

bool BFS(Graph G,int v){
    visit(v);//
    visited[v] = TRUE;//
    Enqueue(Q,v);//
    while(!IsEmpty(Q)){
        Dequeue(Q,v);//
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
                                       //检测k所有邻接点
            if(!visited[w]){           //w为k的尚未访问的邻接结点
                visited[w] = TRUE;     //对w做已访问标记
                Enqueue(Q,w);//
            }else{
                return false;
            }
        }
    }//while
    return true;
}

8.找出u结点到v结点的所有路径

• 基于深度优先遍历算法，从结点u出发，递归深度优先遍历图中结点，若访问到结点v，则输出该搜索路径上的结点。
• 为此，设置一个path数组来存放路径上的结点（初始为空），d表示路径长度（初始为-1）。

void FindPath(Graph G,int u,int v,int path[],int d){
    int w,i;
    ArcNode *p;                   //邻接表定义方法
    d++;                          //路径长度加一
    path[d] = u;                  //写入路径数组
    visited[u] = 1;               //已访问过标记
    if(u == v){
        print(path[]);            //输出路径
    }
    p = G->adjlist[u].firstarc;   //找到相邻接点
    while(p!=NULL){
        w = p->adjvex;            //w未被访问，则递归访问
        if(visited[w] == 0){
            FindPath(G,w,V,path,d);
        }
        p = p->nextarc;           //指向u的下一个结点
    }
    visited[u] = 0;               //恢复环境，使该顶点可重新使用
    
}