当前位置:文档之家› 数据结构--图重点

数据结构--图重点

q = p;
DFSTree(G, w, q, visited);
生成森林:不完全图中的各个连通分量的生成树,构成图的生成森林
二、存储结构
顶点:可采用链表或数组存储顶点列表,一般采用链表存储
边:1.邻接矩阵(数组)
a.无向图:对称阵,可采用矩阵压缩存储方式。A[i][j] = 0表示 和 没有连接;A[i][j]= 1表示 和 有边连接;第i行的和表示顶点 的度
b.有向图:不对称阵。 表示顶点 到 的有向弧的权值; 表示表示顶点 到 没有弧连接或者i = j
enQueue(Q, w);
}
w = getNextNeighbor(G, v, w);
}
}
delete[] visited;
}
四、图的连通性问题(无向图)
1.深度优先生成树(深度优先搜索形成),广度优先生成树(广度优先搜索形成)
深度优先生成森林算法:
void DFSForest(Graph G, CSTree& T) {
CSTree q=null;
int n = G.vexnum;
bool* visited = new bool[n];
for(int i = 0; i < n; i++)visited[i] = false;
for (int v = 0; v < n; v++) {
if (!visited[v]) {
}
}
}
深度优先生成树算法:
void DFSTree(Graph G, int v, CSTree T, bool& visited[]){
visited[v] = true;
bool first = true;
CSTree q = null;
for (int w = getFirstNeighbor(G,v);w != -1; w = getNextNeighbor(G, v, w))
w = getNextNeighbor(G, v, w);
}
}
2.广度优先搜索(类似于树的层次遍历)
基本思想:假设从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问(非连通图),则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。
Quwhile(!isEmpty(Q)){
deQueue(Q, v);
w = getFirstNeighbor(G, v);
while(w != -1) {
if (!visited[w]) {
visit(getValue(G, w));
顶点结点:data(顶点数据),firstin(第一条入弧),firstout(第一条出弧)
三、图的遍历(每个顶点只被访问一次)
1.深度优先遍历(类似树的先根遍历)
基本思想:假设初始状态是图中所有顶点未曾被访问,则深度优先搜索可从图中某个顶点v出发,访问此结点,然后依次从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到;若此时图中尚有顶点未被访问(非连通图),则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。
代码:
viod BFS(Graph& G, int v) {
int i, w, n = G.vexnum;
bool*visited = new bool[n];
for(i = 0; i < n; i++) visited[i] =false;
visit(getValue(G, v));
visited[v] = true;
CSTree p = (CSTree) malloc(sizeof(CSNode));
*p = {getValue(G, v), null, null};
if(T == null) T = p;
else q->nextSibling = p;
q = p;
DFSTree(G, v, p, visited);
if (!visited[w]) {
CSTree p = (CSTree) malloc(sizeof(CSNode));
*p = {getValue(G, w), null, null};
if (first) {
T->lchild = p;
first = false;
}
else q->nextSibling = p;
一、定义与术语
图:无序数据结构
基本构成:1.边集(Edge):a.有向图,有向边<v, w>,弧,弧头,弧尾,权值
b.无向图,无向边(v, w),权值
2.顶点集(Vertices):a.无向图:度(TD(v))
b.有向图:出度(ID(v)),入度(OD(v)),度(TD(v) = ID(v) + OD(v))
2.邻接表(链表,有向无向都可用)
边结点:adjvex(邻接点),nextarc(下一条边),info(权值)
顶点结点:data(顶点数据),firstarc(第一条边)
3.十字链表(Othogonal List)
弧结点:tailvex(弧尾结点),headvex(弧头结点),tlink(弧尾相同的下一条弧),hlink(弧头相同的下一条弧),info(权值)
无向完全图:n个顶点, 条边
有向完全图:n个顶点, 条边
网:带权图
连通分量:无向图中的极大连通子图(多个),无向完全图的连通分量就是本身(一个)
强连通分量:有向图中的极大连通子图,其中 到 以及 到 都有路径
生成树:图的极小连通子图,含有图的全部n个顶点,只有n-1条边,少一条则不能连通,多一条则形成回路
代码:
void DFS(Graph&G, int v, bool first, bool visited[]) {
visit(getValue(G, v));
visited[v] = true;
int = getFirstNeighbor(G, v);
while(w != -1) {
if(!visited[w]) DFS(G, w, visited);
相关主题