数据结构(C++)图论基础
迪丽瓦拉
2024-05-23 03:21:34
0

数据元素称为顶点。

图是由顶点的有穷非空集合和顶点之间边的集合组成,表示为G=(V,E)。G表示一个图,V是顶点的集合,E是顶点之间边的集合。

如果图的任意两个顶点之间的边都是无向边,则称该图为无向图,否则为有向图。

边上带权的图称为带权图或网图。

度:指依附于该顶点的边的个数。

重要公式:在具有n个顶点e条边的无向图中,度数之和等于边数的两倍。

入度之和等于出度之和等于e。

无向完全图:如果任意两个顶点之间都存在边,则称该图为无向完全图。

含有n个顶点的无向完全图有n*(n-1)/2条边。

有向完全图:在有向图中,如果任意两顶点之间都存在方向互为相反的两条弧,则称为有向完全图。

含有n个顶点的有向完全图有n*(n-1)条边

路径的长度:路径上边的数目。

第一个顶点和最后一个顶点相同的路径称为回路。

简单路径:在路径序列中,顶点不重复出现的路径称为简单路径。

简单回路:除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路称为简单回路。

通常情况下,路径指的都是简单路径,回路指的都是简单回路。

连通图:在无向图中,如果顶点vi和vj之间存在路径,则称vi和vj是连通的。若任意顶点vi和vj之间均有路径,则称该图是连通图。

非连通图的极大连通子图称为连通分量。

在有向图中,对任意顶点vi和vj,若从顶点vi到vj均有路径,则称该图是强连通图。

非强连通图的极大强连通子图称为强连通分量。

无向图的邻接矩阵一定是对称矩阵,而有向图的邻接矩阵不一定对称。

邻接矩阵

图的深度优先遍历

void DFS(int v) {cout << vertex[v];visited[v] = 1;for (int j = 0; j < vertexNum; j++) {if (edge[v][j] == 1 && visited[j] == 0) {DFS(j);}}
}

图的广度优先遍历

void BFS(int v) {int w, j, Q[MaxSize];int front = -1, rear = -1;cout << vertex[v];visited[v] = 1;Q[++rear] = v;while (front != rear) {w = Q[++front];for (j = 0; j < vertexNum; j++) {if (edge[w][j] == 1 && visited[j] == 0) {cout << vertex[j];visited[j] == 1;Q[++rear] = j;}}}
}

邻接表

图的深度优先遍历

void dfs(int v) {int j;EdgeNode* p = NULL;cout << adjlist[v].vertex;visited[v] = 1;p = adjlist[v].firstEdge;while (p != NULL) {j = p->adjvex;if (adjvex[j] == 0) {DFS2(j);}p = p->next;}
}

图的广度优先遍历

void bfs(int v) {int w, j, Q[MaxSzie];int front = -1;int rear = -1;EdgeNode* p = NULL;cout << adjlist[v].vertex;visited[v] = 1;Q[++rear] = v;while (front != rear) {w = Q[++front];p = adjlist[w].first;while (p != NULL) {j = p->adjvex;if (visited[j] == 0) {cout << adjlist[j].vertex;visited[j] = 1;Q[++rear] = j;}p = p->next;}}
}

相关内容