本文共 7969 字，大约阅读时间需要 26 分钟。

第六章 图 —— 邻接矩阵/邻接表构造图实现BFS/DFS/Dijkstra算法

要求：

此处均以无向图为例

邻接矩阵：

代码如下：

#include
   
    #include
    
     #include
     
      #include
      
       #define MaxVerNum 100 //顶点最大数目值#define VexType char //顶点数据类型#define EdgeType int //边数据类型,无向图时邻接矩阵对称，有权值时表示权值，没有时1连0不连#define INF 0x3f3f3f3f//作为最大值using namespace std;//图的数据结构typedef struct Graph{       VexType Vex[MaxVerNum];//顶点表    EdgeType Edge[MaxVerNum][MaxVerNum];//边表    int vexnum, arcnum;//顶点数、边数} Graph;//迪杰斯特拉算法全局变量bool S[MaxVerNum]; //顶点集int D[MaxVerNum];  //到各个顶点的最短路径int Pr[MaxVerNum]; //记录前驱//初始化函数void InitGraph(Graph& G){       memset(G.Vex, '#', sizeof(G.Vex));//初始化顶点表    //初始化边表    for (int i = 0; i < MaxVerNum; i++)        for (int j = 0; j < MaxVerNum; j++)            G.Edge[i][j] = INF;    G.arcnum = G.vexnum = 0;          //初始化顶点数、边数}//插入顶点函数bool InsertNode(Graph& G, VexType v){       if (G.vexnum < MaxVerNum)    {           G.Vex[G.vexnum++] = v;        return true;    }    return false;}//插入边函数bool InsertEdge(Graph& G, VexType v, VexType w, int weight){       int p1, p2;//v,w两点下标    p1 = p2 = -1;//初始化    for (int i = 0; i < G.vexnum; i++)//寻找顶点下标    {           if (G.Vex[i] == v)            p1 = i;        if (G.Vex[i] == w)            p2 = i;    }    if (-1 != p1 && -1 != p2)//两点均可在图中找到    {           G.Edge[p1][p2] = G.Edge[p2][p1] = weight;//无向图邻接矩阵对称        G.arcnum++;        return true;    }    return false;}//判断是否存在边(v,w)函数bool Adjancent(Graph G, VexType v, VexType w){       int p1, p2;//v,w两点下标    p1 = p2 = -1;//初始化    for (int i = 0; i < G.vexnum; i++)//寻找顶点下标    {           if (G.Vex[i] == v)            p1 = i;        if (G.Vex[i] == w)            p2 = i;    }    if (-1 != p1 && -1 != p2)//两点均可在图中找到    {           if (G.Edge[p1][p2] == 1)//存在边        {               return true;        }        return false;    }    return false;}bool visited[MaxVerNum];//访问标记数组，用于遍历时的标记//广度遍历函数void BFS(Graph G, int start){       queue
       
         Q;//辅助队列    cout << G.Vex[start];//访问结点    visited[start] = true;    Q.push(start);//入队    while (!Q.empty())//队列非空    {           int v = Q.front();//得到队头元素        Q.pop();//出队        for (int j = 0; j < G.vexnum; j++)//邻接点        {               if (G.Edge[v][j] < INF && !visited[j])//是邻接点且未访问            {                   cout << "->";                cout << G.Vex[j];//访问结点                visited[j] = true;                Q.push(j);//入队            }        }    }//while    cout << endl;}//深度遍历函数（递归形式）void DFS(Graph G, int start){       cout << G.Vex[start];//访问    visited[start] = true;    for (int j = 0; j < G.vexnum; j++)    {           if (G.Edge[start][j] < INF && !visited[j])//是邻接点且未访问        {               cout << "->";            DFS(G, j);//递归深度遍历        }    }}//最短路径 - Dijkstra算法 参数：图G、源点vvoid Dijkstra(Graph G, int v){       //初始化    int n = G.vexnum;//n为图的顶点个数    for (int i = 0; i < n; i++)    {           S[i] = false;        D[i] = G.Edge[v][i];        if (D[i] < INF)            Pr[i] = v; //v与i连接，v为前驱        else            Pr[i] = -1;    }    S[v] = true;    D[v] = 0;    //初始化结束,求最短路径，并加入S集    for (int i = 1; i < n; i++)    {           int min = INF;        int temp;        for (int w = 0; w < n; w++)            if (!S[w] && D[w] < min) //某点temp未加入s集，且为当前最短路径            {                   temp = w;                min = D[w];            }        S[temp] = true;        //更新从源点出发至其余点的最短路径 通过temp        for (int w = 0; w < n; w++)            if (!S[w] && D[temp] + G.Edge[temp][w] < D[w])            {                   D[w] = D[temp] + G.Edge[temp][w];                Pr[w] = temp;            }    }}//输出最短路径void Path(Graph G, int v){       if (Pr[v] == -1)        return;    Path(G, Pr[v]);    cout << G.Vex[Pr[v]] << "->";}//打印图的顶点表void PrintVex(Graph G){       cout<<"图中的顶点为：";    for (int i = 0; i < G.vexnum; i++)    {           cout << G.Vex[i] << " ";    }    cout << endl;}//打印图的边矩阵void PrintEdge(Graph G){       cout<<"邻接矩阵为："<
        
         > vn; cout << "请输入边数目:" << endl; cin >> an; cout << "请输入所有顶点名称:" << endl; for (int i = 0; i < vn; i++) { cin >> v; if (InsertNode(G, v)) continue;//插入点 else { cout << "输入错误！" << endl; break; } } cout << "请输入所有边（每行输入边连接的两个顶点及权值）:" << endl; for (int j = 0; j < an; j++) { int weight; cin >> v >> w >> weight; if (InsertEdge(G, v, w, weight)) continue;//插入边 else { cout << "输入错误！" << endl; break; } } PrintVex(G); cout<
         
          > vname; for (int i = 0; i < G.vexnum; i++) { if (G.Vex[i] == vname) v = i; } if (v == -1) { cout << "没有找到输入点！" << endl; return; } Dijkstra(G, v); cout << "目标点" << "\t" << "最短路径值" << "\t" << "最短路径" << endl; for (int i = 0; i < G.vexnum; i++) { if (i != v) { cout << " " << G.Vex[i] << "\t" << " " << D[i] << "\t"; Path(G, i); cout << G.Vex[i] << endl; } }}//菜单void menu(){ cout<<"1.创建图" << endl; cout<<"2.广度遍历"<
          
           >choice; if (5 == choice) break; switch (choice) { case 1: CreateGraph(G); break; case 2: BFSTraverse(G); break; case 3: DFSTraverse(G); break; case 4: Shortest_Dijkstra(G); break; default: printf("输入错误！！！\n"); break; } cout<
          
         
        
       
      
     
    
   

邻接表

#include 
   
    using namespace std;#define MAXSIZE 100int v[MAXSIZE];//标志位，判断该结点有没有被访问typedef struct ArcNode //定义边节点{       int adjvex;//该节点在图中的位置    int weight;//权值    struct ArcNode *next;//指向下一条边的指针} ArcNode;typedef struct VNode //定义顶点信息{       char data;    ArcNode *firstarc;//指向第一条依附于顶点的边的指针} VNode,AdjList[MAXSIZE];//AdjList表示邻接表类型typedef struct //定义邻接表{       int vexnum,arcnum;//顶点数和边数    AdjList vertices;} ALGraph;//定位函数（将点的名称转化为点的位置）int LocateVex(ALGraph G,char u){       int i;    for(i=1; i<=G.vexnum; ++i)        if(u==G.vertices[i].data)            return i;    return -1;}void CreatUDG(ALGraph &G)//构建无向图{       int i,n,m,p1,p2;    char a,b;    ArcNode *s;    cout<<"请输入顶点数和边数："<
    
     >n>>m;    G.vexnum=n;    G.arcnum=m;    cout<<"输入顶点名称："<
     
      >G.vertices[i].data;        G.vertices[i].firstarc=NULL;//一开始都指向NULL    }    cout<<"输入一条边对应的两个顶点："<
      
       >a>>b;        p1 = LocateVex(G,a);        p2 = LocateVex(G,b);//将名称转化为位置        s=new ArcNode[sizeof(ArcNode)];//生成一个新的边结点        s->adjvex=p2;//邻接点的序号为p2        s->next=G.vertices[p1].firstarc;        G.vertices[p1].firstarc=s;//将新结点前插至边表头部        s=new ArcNode[sizeof(ArcNode)];        s->adjvex=p1;        s->next=G.vertices[p2].firstarc;        G.vertices[p2].firstarc=s;//同上，将新结点前插至边表头部    }}int FirstAdjVex(ALGraph G,int k)//返回图G中与k相邻且未被访问过的点的编号，如果不存在这样的点返回-1{       ArcNode *s;    s=G.vertices[k].firstarc;    if(!s)        return -1;    while(s&&v[s->adjvex])//如果不空又访问过，就看下一个        s=s->next;    if(s)//不空说明找到了        return s->adjvex;    else//否则返回-1        return -1;}int NextAdjVex(ALGraph G,int k,int w)//返回图G中与k相邻、除了编号是w之外的未被访问过的点的编号，如果不存在这样的点返回-1{       ArcNode *s;    s=G.vertices[k].firstarc;    if(!s)        return -1;    while(s&&(v[s->adjvex]||s->adjvex==w))//不空，并且要么是访问过，要么是w，这样的点我们统统忽略        s=s->next;    if(s)//不空说明找到了        return s->adjvex;    else//否则-1        return -1;}void DFS(ALGraph G,int k)//对节点k进行深度优先遍历{       int w;    v[k]=1;//进来就置1    cout<
       
        <<" ";//遍历输出    for(w=FirstAdjVex(G,k); w!=-1; w=NextAdjVex(G,k,w)) //找到所有和k相邻的节点的编号，挨个深搜递归        if(!v[w])            DFS(G,w);}void DFSTraverse(ALGraph G)//对所有点进行深度优先遍历（防止在非连通图中遗漏点）{       int i;    memset(v,0,sizeof(v));    for(i=1; i<=G.vexnum; i++)        if(!v[i])            DFS(G,i);}void BFS(ALGraph G)//广度优先遍历{       int i,k,w;    queue
        
          q;//定义一个队列存储点的名称 memset(v,0,sizeof(v));//因为之前深搜过，这里重新置0一下 for(i=1; i<=G.vexnum; i++) //依次对每个顶点进行考察（此处相当于把BFS和BFSTraverse合并） if(!v[i])//只要不空 { v[i]=1;//只要不空，进来第一件事就是置1 cout<
         
          <<" ";//置1之后马上输出 q.push(G.vertices[i].data);//输出完了之后就入队 while(!q.empty())//只要队列不空 { k=LocateVex(G,q.front());//取队首元素 q.pop();//然后队首出队 for(w=FirstAdjVex(G,k); w!=-1; w=NextAdjVex(G,k,w)) //将所有和队首邻接的顶点依次入队，入一个，输出一个 if(!v[w]) { v[w]=1; cout<
          
           <<" "; q.push(G.vertices[w].data); } } }}int main(){ ALGraph G; CreatUDG(G); cout<<"DFS:"; DFSTraverse(G); cout<