图的基本操作及其相关应用

梦里梦外; 2022-10-08 14:22 244阅读 0赞

### 文章目录 ###

*  一、图的存储结构
 *   *  有向图的邻接矩阵存储
     *  无向图的邻接表存储
 *  二、图的遍历
 *   *  2.1 深度优先搜索（DFS）
     *  2.2 广度优先搜索（BFS）
 *  三、图的连通性
 *   *  3.1 连通分量和生成树
     *  3.2 最小生成树
     *   *  普里姆(Prim)算法
         *  克鲁斯卡尔 (Kruskal) 算法
 *  四、有向无环图及其应用
 *   *  拓扑排序
     *  关键路径
 *  五、最短路径

# 一、图的存储结构 #

## 有向图的邻接矩阵存储 ##

//邻接矩阵
    typedef struct
    {
        
    	VertexType vexs[MAX_VERTAX_NUM];
    	AdjMatrix arcs[MAX_VERTAX_NUM][MAX_VERTAX_NUM];
    	int vexnum, arcnum;
    }MGraph;
    
    int LocateVex(MGraph G, VertexType e)
    {
        
    	int i;
    	for (i = 0; i < G.vexnum; i++)
    	{
        
    		if (G.vexs[i] == e)
    			return i;
    	}
    	return -1;
    }
    
    Status CreateDG(MGraph& G)
    {
        
    	int i, j, k;
    	char v1, v2;
    	cout << "请输入图的顶点个数（vexnum），边数（arcnum）";
    	cin >> G.vexnum >> G.arcnum;
    	getchar();
    	cout << "请输入顶点（例：abcd）:";
    	for (i = 0; i < G.vexnum; i++)
    		G.vexs[i] = getchar();
    	getchar();
    
    	for (i = 0; i < G.vexnum; i++)
    		for (j = 0; j < G.vexnum; j++)
    			G.arcs[i][j] = INFINITYA;
    
    	for (k = 0; k < G.arcnum; k++)
    	{
        
    		cout << k;
    		cout << "请输入两个顶点:";
    		cin >> v1 >> v2;
    		getchar();
    		i = LocateVex(G, v1);
    		j = LocateVex(G, v2);
    		G.arcs[i][j] = 1;
    	}
    	return OK;
    }

## 无向图的邻接表存储 ##

#define MAX_VERTAX_NUM 20 //最大顶点个数
    typedef char Vertextype;
    //邻接表类型 
    typedef struct ArcNode {
        
        int adjvex; //邻接点域 
        struct ArcNode* nextarc; //指向下一个邻接点的指针域 
    }ArcNode;
    //表头结点类型 
    typedef struct VNode
    {
        
        Vertextype data; //顶点域 
        ArcNode* firstarc; //边表头指针 
    }VNode, AdjList[MAX_VERTAX_NUM];
    //图的类型 
    typedef struct
    {
        
        AdjList vertices; //邻接表 
        int vexnum, arcnum; //顶点数 边数 
        //int kind;
    }ALGraph;
    typedef struct CSNode
    {
        
        Vertextype e;
        CSNode* lchild, * nextsibling;
    }CSNode, * CSTree;
    int visited[MAX_VERTAX_NUM];
    
    int LocateVex(ALGraph G, char e)
    {
        
        int i;
        for (i = 0; i < G.vexnum; i++)
        {
        
            if (G.vertices[i].data == e)
                return i;
        }
        return -1;
    }
    
    void CreateUDG(ALGraph& G)
    {
        
        int i, k, j;
        ArcNode* p, * s;
        char v1, v2;
    //    printf("图的种类已默认为无向图\n");
    //    G.kind = 1;
        printf("请输入顶点数和边数：（空格区分）");
        scanf("%d%d", &G.vexnum, &G.arcnum);
        getchar();
        printf("开始建立顶点表\n");
        for (i = 0; i < G.vexnum; i++)
        {
        
            printf("请输入第%d个顶点的信息:", i + 1);
            G.vertices[i].data = getchar();
            getchar();
            G.vertices[i].firstarc = NULL;
        }
        printf("建立边表\n");
        for (k = 0; k < G.arcnum; k++)
        {
        
            printf("请输入两个顶点（例：ab代表a~b）:");
            scanf("%c%c", &v1, &v2);
            getchar();
            i = LocateVex(G, v1);
            j = LocateVex(G, v2);
            p = (ArcNode*)malloc(sizeof(ArcNode));
            p->adjvex = j;
            p->nextarc = G.vertices[i].firstarc;
            G.vertices[i].firstarc = p;
            s = (ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex = i;
            s->nextarc = G.vertices[j].firstarc;
            G.vertices[j].firstarc = s;
        }
        printf("边表建立完成\n");
    }
    //打印邻接表
    void DispGraph(ALGraph G)
    {
        
        int i;
        printf("打印邻接表:\n");
        for (i = 0; i < G.vexnum; i++)
        {
        
            printf("%d->", i);
            while (1)
            {
        
                if (G.vertices[i].firstarc == NULL)
                {
        
                    printf("^");
                    break;
                }
                printf("%d->", G.vertices[i].firstarc->adjvex);
                G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
            }
            printf("\n");
        }
    }

# [二、图的遍历][Link 1] #

## 2.1 深度优先搜索（DFS） ##

https://blog.csdn.net/qq\_46672746/article/details/118097444

## 2.2 广度优先搜索（BFS） ##

https://blog.csdn.net/qq\_46672746/article/details/118097444

# 三、图的连通性 #

## 3.1 连通分量和生成树 ##

## 3.2 最小生成树 ##

### 普里姆(Prim)算法 ###

### 克鲁斯卡尔 (Kruskal) 算法 ###

# 四、有向无环图及其应用 #

## 拓扑排序 ##