图的邻接表建立问题for(k=0;karcnum;k++){cin>>v1>>v2;i=LocateV(G,v1);//

邻接表有多种实现方式,比如最简单的动态链表,对于一个无向图,为每个节点建一个动态链表,储存的只是这个节点每个相邻的点,而在邻接矩阵中,对于每个节点需要把它与其他所有点的关系都表示出来（相邻为1,不相邻为0）,空间复杂度明显是邻接矩阵大,至于查询两者各有千秋,如果只是查询两个点之间是否相邻,邻接矩阵当然更快,但如果是做dfs的话,找当前节点相邻的点,如果用邻接矩阵的话每次都要从1扫到n,如果用邻接表的话每次只需把当前节点邻接表后的点都取出来即可.

邻接矩阵
v1 v2 v3 v4 v5 v1 0 1 0 1 0 v2 1 0 0 1 1 v3 0 0 0 1 1 v4 1 1 1 0 0 v5 0 1 1 0 0
邻接表
v1 -> v2 -> v4 v2 -> v1 -> v4 -> v5 v3 -> v4 -> v5
v4 -> v1 -> v2 -> v3 v5 -> v2 -> v3
度
v1 2
v2 3
v3 2
v4 3
v5 2

不太用到，试着写一下
void InsertEdge(ALGraph *g,int startVex/*新边的出发顶点*/,int targetVex/*新边的目的顶点*/,float weight)
{
if(startVex < 0||startVex >= MaxVertexNum||targetVex < 0||targetVex >= MaxVertexNum)
{
printf("顶点错误");
return;
}
EdgeNode *pEdge = (EdgeNode*)malloc(sizeof(EdgeNode)); //创建新的EdgeNode
pEdge->adjvex = targetVex;//设置新EdgeNode中的目标节点
pEdge->weight = weight；
pEdge->next = g->adjlist[startVex].firstedge;//在VertexNode边链表的头部插入新边
g->adjlist[startVex].firstedge = pEdge;
}
// typedef VertexNode AdjList[MaxVertexNum]；对于这一句，用AdjList创建的对象,比如AdjList al,al是一个数组，可以用al[0]访问,这个数组每个元素的类型是VertexNode

(1)每个点关联一个量d,让所有定点的d值都为0
(2)对v进行广度优先搜索
(3)bfs后d值最大的点就是离v最远的点.

因为拓扑中两个结点只有一个单向边,用邻接表更节省空间,而且在实现拓扑排序时,查找下一个处理的结点,只需查找邻接表指针项为空的结点,查找平均复杂度为O(n)如果用邻接矩阵的话,必须从头开始扫描,平均复杂度为O(n^2)

如果有对称元素 aij 和 aji 分别是1和0,那么一定是有向图(有一条有向边连接两点)
但如果所有的对应元素都相同,就无法判断是有向图还是无向图

用C++实现的,希望对你有所帮助.#include #include using namespace std; #define int_max 10000#define inf 9999 #define max 20//…………………………………………邻接矩阵定义……………………typedef struct Arc...

你肯定还没看懂邻接表,adjvex就是顶点的数组地址,每个顶点都有自己的物理地址,通过数组来存储比较方便操作,不然怎么找到它,你想想.至于前面的算法,我想你看懂了邻接表之后看算法很简单了,这算法没什么技术含量.就是直接利用邻接表的特点

int ComputeOutDegree(ALGraph G,Vnode V)
{
int count= 0;
ArcNode *p;
p=V->firstarc;
while(p){count++;p=p->nextarc;}
return count;
}
其实这个是最简单的,在用邻接表表示的有向图中第i 个链表中的结点个数只是顶点vi的出度,求顶点入度的难度稍微要复杂些,必须遍历整个邻接表.

这样是对的
设一个方案P中.共有W场,赢了N场,平了K场,则输了(W-N-K)场
那么该方案赢得的钱数为200N-200(W-N-K)=400N+200K-200W
因-200W一定..该题就是求最大的400N+200K
现在证明对于N最大,且在N最大的情况下K最大的方案P1,其赢得的钱设为T1,对任意方案Pi,T1>=Ti
1)对于方案Pi,如果Ni=N1,则Ki

不是说要用到栈,而是说用到栈的先进后出的算法而已,题目就是这么问的!

广度优先用队列.深度优先用栈.

d

删边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;

B,广搜都是队列
邻接表是链表

graphHead[] ADTGraph=new graphHead[N];
可是你数组里面 每一个graphHead都没有初始化!每一个graphHead[i]=new graphHead();

深度优先是从某个顶点出发,访问完后,寻找一个未访问的邻接顶点继续深度优先,如果此路不同就往回退,所以看邻接表,首先访问V1,完了后顺链寻找没有访问的邻接顶点,自然链表中的第一个结点就是v3,接着转到v3再来深度优先,访问v3后,在其链表中第一个邻接顶点是v4
接着访问v4,下面走不通,回到v3,继续顺链往后,自然是v5,v5的邻接顶点中v2还没有访问
所以序列为v1, v3, v4, v5, v2
再看广度优先,从某个顶点完成后,需要一口气将其邻接未访问的所有顶点都访问,后面类推
于是过程是先v1,再顺链将v3,v2依次访问完,然后再依次访问v3和v2的各个未访问邻接顶点,v3链表中顺链可以访问v4,v5,所以最后访问序列为v1, v3, v2, v4, v5

邻接矩阵：
0 0 1 1 0
0 0 0 1 1
1 0 0 0 1
1 1 0 0 0
0 1 1 0 0
邻接表：
A:C->D
B:D->E
C:A->E
D:A->B
E:B->C

作业不回答,仅仅修改你的程序.

用邻接表创建一个 < 无向图>,是不会涉及到弧头弧尾的,只有边邻接的两个顶点

int Count(Graph G)
{
int count=0;
for(v=0;v

邻接矩阵：
0 1 1 1 0
1 0 1 0 1
1 1 0 1 1
1 0 1 0 1
0 1 1 1 0
邻接表:
1->2->3->4
2->1->3->5
3->1->2->4->5
4->1->3->5
5->2->3->4

相对于三元组顺序表来讲,增加了一个行逻辑链接的向量（数组）用来指示各行第一个非零元的位置

#include
#include
#include
#include
#define maxsize 64
#define TRUE 1
#define FALSE 0
#define n 10
#define e 13
typedef char datatype ;
typedef char vextype;
typedef int adjtype;
typedef struct
{
vextype vexs[maxsize];
adjtype arcs[maxsize][maxsize];
}graph;
typedef struct
{
datatype data[maxsize];
int front,rear;
}sequeue;
typedef struct node
{
int adjvex;
struct node *next;
}edgenode;
typedef struct
{
vextype vertex;
edgenode *link;
}vexnode;
vexnode gl[maxsize];
graph *ga;
sequeue *Q;
graph *CREATGRAPH()
{
int i,j,k;
char ch;
system("cls");
scanf("%c",&ch);
printf("n请输入顶点信息(邻接矩阵):");
for(i=1;ivexs[i]);
for(i=1;iarcs[j][i]=1;
}
return ga;
}
void PRINT()
{
int i,j;
system("cls");
printf("n对应的邻接矩阵是：nn");
for(i=1;iadjvex=i;
s->next=gl[j].link;
gl[j].link=s;
}
}
void PRINTL()
{
int i;
edgenode *s;
system("cls");
printf("n对应的邻接表是：n");
for(i=1;iadjvex);
s=s->next;
}
printf("n");
}
}
sequeue *SETNULL(sequeue *P)
{
P->front=maxsize-1;
P->rear=maxsize-1;
return P;
}
int EMPTY(sequeue *Q)
{
if(Q->rear==Q->front)
return TRUE;
else
return FALSE;
}
sequeue *ENQUEUE(sequeue *Q,int k)
{
if(Q->front==(Q->rear+1)%maxsize)
{
printf("队列已满!n");
return NULL;
}
else
{
Q->rear=(Q->rear+1)%maxsize;
Q->data[Q->rear]=k;
}
return Q;
}
int DEQUEUE(sequeue *Q)
{
if(EMPTY(Q))
{
printf("队列为空,无法出队!n");
return FALSE;
}
else
{
Q->front=(Q->front+1)%maxsize;
return Q->data[Q->front];
}
return 1;
}
void BFS(int k)
{
int i,j;
int visited[maxsize]={0};
printf("n广度优先遍历后得到的序列是:");
Q=SETNULL(Q);
printf("%3c",ga->vexs[k]);
visited[k]=TRUE;
Q=ENQUEUE(Q,k);
while(!EMPTY(Q))
{
i=DEQUEUE(Q);
for(j=1;jarcs[i][j]==1)&&(!visited[j]))
{
printf("%3c",ga->vexs[j]);
visited[j]=TRUE;
Q=ENQUEUE(Q,j);
}
}
printf("nn深度优先遍历后得到的序列是:");
}
void BFSL(int k)
{
int i;
int visited[maxsize]={0};
edgenode *p;
Q=SETNULL(Q);
printf("n广度优先遍历后得到的序列是:");
printf("%3c",gl[k].vertex);
visited[k]=TRUE;
Q=ENQUEUE(Q,k);
while(!EMPTY(Q))
{
i=DEQUEUE(Q);
p=gl[i].link;
while(p!=NULL)
{
if(!visited[p->adjvex])
{
printf("%3c",gl[p->adjvex].vertex);
visited[p->adjvex]=TRUE;
Q=ENQUEUE(Q,p->adjvex);
}
p=p->next;
}
}
printf("nn深度优先遍历后得到的序列是:");
}
void DFS(int i)
{
int j;
static int visited[maxsize]={0};
printf("%3c",ga->vexs[i]);
visited[i]=TRUE;
for(j=1;jarcs[i][j]==1)&&(!visited[j]))
DFS (j);
}
void DFSL(int k)
{
int j;
edgenode *p;
static int visited[maxsize]={0};
printf("%3c",gl[k].vertex);
visited[k]=TRUE;
p=gl[k].link;
while(p)
{
j=p->adjvex;
if(!visited[j])
DFSL(j);
p=p->next;
}
}
void main()
{
int i,k;
int ch;
Q=malloc(sizeof(graph));
ga=malloc(sizeof(graph));
while(1)
{
printf("nnn");
printf("输入你的选择:");
scanf("%d",&ch);
switch(ch)
{
case 1:CREATADJLIST();
PRINTL();
printf("想从第几号结点开始:");
scanf("%d",&k);
BFSL(k);
DFSL(k);break;
case 2:ga=CREATGRAPH();
PRINT();
printf("想从第几号结点开始:");
scanf("%d",&i);
BFS(i);
DFS(i);break;
case 3:exit (0);
}
}
}

先给A、B、C、D、E按顺序编码1、2、3、4、5.随便找个起点,以A作为起点,A和B、C、E直接相连,则1（A）->2（B）->3（C）->5（E）结尾符；然后B是和A、D直接相连,则2（B）->1(A)->4(D)结尾符号；C直接和A、D、E相连,然后就直接一个个箭头对应着A、D、E对应的数字,把所有字母数一遍就可以了,说的很详细吧

百度一下很多的

因为要找到所有以这个顶点为终点的弧,必须将整个邻接表找完才行,这个不是逆邻接表,每个顶点的边表只管出不管入

邻接表储存时,是B.邻接矩阵储存就是C了.

tyrt6uyiuyjkhjkyuujhkuftywemcnwqwnhecvsyhgynsvsehvysdnfxdnvhbmndhnfdhuuvbvhdfbvhjbvn dfjbgvhadlfbgkjazsnzjd1fn4ghmj68d1fm4f2h4gj4m981xd4m194g9h16gv54h56g4mh141jk87gj1,8+05x684e684mnszwe5918 a687h2uh61li81,7u8j9fg741n987es9gv7498q71gv98w

从A出发,A的邻接点有5、4、2,即E、D、B,依次遍历并加上遍历标记；
再从E出发,E的邻接点有2,即B,已经遍历过；
再从D出发,D的邻接点有3,即C,遍历C并加上遍历标记；
此时所有节点都已经遍历过：A E D B C

这句话不对,邻接表和邻接矩阵,即可以存储无向图也可以存储有向图,稠密图适合用邻接矩阵,稀疏图适合用邻接表存储

结构严谨,内容充实,我会做!~