邻接表删除一条边的算法

邻接表删除一条边的算法

删边i-j
邻接矩阵：
有向图：map[i][j] = 0;
无向图：map[i][j] = map[j][i] = 0;
邻接表：
有向图：
p = v[i] -> firstedge；
pre = p;
while (p && p -> data != j)
{pre = p;p = p -> next;}
if (p && pre == p) v[i] -> firstedge = p -> next;
else if (p) pre -> next = p -> next;
无向图：
p = v[i] -> firstedge；
pre = p;
while (p && p -> data != j)
{pre = p;p = p -> next;}
if (p && pre == p) v[i] -> firstedge = p -> next;
else if (p) pre -> next = p -> next;

p = v[j] -> firstedge；
pre = p;
while (p && p -> data != i)
{pre = p;p = p -> next;}
if (p && pre == p) v[j] -> firstedge = p -> next;
else if (p) pre -> next = p -> next;

#include #include #include //含int_max #define vtype char //顶点值类型 #define etype int //边权值类型 #define maxvnum 50 //最大顶点个数 #define digraph 0 //有向图(网) #define undigraph 1 //无向图(网) #define invalid int_max //无效权值(最大整数表示无穷大) #define empty -1 //"空"顶点序号 //定义邻接矩阵表示的图类型graph: typedef struct { vtype v[maxvnum]; //顶点序列(顶点编号从0开始) etype w[maxvnum][maxvnum]; //邻接矩阵 int vn, en; //顶点数,边数 int kind; //图的种类：=digraph表示有向图(网)，=undigraph表示无向图(网) }graph; int visited[maxvnum]; //访问标志数组(=1已访问，=0未访问)。遍历时用到的全局量。 void creategraph(graph &g, vtype *vex, int vvw[], int kind) { int i, j, p, n, w; n = strlen(vex); g.vn = n; //顶点数 g.kind = kind; //图的种类 //置顶点序列: for (i = 0; i < n; i++) g.v[i] = vex[i]; //初始化邻接矩阵: for (i = 0; i < n; i++) for (j = 0; j < n; j++) g.w[i][j] = invalid; //构造邻接矩阵: p = 0; //vvw数组元素“指针” n = 0; //边计数器 while (vvw[p] != -1) {//只要p未到结束位置便继续: i = vvw[p]; //边的起点序号 j = vvw[p + 1]; //边的终点序号 w = vvw[p + 2]; //边的权 g.w[i][j] = w; //置邻接矩阵的(i,j)位置元素 if (g.kind == undigraph) //若是无向图(网), g.w[j][i] = g.w[i][j]; //则置(i,j)的对称位置(j,i) n++; //边计数器加1 p += 3; //p指向下一组(vi,vj,wij) }//end while g.en = n; //边数 }//creategraph int nextadjvex(graph &g, int i) { int j, a; a = empty; //邻接点序号初始为"空" //在邻接矩阵的第v行找有效元素： for (j = 0; j < g.vn; j++) { if (g.w[i][j] == invalid) //若当前元素是无效元素, continue; //则继续找。 if (!visited[j]) {//若当前有效元素未曾访问过,则作为邻接点a: a = j; break; }//end if }//end for return a; }//nextadjvex void visit(graph &g, int i) { printf("%c", g.v[i]); }//visit void dfs(graph &g, int i) {int a; visit(g, i); //访问i顶点 visited[i] = 1; //标注i顶点已访问 a = nextadjvex(g, i); //找出一个i的邻接点a while (a != empty) {//只要a存在便继续: if (visited[a] == 0) //若a未曾访问, dfs(g, a); //则从a出发继续进行深度优先遍历。 a = nextadjvex(g, i); //找出i的下一个邻接点a }//end while }//dfs void dfstrav(graph &g, int i) {int k; //初始化各顶点的访问标志为0(未曾访问): for (k = 0; k < g.vn; k++) visited[k] = 0; dfs(g, i); //从i出发遍历 //若g非连通图，执行一次dfs无法遍历所有顶点，还需用如下for对尚未访问的顶点dfs。 //若g是连通图，执行一次dfs就已遍历所有顶点，此时如下for什么也不做，因所有visited=1。 for (k = 0; k < g.vn; k++) if (!visited[k]) dfs(g, k); //对尚未访问的顶点dfs }//dfstrav //显示图的邻接矩阵 void showm(graph &g) { int row, col, n; n = g.vn; //顶点数 //以表格形式输出数组： //输出表头： printf(" "); for(col = 0; col < n; col++) printf("%3d",col); printf("\n"); printf("---+"); for(col = 0; col < n; col++) printf("---"); printf("\n"); //输出表体(矩阵元素)： for(row = 0; row < n; row++) { printf("%3d|", row); for(col = 0; col < n; col++) { if (g.w[row][col] == invalid) printf("%3c", '*'); else printf("%3d", g.w[row][col]); }//end for col printf("\n"); }//end for row printf("\n"); }//showm 你的串号我已经记下，采纳后我会帮你制作