|
图的顺序存储：
图没有顺序存储结构，但可以借助二维数组来表示元素 之间的关系，即邻接矩阵表示法。 用邻接矩阵表示法表示图，除了一个用千存储邻接矩阵的二维数组外， 还需要用一个一维数 组来存储顶点信息。 
深度优先遍历：
为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。 为此，设一 个辅助数组visited[n] , 其初始值置为"false"或者0, 一旦访问了顶点V, 便置visited[i]为"true" 或者1。 以该图为例： 
代码如下：
#include
#define MaxInt 0
#define MVNum 100
typedef char VerTexType; //顶点类型
typedef int ArcType; //边权值类型
//邻接矩阵存储结构
typedef struct
{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum, arcnum; //图的当前点数和边数
}AMGraph;
void printGraph(AMGraph G);
int LocateVex(AMGraph G, char v);
//创建无向图
void CreateUDN(AMGraph &G)
{
G.vexnum = 8; //输入总顶点数和边数
G.arcnum = 9;
G.vexs[0] = 'v1'; //输入顶点信息
G.vexs[1] = 'v2';
G.vexs[2] = 'v3';
G.vexs[3] = 'v4';
G.vexs[4] = 'v5';
G.vexs[5] = 'v6';
G.vexs[6] = 'v7';
G.vexs[7] = 'v8';
for (int i = 0; i
G.arcs[i][j] = MaxInt;
}
}
//输入并建立边，由于是无向图，故一条边需要建立两次
int i, j;
i = LocateVex(G, 'v1');
j = LocateVex(G, 'v2');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v1');
j = LocateVex(G, 'v3');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v2');
j = LocateVex(G, 'v4');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v2');
j = LocateVex(G, 'v5');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v5');
j = LocateVex(G, 'v8');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v4');
j = LocateVex(G, 'v8');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v3');
j = LocateVex(G, 'v6');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v3');
j = LocateVex(G, 'v7');
G.arcs[i][j] = G.arcs[j][i] = 1;
i = LocateVex(G, 'v6');
j = LocateVex(G, 'v7');
G.arcs[i][j] = G.arcs[j][i] = 1;
//打印图的邻接矩阵
printGraph(G);
}
//确定顶点在顶点表数组中的下边，并返回
int LocateVex(AMGraph G, char v)
{
for (int i = 0; i
return i;
}
}
}
//输出打印
void printGraph(AMGraph G)
{
for (int i = 0; i
printf("%d ", G.arcs[i][j]);
}
printf("\n");
}
}
//邻接矩阵深度优先遍历
bool visited[MVNum]; //辅助数组，false表示没被访问
void DFS_AM(AMGraph G, int v)
{
printf("v%c->", G.vexs[v]);
visited[v] = true;
for (int w = 0; w
DFS_AM(G, w);
}
}
}
int main()
{
AMGraph G;
CreateUDN(G);
int v = 0; //从0号下标开始遍历访问
DFS_AM(G, v);
}
运行结果：
|