Java数据结构与算法(十)-图-白红宇

1.什么是图

图是一种和树相像的数据结构，通常有一个固定的形状，这是有物理或者抽象的问题来决定的。

2.邻接

如果两个定点被同一条便连接，就称这两个定点是邻接的。

3.路径

路径是从一个定点到另一个定点经过的边的序列。

4. 连通图和非连通图

至少有一挑路径可以连接所有的定点，那么这个图就是连通的，否则是非连通的。

5.有向图和无向图

有向图的边是有方向的，入只能从A到B，不能从B到A。

无向图的边是没有方向的，可以从A到B，也可以从B到A。

6.带权图

在有些图中，边被富裕了一个权值，权值是一个数字，他可以代表如两个顶点的物理距离，或者是一个顶点到另一个顶点的时间等等，这样的图叫做带权图。

7.程序实现

#include 
     
      #define  MAXVEX 100      //最大顶点数#define INFINITY 65535   //最大权值typedef int EdgeType;    //权值类型自己定义typedef char VertexType;  //顶点类型自己定义#pragma once#pragma region 邻接矩阵结构体typedef struct {    VertexType vex[MAXVEX];   //顶点表    EdgeType arg[MAXVEX][MAXVEX];  ///权值表-邻接矩阵    int numVertexes,numEdges;  //图中的边数和顶点数}GraphArray;#pragma endregion#pragma region 邻接表结构体//边表结点typedef struct EdgeNode{    int nNodevex;     //邻接点的点表中结点的坐标    EdgeType nNodeWeight;   //用于网图中边的权值    EdgeNode* next;       //链域，指向下一个邻接点}EdgeNode,*pEdgeNode;//顶点表结点typedef struct VertexNode{    VertexType nNodeData;   //顶点表中存储的数据    pEdgeNode pFirstNode;   //顶点表和边表中关联指针，指向边表头指针}VertexNode,pVertexNode,VertexList[MAXVEX];//图结构typedef struct{    VertexList vertexList;    int numVertess,numEdges;}GraphList;#pragma endregionclass GraphData{public:    GraphData(void);    ~GraphData(void);    #pragma region 创建邻接矩阵    void CreateGraphArray(GraphArray* pGraphArray,int numVer,int numEdegs);    int GetGraphLocation(GraphArray* pGraphArrray,char chpoint);    #pragma endregion    #pragma region 创建邻接表    void CreateGraphList(GraphList* pList,int numVer,int numEdegs);    int GetGraphListLocation(GraphList* pList,char chpoint);    #pragma endregion};

#include "GraphData.h"GraphData::GraphData(void){}GraphData::~GraphData(void){}int GraphData::GetGraphLocation(GraphArray* pGraphArrray,char chpoint){    int i = 0;    for (i = 0;i< pGraphArrray->numVertexes;i++)    {        if (pGraphArrray->vex[i] == chpoint)        {            break;;        }    }    if (i >= pGraphArrray->numVertexes)    {        return -1;    }    return i;}/// /// 创建邻接矩阵/// 
        void GraphData::CreateGraphArray(GraphArray* pGraphArray,int numVer,int numEdegs){    int weight = 0;    pGraphArray->numVertexes = numVer;    pGraphArray->numEdges = numEdegs;        //创建顶点表    for (int i= 0; i < numVer;i++)    {        pGraphArray->vex[i] = getchar();        while(pGraphArray->vex[i] == '\n')        {            pGraphArray->vex[i] = getchar();        }    }    //创建邻接表的边矩阵    for (int i = 0; i < numEdegs; i++)    {        for (int j = 0;j < numEdegs ; j++)        {            pGraphArray->arg[i][j] = INFINITY;        }            }    for(int k = 0; k < pGraphArray->numEdges; k++)    {        char p, q;        printf("输入边(vi,vj)上的下标i，下标j和权值:\n");        p = getchar();        while(p == '\n')        {            p = getchar();        }        q = getchar();        while(q == '\n')        {            q = getchar();        }        scanf("%d", &weight);            int m = -1;        int n = -1;        m = GetGraphLocation(pGraphArray, p);        n = GetGraphLocation(pGraphArray, q);        if(n == -1 || m == -1)        {            fprintf(stderr, "there is no this vertex.\n");            return;        }        //getchar();        pGraphArray->arg[m][n] = weight;        pGraphArray->arg[n][m] = weight;  //因为是无向图，矩阵对称    }    }#pragma regionvoid GraphData::CreateGraphList(GraphList* pList,int numVer,int numEdegs){    int weight = 0;    GraphList *pGraphList = pList;    pGraphList->numVertess = numVer;    pGraphList->numEdges = numEdegs;    EdgeNode* firstNode,*secondNode;    //创建顶点表    for (int i= 0; i < numVer;i++)    {        pGraphList->vertexList[i].nNodeData = getchar();        pGraphList->vertexList[i].pFirstNode = NULL;        while(pGraphList->vertexList[i].nNodeData == '\n')        {            pGraphList->vertexList[i].nNodeData = getchar();        }    }    //创建边表        for(int k = 0; k < pGraphList->numEdges; k++)    {        char p, q;        printf("输入边(vi,vj)上的下标i，下标j和权值:\n");        p = getchar();        while(p == '\n')        {            p = getchar();        }        q = getchar();        while(q == '\n')        {            q = getchar();        }        scanf("%d", &weight);            int m = -1;        int n = -1;        m = GetGraphListLocation(pGraphList, p);        n = GetGraphListLocation(pGraphList, q);        if(n == -1 || m == -1)        {            fprintf(stderr, "there is no this vertex.\n");            return;        }        //getchar();        //字符p在顶点表的坐标为m，与坐标n的结点建立联系权重为weight        firstNode = new EdgeNode();        firstNode->nNodevex = n;        firstNode->next = pGraphList->vertexList[m].pFirstNode;        firstNode->nNodeWeight = weight;        pGraphList->vertexList[m].pFirstNode = firstNode;        //第二个字符second        secondNode = new EdgeNode();        secondNode->nNodevex = m;        secondNode->next = pGraphList->vertexList[n].pFirstNode;        secondNode->nNodeWeight = weight;        pGraphList->vertexList[n].pFirstNode = secondNode;    }}int GraphData::GetGraphListLocation(GraphList* pList,char chpoint){    GraphList *pGraphList = pList;    int i = 0;    for (i = 0;i< pGraphList->numVertess;i++)    {        if (pGraphList->vertexList[i].nNodeData == chpoint)        {            break;;        }    }    if (i >= pGraphList->numVertess)    {        return -1;    }    return i;}#pragma endregion

#include 
     
      #include "GraphData.h"using namespace std;//void PrintGrgph(GraphList *pGraphList){    int i =0;    while(pGraphList->vertexList[i].pFirstNode != NULL && i
      
       vertexList[i].nNodeData);        EdgeNode *e = NULL;        e = pGraphList->vertexList[i].pFirstNode;        while(e != NULL)        {            printf("%d  ", e->nNodevex);            e = e->next;        }        i++;        printf("\n");    }    }int main(){    int numVexs,numEdges;    GraphData* pTestGraph = new GraphData();    GraphArray graphArray;    GraphArray* pGraphArray = &graphArray;    GraphList* pGgraphList = new GraphList();        cout<<"输入顶点数和边数"<
       
        >numVexs>>numEdges;    cout<<"顶点数和边数为："<
        
         <
         
          <
          
           CreateGraphArray(pGraphArray,numVexs,numEdges); for(int i = 0; i< numEdges;i++) { for (int j = 0;j< numEdges;j++) { cout<
           
            arg[i][j]; } cout<
            
             CreateGraphList(pGgraphList,numVexs,numEdges); PrintGrgph(pGgraphList); system("pause");}

借鉴文章