文章目录

• 一、图的存储结构
• • 有向图的邻接矩阵存储
  • 无向图的邻接表存储
• 二、图的遍历
• • 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");}
}

二、图的遍历

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) 算法

四、有向无环图及其应用

拓扑排序

关键路径

五、最短路径

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！